Proof By Induction Recurrance Questions, Answers and Solutions
a - answer s - solution v - video
Question 1
Prove:
a) $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
a
Answer and Solution are the same for proofs
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
s
Answer and Solution are the same for proofs
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
v
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question ID: 10050050010
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
b) $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
a
Answer and Solution are the same for proofs
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
s
Answer and Solution are the same for proofs
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
v
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question ID: 10050050020
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
c) $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
a
Answer and Solution are the same for proofs
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
s
Answer and Solution are the same for proofs
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
v
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question ID: 10050050025
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
d) $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
a
Answer and Solution are the same for proofs
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
s
Answer and Solution are the same for proofs
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
v
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question ID: 10050050030
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
e) $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
a
Answer and Solution are the same for proofs
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
s
Answer and Solution are the same for proofs
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
v
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question ID: 10050050050
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question 2
Prove
a) A term in the Fibonacci Sequence can be calculated by the formula $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
a
Answer and Solution are the same for proofs
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
s
Answer and Solution are the same for proofs
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
v
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question ID: 10050050060
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
Something wrong? Copy Question ID and contact us
Submit yours! Copy Question ID and click here
Question by: ada
Answer by: ada
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question 1
Prove:
a) $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
b) $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
c) $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
d) $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
e) $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Question 2
Prove
a) A term in the Fibonacci Sequence can be calculated by the formula $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Answers
Question 1
a) Answer and Solution are the same for proofs
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
b) Answer and Solution are the same for proofs
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
c) Answer and Solution are the same for proofs
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
d) Answer and Solution are the same for proofs
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
e) Answer and Solution are the same for proofs
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question 2
a) Answer and Solution are the same for proofs
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question 1
Prove:
a) $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
b) $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
c) $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
d) $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
e) $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Question 2
Prove
a) A term in the Fibonacci Sequence can be calculated by the formula $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Answers
Question 1
a) Answer and Solution are the same for proofs
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
b) Answer and Solution are the same for proofs
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
c) Answer and Solution are the same for proofs
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
d) Answer and Solution are the same for proofs
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
e) Answer and Solution are the same for proofs
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question 2
a) Answer and Solution are the same for proofs
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Solutions
Question 1
a) Answer and Solution are the same for proofs
To prove: $T_n=3^n-2$ if $T_{n+1}=3T_n+4$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=3T_n+4$, $T_1=1$ Statement 1
Call $T_n=3^n-2$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=3T_1+4$
$=3\times1+4$
$=7$
Statement 2
$T_2=3^2-2$
$=9-2$
$=7$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=3^k-2$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=3^{k+1}-2$
Statement 1
$T_{k+1}=3T_k+4$
$=3(3^k-2)+4$ (from Step 2)
$=3\times3^k-6+4$
$=3^{k+1}-2$
Which shows that $T_{k+1}=3^{k+1}-2$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=3^k-2$, then $T_{k+1}=3^{k+1}-2$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
b) Answer and Solution are the same for proofs
To prove: $T_n=2^n-1$ if $T_n=2T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=2T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=2^n-1$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=2T_0+1$
$=2\times0+1$
$=1$
Statement 2
$T_1=2^1-1$
$=2-1$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2^k-1$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2^{k+1}-1$
Statement 1
$T_{k+1}=2T_k+1$
$=2(2^k-1)+1$ (from Step 2)
$=2\times2^k-2+1$
$=2^{k+1}-1$
Which shows that $T_{k+1}=2^{k+1}-1$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=2^k-1$, then $T_{k+1}=2^{k+1}-1$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
c) Answer and Solution are the same for proofs
To prove: $T_n=2\times5^{n-1}$ if $T_{n+1}=5T_n$, $T_1=2$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=5T_n$, $T_1=2$ Statement 1
Call $T_n=2\times5^{n-1}$ Statement 2
Step 1 - Prove true for $T_2$
Statement 1
$T_2=5T_1$
$=10$
Statement 2
$T_2=2\times5^{2-1}$
$=2\times5$
$=10$
Therefore both statements true for $T_2$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=2\times5^{k-1}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=2\times5^k$
Statement 1
$T_{k+1}=5T_k$
$=5(2\times5^{k-1})$ (from Step 2)
$=2\times5\times5^{k-1}$
$=2\times5^k$
Which shows that $T_{k+1}=2\times5^k$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ then true for $n=k+1$. As true for $T_2$ when $n=1$, it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
d) Answer and Solution are the same for proofs
To prove: $T_n=\frac{5^n-1}{4}$ if $T_n=5T_{n-1}+1$, $T_0=0$ for all $n\ge0$ and $n\in\mathbb{Z}^+$
Call $T_n=5T_{n-1}+1$, $T_0=0$ Statement 1
Call $T_n=\frac{5^n-1}{4}$ Statement 2
Step 1 - Prove true for $T_1$
Statement 1
$T_1=5T_0+1$
$=5\times0+1$
$=1$
Statement 2
$T_1=\frac{5^1-1}{4}$
$=\frac44$
$=1$
Therefore both statements true for $T_1$
Step 2 - Assume true for $n=k$
Statement 2
$T_k=\frac{5^k-1}{4}$
Step 3 - Show true for $n=k+1$
Need to show, statement 2: $T_{k+1}=\frac{5^{k+1}-1}{4}$
Statement 1
$T_{k+1}=5T_k+1$
$=5(\frac{5^k-1}{4})+1$ (from Step 2)
$=\frac{5\times(5^k-1)}{4}+1$
$=\frac{5\times5^k-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+1$
$=\frac{5^{k+1}-5}{4}+\frac44$
$=\frac{5^{k+1}-5+4}{4}$
$=\frac{5^{k+1}-1}{4}$
Which shows that $T_{k+1}=\frac{5^{k+1}-1}{4}$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If $T_k=\frac{5^k-1}{4}$, then $T_{k+1}=\frac{5^{k+1}-1}{4}$. As true for $T_1$ when $n=0$, it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.
e) Answer and Solution are the same for proofs
To prove: $T_n<4$ if $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ for all $n\ge1$ and $n\in\mathbb{Z}^+$
Call $T_{n+1}=\sqrt{1+2T_n}$, $T_1=1$ Statement 1
Call $T_n<4$ Statement 2
Step 1 - Prove true for $n=1$
Statement 1
$T_2=\sqrt{1+2T_1}$
$=\sqrt{1+2\times1}$
$=\sqrt3$
$<4$
Therefore true when $n=1$
Step 2 - Assume true
So, $T_k<4$
Step 3 - Show true for $n=k+1$
Need to show when $T_{k+1}=\sqrt{1+2T_k}$ $T_{k+1}<4$
Statement 1
$T_{k+1}=\sqrt{1+2T_k}$
$<\sqrt{1+2\times4}$ (from Step 2)
$=\sqrt9$
$=3$
$<4$
Which shows that $T_{k+1}<4$
Step 4 - Conclusion
It is true that $T_{k+1}<4$, when $T_k$ holds. As true for $T_1$ and $T_2$ it is also true for all $n\ge1$ and $n\in\mathbb{Z}^+$ by mathematical induction.
Question 2
a) Answer and Solution are the same for proofs
To prove: $T_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{n+1}-\left(\frac{1-\sqrt5}{2}\right)^{n+1}\right]$ where $T_0=1$, $T_1=1$, $T_2=2$, $T_3=3$, $T_4=5$, etc.
Step 1 - Prove true for $T_0$ and $T_1$
$T_0=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{0+1}-\left(\frac{1-\sqrt5}{2}\right)^{0+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{2\sqrt5}{2}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
$T_1=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{1+1}-\left(\frac{1-\sqrt5}{2}\right)^{1+1}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{6+2\sqrt5}{4}-\frac{6-2\sqrt5}{4}\right]$
$=\frac{1}{\sqrt{5}}\left[\frac{4\sqrt5}{4}\right]$
$=\frac{1}{\sqrt5}\times\sqrt5$
$=1$
Step 2 - Assume true for $n=k$ and $n=k-1$
$T_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]$
$T_{k-1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
Step 3 - Show true for $n=k+1$
Need to show, $T_{k+1}=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
$T_{k+1}=T_k+T_{k-1}$ (by definition of the Fibonacci Sequence)
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{1+\sqrt5}{2}\right)^{k}-\left(\frac{1-\sqrt5}{2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+1}-\left(\frac{1-\sqrt5}{2}\right)^{k+1}+\left(\frac{2(1+\sqrt5)}{2\times2}\right)^{k}-\left(\frac{2(1-\sqrt5)}{2\times2}\right)^{k}\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}+(2(1+\sqrt5))^{k}-(2(1-\sqrt5)^{k}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(1+\sqrt5+2)-(1-\sqrt5)^{k}(1-\sqrt5+2)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}(3+\sqrt5)-(1-\sqrt5)^{k}(3-\sqrt5)\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+1}\left[(1+\sqrt5)^{k}\frac{(1+\sqrt5)^2}{2}-(1-\sqrt5)^{k}\frac{(1-\sqrt5)^2}{2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac12\right)^{k+2}\left[(1+\sqrt5)^{k+2}-(1-\sqrt5)^{k+2}\right]\right]$
$=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt5}{2}\right)^{k+2}-\left(\frac{1-\sqrt5}{2}\right)^{k+2}\right]$
Therefore it is true for $n=k+1$
Step 4 - Conclusion
If true for $n=k$ and $n=k-1$ then true for $n=k+1$. As true for $T_0$ and $T_1$ it is also true for all $n\ge0$ and $n\in\mathbb{Z}^+$ by mathematical induction.