# Induction homework help

1. Nov 8, 2006

### McFlea

Hi there, Im having some problems with figuring out these two questions I have been given out for homework. Both of these make no sense to me and I cant seem to prove them, can anyone give me an insight to them?

1+5+9+ ... + (4n+1)=(n+1)(2n+1) for each positive integer n

and

2^2n - 1 is divisible by 3 for n = 1,2,3,....

any ideas?

Thanks.

2. Nov 8, 2006

Well, did you go through some examples of the application of mathematical induction? Do you know what it is? Inform yourself, make an effort to solve the problem, and if you get stuck, we'll be glad to help.

3. Nov 8, 2006

### Sane

For the first question, prove it by looking back to your notes on arithmatic series'.

For the second question, the answer will probably deal with series' again. I haven't looked at it yet, but I'll be glad to and update this post when I figure out anything else.

Last edited: Nov 8, 2006
4. Nov 8, 2006

### McFlea

What I know is that induction proves a statement holds for all natural numbers.. so the first step would be to check if n+1 is true there by adding (n+1) to both sides of the equation? Am I on the right track?

Sane, we havent covered arithmatic series at all yet, but I have done it previously therefore I doubt that we would be expect to use it?

5. Nov 8, 2006

### Sane

Well, that may not be the way to prove it, but it is an answer.

The arithmetic progression equation for the sum of numbers to (4n+1) is:

$$\frac{(n+1)(1+(4n+1))}{2}[/itex] You'll see that, if you do a right side/left side proof, it is equivilent to (n+1)(2n+1). Simple enough, no? 6. Nov 9, 2006 ### VietDao29 @Sane: To prove the sum of the first n terms of an arithmetic series, we use induction. That means, your argument is somewhat circular... ----------- @McFlea: Do you know how induction works? It goes like this. There are 3 steps. The first step is to prove that the statement is true for some stating value n (say, n = 1 in your first problem, since the smallest positive integer is 1). The second step is to assume that the statement holds for n = k (k is some number). The third, and also the final step is to use your assumption in Step 2, and prove that the statement is true for n = k + 1. So if the statement is true for n = 1 (the first step), then from the second and the third step, we can see that it's also true for n = 1 + 1 = 2. And since the statement is true for n = 2, we can conclude that it's true for n = 2 + 1 = 3. And since the statement is true for n = 3, it must be true for n = 3 + 1 = 4, and so on... Hence, it's true for all positive integers. ----------- Ok, I'll give you an example: Example: Prove that: [tex]\sum_{i = 1} ^ n (i) = \frac{n (n + 1)}{2}$$
Step 1:
Test for n = 1, the LHS is 1, and the RHS is also 1, hence the equation holds for n = 1.
Step 2:
Assume that the equation holds for some n = k, ie:
$$\sum_{i = 1} ^ k (i) = \frac{k (k + 1)}{2}$$
Step 3:
Use the assumption:
$$\sum_{i = 1} ^ k (i) = \frac{k (k + 1)}{2}$$
to prove that:
$$\sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}$$.
We start from what we know:
$$\sum_{i = 1} ^ k (i) = \frac{k (k + 1)}{2}$$
Adding (k + 1) to both sides, we have:
$$\Leftrightarrow \left( \sum_{i = 1} ^ k (i) \right) + (k + 1) = \frac{k (k + 1)}{2} + k + 1$$
$$\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k (k + 1) + 2k + 2}{2}$$
$$\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{k ^ 2 + 3k + 2}{2}$$
$$\Leftrightarrow \sum_{i = 1} ^ {k + 1} (i) = \frac{(k + 1) (k + 2)}{2}$$
Hence, the equation holds for n = k + 1. (Q.E.D)
Can you go from here?
Let's see if you can finish the 2 problems above.

7. Nov 13, 2006

### fopc

Let Universe equal nonnegative integers.
Proof by mathematical induction (first principle):
Basis clause: n=0 case. Clearly, this is true.
Induction clause: For arbitrary n >= 0 [[1+5+9+...+(4n+1) = (n+1)(2n+1)] -> [1+5+9+...+(4n+1)+(4n+5) = (n+2)(2n+3)]].
From the induction hypothesis we can write 1+5+9+...+(4n+1)+(4n+5) = (n+1)(2n+1)+(4n+5), which equals,
2n^2+7n+6. But (n+2)(2n+3) = 2n^2+7n+6.
Since n >= 0 was arbitrary, by Universal Generalization, we obtain the truth of the above stated
implication, for all n >= 0. But of course the implication is not what we're trying to prove.
"Extremal": Finally, by first principle, for all n >= 0 [1+5+9+...(4n+1) = (n+1)(2n+1)].

8. Nov 14, 2006

### tuananh

and here is the answer of the second question:

Note that: 2^(2n) - 1 = 4^n -1
and use the equatity : a^n - b^n = (a-b)(a^(n-1)b - a^(n-2)b^2 + ...)
with a=4, b=1

Or we can check all steps of the induction process as follow:

With n=1: 4^1 -1 = 3 is divisible by 3
Suppose the statement is true with n=k, i.e 4^k -1 is divisible by 3 (*)
The, with n=k+1, we have:
4^(k+1) -1 = 4.4^k -1 = 3.4^k + (4^k - 1)
The second term (4^k-1) is divisible by 3 according to (*), the first term apparently is divisible by 3. Thus, 4^(k+1) - 1 is also.