Problem:
Consider the sequence of numbers defined recursively by t1=1 and for n>1 by tn=1+t(n/2) when n is even and by tn=1/t(n−1) when n is odd. Given that tn=19/87, the sum of the digits of n is
Answer Choices:
A. 15
B. 17
C. 19
D. 21
E. 23
Solution:
It is easily seen by induction that tk>1 is true for all even k, and that 0<tk<1 is true for all odd k>1. Hence n is odd, and tn−1 is 87/19. Because 87/19>4, it follows that n−1 is divisible by 2 four times and that, subtracting 1 from tn−1 for each division by 2, term number (n−1)/16 is (87/19)−4=11/19. Continuing in this way, we find that term number 16n−1−1=(n−17)/16 is 19/11, term number (n−17)/32 is 8/11, term number (n−49)/32 is 11/8, term number (n−49)/64 is 3/8, term number (n−113)/64 is 8/3, term number (n−113)/256 is 2/3, term number (n−369)/256 is 3/2, term number (n−369)/512 is 1/2, term number (n−881)/512 is 2, and term number (n−881)/1024 is 1. Hence (n−881)/1024 equals 1, so n=1905. The sum of the digits of n is 15.
Note. The given recursion is just a disguised form of the standard representation of a positive rational number in continued fraction form.