Induction proofing of a sequence A sequence $a_n$ is defined by:
$a_1=1, a_2 = 1, a_n = a_{n-1} +2*a_{n-2}$ for all n> 2.
show that $a_n = 1/3*(-1)^{n-3}+{2^n}/3$ by induction.
I'm not quite sure on how to approach this induction as I haven't really learnt it yet, but I think you prove its true for n=3 and then work out $a_n$ for n=n+1 but when I've tried i cant find the proof in it.
 A: A not-so-inductive solution, for fun:
$$a_n=a_{n-1}+2a_{n-2}$$ can be rewritten $$a_n+a_{n-1}=2(a_{n-1}+a_{n-2}),$$ which is of the form $$b_n=2b_{n-1}.$$
We recognize a geometric progression of common ratio $2$, and with $b_2=2$,
$$b_n=2^{n-1}.$$
Now let us solve 
$$a_n+a_{n-1}=2^{n-1},$$ or, introducing $c_n=(-1)^{n-1}a_n$,
$$(-1)^{n-1}c_n=-(-1)^{n-2}c_{n-1}+2^{n-1},$$
$$c_n=c_{n-1}+(-2)^{n-1}.$$
We recognize the summation of a geometric progression of common ratio $-2$ and with $c_1=1$ get
$$c_n=\frac{(-2)^n-1}{-2-1},$$
$$a_n=\frac{2^n-(-1)^n}3.$$
A: First, show that this is true for $k=3$:
$a_{3}=a_{2}+2a_{1}=1+2=3=\dfrac{1+8}{3}=\dfrac{(-1)^{3-3}+2^{3}}{3}$
Second, assume that this is true for all ${k}\leq{n}$:
$a_{k}=\dfrac{(-1)^{k-3}+2^{k}}{3}$
Third, prove that this is true for $n+1$:
$a_{n+1}=$
$\color\red{a_{n}}+2\color\green{a_{n-1}}=$
$\color\red{\dfrac{(-1)^{n-3}+2^{n}}{3}}+2\left(\color\green{\dfrac{(-1)^{n-4}+2^{n-1}}{3}}\right)=$
$\dfrac{(-1)^{n-3}+2^n+2(-1)^{n-4}+2^n}{3}=$
$\dfrac{(-1)^{n-3}+2(-1)^{n-4}+2^n+2^n}{3}=$
$\dfrac{(-1)^{n-4}(-1+2)+2^{n+1}}{3}=$
$\dfrac{(-1)^{n-4}+2^{n+1}}{3}=$
$\dfrac{(-1)^{n-2}+2^{n+1}}{3}$

Please note that the assumption is used only in the part marked red and green.
A: First off, you prove that the statement is true for $n=3$. I assume that is simple enough.
Then, you assume that the fact is true for $n$, and you prove that it is then true for $n+1$. Alternatively, and this is much better here, you can assume that it is true for all $k$ such that $k\leq n$, then it is true for $n+1$.
So, your assumptions are now:


*

*As before, you know that for all $k$, you have $a_k = a_{k-1} + 2a_{k-2}$

*You now also know that for all $k\leq n$, you have $a_k = \frac13 (-1)^{k-3} + \frac{2^k}3$.


Now, I advise you to first look at the fact that 
$$a_{n+1} = a_n + 2a_{n-1}$$
Now, replace the value of $a_n$ with $\frac13 (-1)^{n-3} + \frac{2^n}3$ and replace $a_{n-1}$ with $\frac13 (-1)^{(n-1)-3} + \frac{2^{(n-1)}}{3}$
You will get some expression $a_{n+1} = f(n)$, and if you can prove that this expression is equal to $$a_{n+1} = \frac13(-1)^{(n+1)-3} + \frac{2^{n+1}}3$$
you are done.
