Use induction to show that $a_{n+1}-a_n=\biggl(-\frac{1}{2} \biggr)^n (a_1-a_0) .$

Question

Let $a_0$ and $a_1$ be distinct real numbers. Define $a_n=\frac{a_{n-1}+a_{n-2}}{2}$ for each positive integer $n\geq 2$. Prove that $$a_{n+1}-a_n=\biggl(-\frac{1}{2} \biggr)^n (a_1-a_0) $$

This is what I have so far:

Let $P(n)$ be the statement: For all $n\geq 2$, $n\in\mathbb{N}$, $$ a_{n+1}-a_n=\biggl(-\frac{1}{2} \biggr)^n (a_1-a_0). $$ We must show 1. $P(2)$ holds, 2. For all $k\geq 2$, $k\in\mathbb{N}$, if $P(k)$ holds, then $P(k+1)$ holds. Let $n=2$. Then $$ \begin{aligned} a_{n+1}-a_n &=a_3-a_2\\ &=\frac{a_2+a_1}{2}-\frac{a_1+a_0}{2}\\ &=\frac{a_1+a_0+2a_1}{4}-\frac{a_1+a_0}{2}\\ &=\frac{3a_1+a_0}{4}+\frac{-2a_1-2a_0}{4}\\ &=\frac{a_1-a_0}{4}\\ &=\biggl(-\frac{1}{2}\biggr)^2(a_1-a_0). \end{aligned} $$ Hence, $P(2)$ holds. Suppose that for all $k\geq 2$, $k\in\mathbb{N}$, $P(k)$ holds, that is $$ \begin{aligned} a_{k+1}-a_k &=\frac{a_k+a_{k-1}}{2}-\frac{a_{k-1}+a_{k-2}}{2}\\ &=\biggl(-\frac{1}{2} \biggr)^k (a_1-a_0). \end{aligned} $$ Then $$ \begin{aligned} a_{(k+1)+1}-a_{k+1} &=a_{k+2}-a_{k+1}\\ &=\frac{a_{k+1}+a_k}{2}-\frac{a_k+a_{k-1}}{2}\\ &=\frac{a_k+a_{k-1}+a_{k-1}+a_{k-2}}{4}-\frac{a_{k-1}+a_{k-2}+a_{k-2}+a_{k-3}}{4}\\ &=\biggl(\frac{a_k+a_{k-1}-a_{k-2}-a_{k-3}}{2}\biggr)^2\\ &=\frac{a_{k-1}+a_{k-2}+a_{k-2}+a_{k-3}-a_{k-3}-a_{k-4}-a_{k-4}-a_{k-5}}{8}\\ &=\biggl(\frac{a_{k-1}+2a_{k-2}-2a_{k-4}-a_{k-5}}{2}\biggr)^3 \end{aligned} $$

Ok, so here it seems that I will just end up substituting forever. I'm sure that I'm missing something obvious. Any help would be greatly appreciated. Thanks.

Answer 1

Hint: Subtract $a_{n-1}$ from both sides. We get $$a_n-a_{n-1}=-\frac{1}{2}(a_{n-1}-a_{n-2}).$$ The "new difference" is the "old difference" times $-\frac{1}{2}$.

Answer 2

You should use the induction hypothesis (with two base cases) immediately after your second equality when computing $a_{k + 1} - a_{k + 1}$, for we then have

\begin{align*} \frac{a_{k + 1} + a_k}{2} - \frac{a_k + a_{k - 1}}{2} &= \frac 1 2\left(- \frac 1 2\right)^k (a_1 - a_0) - \frac 1 2\left(-\frac 1 2\right)^{k - 1} (a_1 - a_0) \\ &= (-1)^k \left(\frac{1}{2^{k + 1}} - \frac 1 {2^k}\right) (a_1 - a_0) \\ &= (-1)^k \left(-\frac{1}{2^{k + 1}}\right) (a_1 - a_0) \\ &= \left(-\frac 1 2 \right)^{k + 1} (a_1 - a_0) \end{align*}

as desired.