1. ## induction help

I keep confusing myself when I try and do this.
Let $a_{1}$ and $a_{0}$ be distinct real numbers. Define $a_{n} = \frac{a_{n-1} + a_{n-2}}{2}$ for positive integers $n \geq 2$ . Show $a_{n+1} - a_{n } = (-\frac{1}{2})^{n}(a_{1}- a_{0})$

I show when n =1 is true $a_{2} - a_{1 } = (-\frac{1}{2})^{1}(a_{1}- a_{0})$
=> $a_{2} - a_{1 } = (-\frac{1}{2})}(a_{1}- a_{0})$

Then I must assume n = k is true, and show for n = k+1 is true.
However I keep wanting to reduce into terms of $a_{1}$ and $a_{0}$ and I get mixed up and forget what Im trying to do.

2. ## Re: induction help

Originally Posted by delgeezee
I keep confusing myself when I try and do this.
Let $a_{1}$ and $a_{0}$ be distinct real numbers. Define $a_{n} = \frac{a_{n-1} + a_{n-2}}{2}$ for positive integers $n \geq 2$ . Show $a_{n+1} - a_{n } = (-\frac{1}{2})^{n}(a_{1}- a_{0})$

I show when n =1 is true $a_{2} - a_{1 } = (-\frac{1}{2})^{1}(a_{1}- a_{0})$
=> $a_{2} - a_{1 } = (-\frac{1}{2})}(a_{1}- a_{0})$

Then I must assume n = k is true, and show for n = k+1 is true.
However I keep wanting to reduce into terms of $a_{1}$ and $a_{0}$ and I get mixed up and forget what Im trying to do.
Assume true for n, i.e.

\begin{align*}&a_{n+1}-a_n=\left(-\dfrac 1 2\right)^n (a_1-a_0)\\ \\ &\text{Now show true for }n+1 \\ \\ &a_{n+2}-a_{n+1} = \dfrac 1 2 (a_{n+1} + a_n) - a_{n+1}= \\ \\ &-\dfrac 1 2 (a_{n+1}-a_n)=\\ \\ &-\dfrac 1 2 \left(-\dfrac 1 2\right)^n (a_1-a_0)= \\ \\ &\left(-\dfrac 1 2\right)^{n+1} (a_1-a_0)\end{align*}

and as you showed it true for $n=2$ this completes the proof.

3. ## Re: induction help

You need to show that if n=1, the statement that $a_{1+1}-a_1 = \left(-\dfrac{1}{2}\right)^1(a_1-a_0)$ is true. You are not supposed to show that $n=1$ is true ( $n=1$ is true when you let $n=1$, so there is nothing to show).

Based on the definition:

$a_2 = \dfrac{a_1+a_0}{2}$

Subtracting $a_1$ from both sides gives:

$a_2-a_1 = -\dfrac{1}{2}a_1 + \dfrac{1}{2}a_0 = -\dfrac{1}{2}(a_1-a_0)$

That shows the statement is true when $n=1$. Assume for all positive integers less than or equal to $n$, $a_{n+1}-a_n = \left(-\dfrac{1}{2}\right)^n(a_1-a_0)$.

\begin{align*}a_{(n+1)+1} - a_{n+1} & = \dfrac{a_{n+1}+a_n}{2} - a_{n+1} \\ & = -\dfrac{1}{2}\left(a_{n+1} - a_n\right)\end{align*}

By the induction hypothesis, $a_{n+1}-a_n = \left(-\dfrac{1}{2}\right)^n(a_1-a_0)$. Plugging that in:

$a_{n+2}-a_{n+1} = \left(-\dfrac{1}{2}\right)\left(-\dfrac{1}{2}\right)^n(a_1-a_0) = \left(-\dfrac{1}{2}\right)^{n+1}(a_1-a_0)$

This shows the induction statement is true for $n+1$, as well. (Feel free to add in k and k+1 if you like). This is the general idea of the proof.

4. ## Re: induction help

Hi,
The following is an inductive proof, a little tricky, I admit. If you know about linear recurrence relations, the whole problem is easier to solve without induction.
Edit: Slipeternal's standard inductive proof is much easier, but maybe you want to read this anyway.

5. ## Re: induction help

Thank you for your elaboration. I can see where I was going wrong.