The sequence un is defined by u0 = 1, u2n = un + un-1, u2n+1 = un. Show that for any positive rational k we can find n such that un/un+1 = k.
Solution
Let Sm be the statement that for any positive rational k = r/s with max(r, s) = m, we can find n such that un/un+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 = un/un+1 for some n. Hence k = (un + un+1)/un+1 = u2n+2/u2n+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) = un/un+1 for some n. Hence k = un/(un+1 + un) = u2n+1/u2n+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