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