Induction Homework Help: Proving Equations for Positive Integers

[McFlea]

Hi there, I am 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 can't 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.

 

[radou]

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.

 

[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.

 

[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 haven't covered arithmatic series at all yet, but I have done it previously therefore I doubt that we would be expect to use it?

 

[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:

[tex]\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?

 

[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:
$$\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.

 

[fopc]

I'll try your first question:

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)].

 

[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.