Proving the Recursive Formula for an Using Induction

[IntroAnalysis]

Homework Statement

Define an = (a_n-1 + a_n-2)/2 for each positive integer ≥ 2. Use induction to show that: a_n+1 - a_n = (-1/2)ⁿ(a₁ -a₀)

Homework Equations

First show it is true for base case. Assume if it is true for (k), then show it is true for (k + 1).

The Attempt at a Solution

Base case n=1. Then a₂ - a₁ = (-1/2)¹(a₁ - a₀) = (a₀ - a₁)/2
Check: a₂ - a₁ = (a₁ + a₀)/2 - a₁ = (a₁ + a₀ - 2a₁)/2 = (a0 - a1)/2.

So then do I assume that a_k+1 - a_k = (-1/2)^k(a₁ - a₀)? Then what?

 

[lanedance]

so assume it is true for k-1,k as below (note you had the power wrong above)
$$a_k - a_{k-1} = (-1/2)^k(a_1 - a_0)$$

Now using that can you show
$$a_{k+1} - a_{k} = (-1/2)^{k+1}(a_1 - a_0)$$

 

[IntroAnalysis]

No, I did not have the power wrong. This is from Introduction to Analysis, Gaughan, Prob. 23.

It says you may want to use induction to show that:
an+1 - an = (-1/2)^n(a1 - a0).

 

[IntroAnalysis]

Got the induction part:

Assume a_k+1 - a_k = (-1/2^)k(a₁-a₀), then

a_k+2 - a_k+1 = (a_k+1 + a_k)/2 -[(-1/2)^k(a₁ - a₀) + a_k]

= (a_k+1 + a_k - 2a_k)/2 - [(-1/2)^k(a₁ - a₀)]
= (a_k+1 - a_k)/2 - [(-1/2)^k(a₁ - a₀)]
= (1/2)(-1/2)^k(a₁ - a₀) - [(-1/2)^k(a₁ - a₀)]
= -(-1/2)^k+1(a₁ - a₀) - [(-1/2)^k(a₁ - a₀)]
= (-1/2)^k(a₁ - a₀)[1/2 - 1] = (-1/2)^k+1(a₁ - a₀) as desired.

The rest of the proof uses Triangle Inequality Theorem.