Induction equation proof

Question

Lets define $a_0=a_1=1$ and every $k$ what is bigger than $1$ and is integer, $$a_k=a_{k-1}+2a_{k-2}.$$ Prove with induction, that every integer that is $k\geq0$ the equation

$$a_k=\dfrac{(2^{k+1}+(-1)^k)}{3}.$$

Answer 1

For $n=0$ the base case we have $a_0=\dfrac{(2^{0+1}+(-1)^0)}{3}=1$. Let us assume the result is true for $n=k$ i.e. $a_k=\dfrac{(2^{k+1}+(-1)^k)}{3}$. We shall prove for $n=k+1$. $a_{k+1}=a_k+2a_{k-1}=\dfrac{(2^{k+1}+(-1)^k+2\cdot(2^k+(-1)^{k-1}))}{3}=\dfrac{(2^{k+2}+(-1)^{k-1}(-1+2))}{3}=\dfrac{(2^{k+2}+(-1)^{k-1}(-1)^2)}{3}=\dfrac{(2^{k+2}+(-1)^{k+1})}{3}$.

Hence by principle of mathematical induction the result is true for all $n$.

Answer 2

Try the following theorem:

If $x_1$ and $x_2$ are solutions of $x^2-pt-q=0$, then $a_k=c_1x_1^k+c_2x_2^k$ is solution of the recurrence $a_k-pa_{n-1}-qa_{k-2}=0$.

After this, you can try $k=0,1$ in the geral solution to obtain a particluar answer, your answer.

Answer 3

The characteristics equation helps us here which is: $$x^2=x+2$$and has two roots $$x_1=2\\x_2=-1$$therefore$$a_n=a2^n+b(-1)^n$$ by substituting the initial conditions we obtain what we want