International Mathematics Competition
for University Students
2015

IMC2015: Day 1, Problem 3

3. Let $F(0)=0$, $F(1)=\frac32$, and $F(n)=\frac{5}{2}F(n-1)-F(n-2)$ for $n\ge2$.

Determine whether or not $\displaystyle{\sum_{n=0}^{\infty}\, \frac{1}{F(2^n)}}$ is a rational number.

Proposed by Gerhard Woeginger, Eindhoven University of Technology

Solution 1. The characteristic equation of our linear recurrence is $x^2-\tfrac52x+1=0$, with roots $x_1=2$ and $x_2=\tfrac12$. So $F(n)=a\cdot 2^n +b\cdot (\tfrac12)^n$ with some constants $a,b$. By $F(0)=0$ and $F(1)=\tfrac32$, these constants satisfy $a+b=0$ and $2a+\tfrac{b}{2}=\tfrac32$. So $a=1$ and $b=-1$, and therefore $$ F(n) = 2^n - 2^{-n}. $$

Observe that $$ \frac1{F(2^n)} = \frac{2^{2^n}}{(2^{2^n})^2-1} = \frac{1}{2^{2^n}-1} - \frac1{(2^{2^n})^2-1} = \frac{1}{2^{2^n}-1} - \frac1{2^{2^{n+1}}-1}, $$ so \[ \sum_{n=0}^{\infty}\, \frac{1}{F(2^n)} = \sum_{n=0}^{\infty}\, \left( \frac{1}{2^{2^n}-1} - \frac1{2^{2^{n+1}}-1} \right) = \frac1{2^{2^0}-1} = 1. \] Hence the sum takes the value~$1$, which is rational.

Solution 2. As in the first solution we find that $F(n)=2^n-2^{-n}$. Then \[ \sum_{n=0}^{\infty}\, \frac{1}{F(2^n)} = \sum_{n=0}^{\infty}\, \frac{1}{2^{2^n}-2^{-2^n}} ~=~ \sum_{n=0}^{\infty}\, \frac{(\tfrac12)^{2^{n}}}{1-(\tfrac12)^{2^{n+1}}} \] \[ = \sum_{n=0}^{\infty}\, (\tfrac12)^{2^{n}} \sum_{k=0}^{\infty} \left((\tfrac12)^{2^{n+1}}\right)^k ~=~ \sum_{n=0}^{\infty}\, (\tfrac12)^{2^{n}} \sum_{k=0}^{\infty} (\tfrac12)^{2k\cdot 2^n} \] \[ = \sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\, (\tfrac12)^{2^{n}(2k+1)} ~=~ \sum_{m=1}^{\infty}\, (\tfrac12)^m ~=~ 1. \] (Here we used the fact that every positive integer $m$ has a unique representation $m=2^{n}(2k+1)$ with non-negative integers $n$ and $k$.)

This shows that the series converges to $1$.