daktielti

2022-07-01

Induction proof on a sequence
A sequence ${a}_{0},{a}_{1},\dots$ is defined by letting ${a}_{0}={a}_{1}=1$ and ${a}_{k}={a}_{k-1}+2{a}_{k-2}$ for all integers $k>1$. Prove that for all integers $k\ge 0$, ${a}_{k}=\frac{{2}^{k+1}+\left(-1{\right)}^{k}}{3}$.
Base case: S(2)
Let $k=2$. Then ${a}_{2}=\frac{{2}^{2+1}+\left(-1{\right)}^{2}}{3}=\frac{9}{3}=3$.
S(3)
Let $k=3$. Then ${a}_{3}=\frac{{2}^{3+1}+\left(-1{\right)}^{3}}{3}=\frac{15}{3}=5$
Base is true.
Induction step: Assume S(k) and $S\left(k-1\right)$ are true. Then
$S\left(k\right)={a}_{k}=\frac{{2}^{k+1}+\left(-1{\right)}^{k}}{3}$
and $S\left(k-1\right)={a}_{k+1}=\frac{{2}^{k}+\left(-1{\right)}^{k-1}}{3}$
Since $S\left(k\right)={a}_{k}$ and $S\left(k-1\right)={a}_{k-1}$, by definition $S\left(k+1\right)=S\left(k\right)+2\cdot S\left(k-1\right)$.
$\frac{{2}^{k+2}+\left(-1{\right)}^{k+1}}{3}=\frac{{2}^{k+1}+\left(-1{\right)}^{k}}{3}+2\cdot \frac{{2}^{k}+\left(-1{\right)}^{k-1}}{3}$
Solving this should lead to that
$k=-2$
Therefore $S\left(k+1\right)$ is true.
I think I've got the right idea but I'm not completely sure that I've done this correctly. Any help or suggestions are much appreciated!

Freddy Doyle

Step 1
S(k) must have a truth value. In this case it's the statement ${a}_{k}=\frac{{2}^{k+1}+\left(-1{\right)}^{k}}{3}$. So you shouldn't write $S\left(k+1\right)=S\left(k\right)+2S\left(k-1\right)$ because that's adding statements!
Step 2
The question asks to show S(k) for $k\ge 0$. So your base case must include $k=0$. (Note that here I've abbreviated "S(k) is true" to "S(k)" – in the same way that I can abbreivate "it's true that it's raining" to "it's raining". But feel free to say "S(k) is true" for clarity.)
Step 3
The aim for the induction part is to (as I think you know) assume $S\left(k-1\right)$ and S(k), and then show $S\left(k+1\right)$. The aim is then to do something like
$\begin{array}{rcll}{a}_{k+1}& =& {a}_{k}+2{a}_{k-1}& \text{(by definition)}\\ & =& \frac{{2}^{k+1}+\left(-1{\right)}^{k}}{3}+\frac{{2}^{k}+\left(-1{\right)}^{k-1}}{3}& \text{(by inductive hypothesis)}\\ & =& \dots & \text{(some steps for you to work out)}\\ & =& \frac{{2}^{k+2}+\left(-1{\right)}^{\left(k+1\right)}}{3}\end{array}$
i.e. $S\left(k+1\right)$. In your proof you seemed to begin with assuming $S\left(k+1\right)$, which is incorrect.

Do you have a similar question?