Homework Help: Use induction to show that

1. Feb 1, 2012

IntroAnalysis

1. The problem statement, all variables and given/known data
Define an = (an-1 + an-2)/2 for each positive integer ≥ 2. Use induction to show that: an+1 - an = (-1/2)n(a1 -a0)

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

3. The attempt at a solution
Base case n=1. Then a2 - a1 = (-1/2)1(a1 - a0) = (a0 - a1)/2
Check: a2 - a1 = (a1 + a0)/2 - a1 = (a1 + a0 - 2a1)/2 = (a0 - a1)/2.

So then do I assume that ak+1 - ak = (-1/2)k(a1 - a0)? Then what?
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Feb 1, 2012

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

3. Feb 7, 2012

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

4. Feb 7, 2012

IntroAnalysis

Got the induction part:

Assume ak+1 - ak = (-1/2)k(a1-a0), then

ak+2 - ak+1 = (ak+1 + ak)/2 -[(-1/2)k(a1 - a0) + ak]

= (ak+1 + ak - 2ak)/2 - [(-1/2)k(a1 - a0)]
= (ak+1 - ak)/2 - [(-1/2)k(a1 - a0)]
= (1/2)(-1/2)k(a1 - a0) - [(-1/2)k(a1 - a0)]
= -(-1/2)k+1(a1 - a0) - [(-1/2)k(a1 - a0)]
= (-1/2)k(a1 - a0)[1/2 - 1] = (-1/2)k+1(a1 - a0) as desired.

The rest of the proof uses Triangle Inequality Theorem.

Last edited: Feb 7, 2012