Halve the error at every step

\{u_n\}

[2011/TJC/Promo/14]

Total marks: 12

Solution

(a)(i)

Limit

$u_{n+1}=\frac12u_n+1$ . Given that it converges to $l$ , find $l$ .

Explore this idea

Hint

Replace both $u_n$ and $u_{n+1}$ by $l$ .

Answer · (a)(i)

l=2

Explore the idea

The line meets the diagonal at 2

Start at the chosen value on the horizontal axis, go up to the curve, across to the diagonal, and repeat. Each corner of the web is the next term.

Starting valueu₁ = 0

Iterations drawn4

Try an example

u(n = 5)

1.875

u(n = 1)

Distance to l = 2

0.125

Key idea

A line with slope $\frac12$ meets the diagonal once, at $2$ , and pulls both sides toward it.

Ideas to try

Start below

2

and above

2

in turn. Both webs head to the same point.

(a)(ii)

Invariant interval

If $u_n<l$ , show that $u_n<u_{n+1}<l$ .

Explore this idea

Hint

Show $u_{n+1}-u_n>0$ .
Show $u_{n+1}-2<0$ .

Answer · (a)(ii)

u_{n+1}-u_n=(2-u_n)/2>0

Explore the idea

The web never crosses the fixed point

Open the increment plot to see why the step is positive below $2$ and zero at $2$ .

Starting valueu₁ = 1

Iterations drawn4

Try an example

u(n = 5)

1.9375

u(n = 1)

Distance to l = 2

0.0625

Key idea

The map is increasing and fixes $2$ , so it maps $(-\infty,2)$ into itself; the positive increment then makes terms climb.

Ideas to try

In the terms plot, all points stay under the guide at $2$ and rise.
In the increment plot, the dot is above the axis for every start below $2$ .

(a)(iii)

Describe the sequence

If $u_1<l$ , describe the behaviour of the sequence.

Explore this idea

Hint

Combine monotonic and bounded.

Answer · (a)(iii)

2

Explore the idea

Increasing and bounded

Drag the slider to change n and compare the plotted values.

Indexn = 3

Try an example

term uₙ (u₁ = 0) at n = 3

1.5

Key idea

Increasing and bounded above is enough to guarantee a limit; the fixed point then identifies it.

Ideas to try

The gap to

2

halves each step: read the value at

n=4

, then at

n=5

(b)(i)

Show a GP

$v_n=u_n-2$ . Show that $\{v_n\}$ is a geometric progression.

Explore this idea

Hint

Express $v_{n+1}$ in terms of $v_n$ without dividing.

Answer · (b)(i)

v_{n+1}=v_n/2

Explore the idea

The shifted sequence halves each time

For $u_1=3$ , the terms $u_n$ and the shifted terms $v_n=u_n-2$ are the same curve moved down by $2$ .

Indexn = 2

Try an example

term uₙ at n = 2

2.5

shifted vₙ = uₙ − 2 at n = 2

0.5

Key idea

Shifting by the fixed point removes the constant, leaving a pure multiplier.

Ideas to try

Compare

v_n

n=2

and

n=3

: the second is half the first.

(b)(ii)

Closed form

If $u_1=3$ , show that $u_n=2+\left(\frac12\right)^{n-1}$ .

Explore this idea

Hint

Find $v_1$ , use the GP formula, then add $2$ back.

Answer · (b)(ii)

u_n=2+(1/2)^{n-1}

Explore the idea

From above

Start at the chosen value on the horizontal axis, go up to the curve, across to the diagonal, and repeat. Each corner of the web is the next term.

Starting valueu₁ = 3

Iterations drawn4

Try an example

u(n = 5)

2.0625

u(n = 1)

Distance to l = 2

0.0625

Key idea

Above $2$ the terms fall and are still bounded below by $2$ ; below $2$ they rise. The gap is halved either way.

Ideas to try

From

u_1=3

the terms are

3,\ 2.5,\ 2.25,\ 2.125

. Each is

2

plus a halving gap.

Takeaway

Measure from the fixed point

Replacing $u_n$ by its distance from the fixed point turns an affine recurrence into a pure multiplier.

Halve the error at every step

Solution

Limit

Solve the fixed-point equation

The line meets the diagonal at 2

Invariant interval

The terms increase

The terms stay below 2

The web never crosses the fixed point

Describe the sequence

Combine

State the limit

Increasing and bounded

Show a GP

Compute $v_{n+1}$

Conclude

The shifted sequence halves each time

Closed form

First term of $v$

GP formula

Undo the shift

From above

Measure from the fixed point

Solve the fixed-point equation

The terms increase

The terms stay below 2

Combine

State the limit

Compute vn+1v_{n+1}vn+1​

Conclude

First term of vvv

GP formula

Undo the shift

Measure from the fixed point

Compute $v_{n+1}$

First term of $v$