problem understanding induction proof for following recurrence sequence $\frac{a_{n-1}+a_{n-2}}{2}$

I've got this recurrence sequence and it's proof, but I'm stuck with the 2nd/3rd step in the induction step.

$$a_0:=0, a_1:=1\\ a_n:= \frac{a_{n-1}+a_{n-2}}{2}$$

Show that for all $n\in N$: $a_n-a_{n-1}=(-\frac{1}{2})^{n-1}$
Induction start: $n=1$ and $n=2$
$$a_1-a_0=1=(-1/2)^0\\ a_2-a_1= 1/2-1=-(1/2)^1$$ Induction step: $n \rightarrow n+1$ $$a_{n+1}-a_n = \frac{a_n+a_{n-1}-\overbrace{ (a_{n-1}+a_{n-2})}^{a_n}}{2}\\ =\frac{(-1/2)^{n-1}+(-1/2)^{n-2}}{2}\\ =\frac{ (-1)^{n-2} }{2}*\left(\frac{-1}{2^{n-1}}+\frac{1}{2^{n-2}}\right)\\ = \frac{(-1)^n}{2}*\left(\frac{-1}{2^{n-1}}+\frac{2}{2^{n-1}}\right)\\ = \left(-\frac{1}{2}\right)^n$$

I am stuck with the 2nd/3rd transforamtion in the induction step. The sencond one, marked with the overbrace is clear to me, that is simply the Induction premise and the first part of the term is simply the formula for $a_{n+1}$. But I don't really get the next step, the $(-1/2)^{n-2}$, why can I use this? Could someone explain the step in more detail?

I found this as related, but it's different from mine. Proof by induction that if $a_0 = 0, a_1 = 1, a_n = \frac{a_{n-1} + a_{n-2}}{2}$ then $a_n = \frac23 \left( 1 + \frac{(-1)^{n+1}}{2^n} \right)$

• are you allowed to use generating functions instead?
– Alex
Mar 12, 2015 at 15:07
• Actually the $=(-\frac12)^{n-1}$-step is the induction premise. The other step is just the definition of $a_n$. Mar 12, 2015 at 15:07
• There's a tiny bit of algebra missing between the overbrace and the first line with the $\frac12$s: you have $a_n+a_{n-1}-(a_{n-1}+a_{n-2})=a_n+a_{n-1}-a_{n-1}-a_{n-2}=(a_n-a_{n-1})+(a_{n-1}-a_{n-2})$. Now use your induction premise twice, once for $n$ and once for $n-1$. Does that make more sense? Mar 12, 2015 at 15:08
• @ChristophS Are you aware of "strong induction"? It's the induction premise from two steps backward so to say. Mar 12, 2015 at 15:10
• @ChristophS Correct. Mar 12, 2015 at 16:19

1 Answer

The key is that this is a mild form of strong induction, where to prove the principle $P(n+1)$ you don't just assume that $P(n)$ is true, but can also use $P(k)$ for all $k\leq n$. In this case, we use both $P(n)$ and $P(n-1)$:

$a_{n+1}-a_n$ $=\dfrac{a_n+a_{n-1}}{2}-\dfrac{a_{n-1}+a_{n-2}}{2}$ (by using the definitions of $a_{n+1}$ and $a_n$)

$=\frac12\left(a_n+a_{n-1}-(a_{n-1}+a_{n-2})\right)$ (by algebra)

$=\frac12\left((a_n-a_{n-1})+(a_{n-1}-a_{n-2})\right)$ (also by algebra)

$= \frac12\left(\left(-\frac12\right)^n+(a_{n-1}-a_{n-2})\right)$ (by using $P(n)$ to replace $a_n-a_{n-1}$ with $\left(-\frac12\right)^n$)

$=\frac12\left(\left(-\frac12\right)^n+\left(-\frac12\right)^{n-1}\right)$ (by using $P(n-1)$ to replace $a_{n-1}-a_{n-2}$ with $\left(-\frac12\right)^{n-1}$)

And then from there the rest of it is just more algebra.

• Ah, thanks! I think I understand it now, it's because in the premise I showed it for two indices, n=1 and n=2. Mar 12, 2015 at 16:19