The sequence u_{n} is defined by u_{0} = 1, u_{2n} = u_{n} + u_{n-1}, u_{2n+1} = u_{n}. Show that for any positive rational k we can find n such that u_{n}/u_{n+1} = k.

**Solution**

Let S_{m} be the statement that for any positive rational k = r/s with max(r, s) = m, we can find n such that u_{n}/u_{n+1} = k. We use induction on m. The result is obviously true for m = 1 (if m = 1, then k must be 1/1 and we can take n = 0). So suppose the result is true for m < N. We now have to consider k = N/s with s < N and k = s/N with s < N.

If k = N/s, then k > 1 and k - 1 = (N-s)/s. But max(N-s, s) < N, so k - 1 = u_{n}/u_{n+1} for some n. Hence k = (u_{n} + u_{n+1})/u_{n+1} = u_{2n+2}/u_{2n+3}.

If k = s/N, then k < 1 and k/(1-k) = s/(N-s). But max(s, N-s) < N, so k/(1-k) = u_{n}/u_{n+1} for some n. Hence k = u_{n}/(u_{n+1} + u_{n}) = u_{2n+1}/u_{2n+2}.

Thus the result is also true for m = N and hence for all m.

© John Scholes

jscholes@kalva.demon.co.uk

11 Dec 2002