Categories

# Converge to an Integer

Given the iterative formula:

xn+1 = sqrt(xn) + a

There are some values of a for which a positive starting value for x results in this formula converging to an integer.

For example, if a = 2, you would observe that xn+1 = sqrt(xn) + 2 eventually converges to 4 for any positive starting value.

What form must a take in order for this formula to converge to an integer?

#### Solution

a must be in the form b (b – 1) where b is an integer.

1. Assuming a limit L exists, let xn+1 = xn = L at the limit.
2. Substituting back into the iterative formula, L = sqrt(L) + a
3. To solve for L, evaluate to:
• sqrt(L) = L – a
• L = L2 – 2aL + a2
• L2 – (2a + 1) L + a2
• L = ((2a + 1) +/– sqrt(4a + 1)) / 2
4. For L to be an integer, 4a + 1 has to be a perfect square
• Note: division by 2 is not an issue, because 2a + 1 is odd and sqrt(4a + 1) is odd whenever it is an integer, so their sum will always be even.
5. So 4a + 1 = k2 means k must be odd. So let k = 2b – 1.
6. 4a + 1 = (2b – 1)2, so a must take the form b ( b – 1)