Converging Root

Problem

Consider the iterative formula, un+1 = un + 2. By investigating the behaviour it should become clear that all positive starting values converge to the limit 4.

What form must the positive integer, m, take, for the iterative formula, un+1 = un + m, to converge to an integral root?

Solution

We shall assume that the limit, L, exists, such that for sufficiently large values of n, un+1 un, and at limit, un+1 = un = L.

Therefore, L + m = L, L = L m.

Squaring both sides, L = L2 2mL + m2, and L2 (2m+1)L + m2 = 0.

Using the quadratic formula, L = (2m+1)(4m+1)/2.

As 2m+1 is odd and 4m+1 will be an odd square, their sum will be even, so it will always be divisible by 2. That is, the only condition is that 4m+1 is a perfect square.

Writing, 4m+1 = k2, m = (k2 1)/4, it is clear that k must be odd,
let k = 2a 1.

m = ((4a 4a + 1) 1)/4 = a(a 1).

Hence, if m is of the form, a(a 1), the iterative form will converge to an integral root.

The solution, L = (2m+1)(4m+1)/2, suggests that there are two roots of convergence. Prove that the iterative formula will always converge to the upper limit for all positive starting values.

Problem ID: 160 (Mar 2004)     Difficulty: 3 Star

Only Show Problem