Induction proofing of a sequence

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.$$