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.
- Assuming a limit L exists, let xn+1 = xn = L at the limit.
- Substituting back into the iterative formula, L = sqrt(L) + a
- 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
- 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.
- So 4a + 1 = k2 means k must be odd. So let k = 2b – 1.
- 4a + 1 = (2b – 1)2, so a must take the form b ( b – 1)