Hi, im new college student learn calculus. i already watch the video from youtube and so on but i still cannot understand how to solve this.. Can someone explain using strong induction how to prove [math]a_1=3,a_2=6\space and\space a_n+_2=a_n+_1\space+2a_n-2n+1\space so\space a_n=2^n+n\space for\space every\space integer\space n≥1[/math]
Mathematical induction
- Thread starter Leons
- Start date
lev888
Elite Member
- Joined
- Jan 16, 2018
- Messages
- 2,939
What do you know about induction? Have you used it before? Can you list the steps of an induction proof and do the first one?
it have 3 steps. First induction basis, show that p(1) true. Second induction hypothesis, assume that n=k true. Third, induction step, prove that n=k+1 true.. i just only used this step before, for the strong induction i haven't used it.. i will try first.. can you check if my answer correct or not.. im still confuse for the step number 3
Last edited:
lev888
Elite Member
- Joined
- Jan 16, 2018
- Messages
- 2,939
Doesn't look right to me.
You have a sequence defined recursively - each terms is defined through 2 previous terms. You need to prove that each term also follows the second, explicit, definition.
In the first step you need to show that the above is true for n=1. Plug in n=1 into both definitions and show that they produce the same result.
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,081
Since each term is defined in terms of the two previous terms, in your induction step you will need to have two previous cases known to be true. So the base case to be verified will cover both i=1 and i=2. Then the inductive step will use the recursion.
Also, you don't really mean this, do you?
Also, you don't really mean this, do you?
oh, I see... this one, is it correct? and for the one that i starred, is it I have to write it too?
Actually i dont quite understand what im write for the step 2.. =( is this what you mean?
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,081
You are right about the base case; 3 and 6 are given, and you've shown that the formula yields them.
But the inductive step is to assume that [imath]a_i = 2^i+i[/imath], not for every [imath]i\ge 1[/imath], which is what you are to prove, but for every [imath]1\le i\le k[/imath] for some given k, and use that to prove that it is true for the next case, namely [imath]a_{k+1} = 2^{k+1}+(k+1)[/imath].
So, what does the definition say [imath]a_{k+1}[/imath], using the formula for the two preceding terms? Try to manipulate that to look like [imath]2^{k+1}+(k+1)[/imath].
No, you don't need to show the value of [imath]a_3[/imath]; you'll be using the definition in the inductive step.
The problem is oddly worded, but clearly says to use strong induction. Here is how I would set it up.
[math]\text {PROVE P(n) such that } a_n = 2^n + n \text { for every positive integer } n, \text {given }[/math]
[math]a_1 = 3, \ a_2 = 6 \text { and } a_n = a_{n-1} + 2a_{n-2} - 2n + 1 \text { for n } \ge 3.[/math]
[math]\text {Step I: } n = 1 \implies a_n = 3 = 2 + 1 = 2^1 + 1 = 2^n + n.\\ n = 2 \implies a_n = 6 = 4 + 2 = 2^2 + 2 = 2^n + n \implies \\ \text {P(n) is true for every positive integer} \le 2.[/math]
[math]\text {STEP II: Thus, there exists a positive integer } k \ge 2\\ \text { such that P(j) is true for every positive integer} \le k.[/math]
[math]k + 1 \text { is an integer} \ge 3 \text { because } k \text { is an integer} \ge 2.[/math]
[math]a_{k+1} = a_{(k+1)-1} + 2a_{(k+1)-2} - 2\{(k + 1) - 2\} + 1 \text { by hypothesis.}[/math]
[math]\therefore a_{k+1} = a_k + 2a_{k-1} - 2(k - 1) + 1 =\\ (2^k + k) + 2\{2^{(k - 1)} + (k - 1)\} - 2k + 2 + 1 =\\ 2^k + k + 2 * 2^{(k-1)} +2k - 2 - 2k + 3 =\\ 2^k + 2^k + 3k - 2k + 3 - 2 =\\ 2 * 2^k + k + 1 =\\ 2^{(k + 1)} + (k + 1).[/math]
Do you see where the need for strong induction comes in?
[math]\text {PROVE P(n) such that } a_n = 2^n + n \text { for every positive integer } n, \text {given }[/math]
[math]a_1 = 3, \ a_2 = 6 \text { and } a_n = a_{n-1} + 2a_{n-2} - 2n + 1 \text { for n } \ge 3.[/math]
[math]\text {Step I: } n = 1 \implies a_n = 3 = 2 + 1 = 2^1 + 1 = 2^n + n.\\ n = 2 \implies a_n = 6 = 4 + 2 = 2^2 + 2 = 2^n + n \implies \\ \text {P(n) is true for every positive integer} \le 2.[/math]
[math]\text {STEP II: Thus, there exists a positive integer } k \ge 2\\ \text { such that P(j) is true for every positive integer} \le k.[/math]
[math]k + 1 \text { is an integer} \ge 3 \text { because } k \text { is an integer} \ge 2.[/math]
[math]a_{k+1} = a_{(k+1)-1} + 2a_{(k+1)-2} - 2\{(k + 1) - 2\} + 1 \text { by hypothesis.}[/math]
[math]\therefore a_{k+1} = a_k + 2a_{k-1} - 2(k - 1) + 1 =\\ (2^k + k) + 2\{2^{(k - 1)} + (k - 1)\} - 2k + 2 + 1 =\\ 2^k + k + 2 * 2^{(k-1)} +2k - 2 - 2k + 3 =\\ 2^k + 2^k + 3k - 2k + 3 - 2 =\\ 2 * 2^k + k + 1 =\\ 2^{(k + 1)} + (k + 1).[/math]
Do you see where the need for strong induction comes in?
oh okay,, can you check if my answer is correct or not?
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,081
The main work is good, but some of the details are off. Why do you assume it's true through k, but then leap to k+3?
I think he is talking about (k + 1) + 2. Stopped me for a second as well.
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,081
But this applies the hypothesis to the cases k+1 and k+2, which isn't assumed to be true:
lev888
Elite Member
- Joined
- Jan 16, 2018
- Messages
- 2,939
The first step doesn't make sense. You need to show that the 2 definitions produce the same value for n=1. Don't see it.
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,081
a1 and a2 are defined as 3 and 6 respectively; Leons showed that the formula to be proved gives those values.
lev888
Elite Member
- Joined
- Jan 16, 2018
- Messages
- 2,939
I assumed we had to start with [imath]a_n+_2[/imath], which is [imath]a_3[/imath] for n=1. But, yes, you are right, the first term according to the other formula is [imath]a_1[/imath].