Proof By Strong Induction Questions, Answers and Solutions

Answers

Question 1

Question 1

Prove:

Answers

Question 1

a) Answer and Solution are the same for proofs

To prove: $T_n=3^n-2^n$ if $T_{n+2}=5T_{n+1}-6T_n$, $T_1=1$, $T_2=5$ for all $n\ge3$ and $n\in\mathbb{Z}^+$

Call $T_{n+2}=5T_{n+1}-6T_n$, $T_1=1$, $T_2=5$ Statement 1
Call $T_n=3^n-2^n$ Statement 2

Step 1 - Prove true for $T_3$

Statement 1
$T_3=5T_2-6T_1$
$=5\times5-6\times1$
$=25-6$
$=19$

Statement 2
$T_3=3^3-2^3$
$=27-8$
$=19$

Therefore both statements true for $T_3$

Step 2 - Assume true for $T_{k+1}$ and $T_k$

Assume Statement 2 true
$T_k=5T_{k-1}-6T_{k-2}$

So Statement 1 true
$T_k=3^k-2^k$

Again, assume Statement 2 true
$T_{k+1}=5T_{k}-6T_{k-1}$

So Statement 1 true
$T_{k+1}=3^{k+1}-2^{k+1}$

Step 3 - Show true for $T_{k+2}$

Need to show, statement 1: $T_{k+2}=3^{k+2}-2^{k+2}$

Statement 2
$T_{k+2}=5T_{k+1}-6T_k$
$=5(3^{k+1}-2^{k+1})-6(3^k-2^k)$ (from Step 2)
$=5\times3^{k+1}-5\times2^{k+1}-6\times3^k+6\times2^k$
$=5\times3^{k+1}-6\times3^k+6\times2^k-5\times2^{k+1}$
$=5\times3^{k+1}-2\times3\times3^k+3\times2\times2^k-5\times2^{k+1}$
$=5\times3^{k+1}-2\times3^{k+1}+3\times2^{k+1}-5\times2^{k+1}$
$=3\times3^{k+1}-2\times2^{k+1}$
$=3^{k+2}-2^{k+2}$

Therefore it is true for $T_{k+2}$

Step 4 - Conclusion

If true for $T_k$ and $T_{k+1}, then true for $T_{k+2}. As true for $T_3$ it is also true for all $n\ge3$ and $n\in\mathbb{Z}^+$ by mathematical induction.
b) Answer and Solution are the same for proofs

To prove: $T_n=3\times2^{n-1}+2(-1)^n$ if $T_{n}=T_{n-1}+2T_{n-2}$, $T_1=1$, $T_2=8$ for all $n\ge3$ and $n\in\mathbb{Z}^+$

Call $T_{n+2}=T_{n+1}+2T_n$, $T_1=1$, $T_2=8$ Statement 1
Call $T_n=3\times2^{n-1}+2(-1)^n$ Statement 2

Step 1 - Prove true for $T_3$

Statement 1
$T_{3}=T_{2}+2T_1$
$=8+2\times1$
$=10$

Statement 2
$T_3=3\times2^{3-1}+2\times(-1)^3$
$=3\times2^2+2\times-1$
$=12-2$
$=10$

Therefore true for $n=3$

Step 2 - Assume true for $T_{k+1}$ and $T_k$

So Statement 2 true
$T_k=3\times2^{k-1}+2(-1)^k$
$T_{k+1}=3\times2^{k}+2(-1)^{k+1}$

Step 3 - Show true for $T_{k+2}$

Need to show, statement 2: $T_{k+2}=3\times2^{k+1}+2(-1)^{k+2}$

Start with Statement 1
$T_{k+2}=T_{k+1}+2T_k$
$=3\times2^{k}+2(-1)^{k+1}+2\times(3\times2^{k-1}+2(-1)^k)$ (from Step 2)
$=3\times2^k+2(-1)^{k+1}+3\times2^k+2\times2(-1)^k$
$=2\times3\times2^k+[-1\times2(-1)^k+2\times2(-1)^k]$
$=3\times2^{k+1}+[2(-1)^k]$
$=3\times2^{k+1}+2(-1)^k\times1$
$=3\times2^{k+1}+2(-1)^k\times(-1)^2$
$=3\times2^{k+1}+2(-1)^{k+2}$

which was required to prove

Therefore it is true for $T_{k+2}$

Step 4 - Conclusion

If true for $T_k$ and $T_{k+1}$, then true for $T_{k+2}$. As true for $T_3$ it is also true for all $n\ge3$ and $n\in\mathbb{Z}^+$ by mathematical induction.