# Induction proof on a sequence A sequence a 0 </msub> , a 1 </

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!
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

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.