IMC 2015 · Day 1 · P3

The characteristic equation of our linear recurrence is $x^2 - \frac{5}{2} x + 1 = 0$, with roots $x_1 = 2$ and $x_2 = \frac{1}{2}$. So $F(n) = a \cdot 2^n + b \cdot \left(\frac{1}{2}\right)^n$ with some constants $a, b$. By $F(0) = 0$ and $F(1) = \frac{3}{2}$, these constants satisfy $a + b = 0$ and $2a + \frac{b}{2} = \frac{3}{2}$. So $a = 1$ and $b = -1$, and therefore $$F(n) = 2^n - 2^{-n}.$$ Observe that $$\frac{1}{F(2^n)} = \frac{2^{2^n}}{(2^{2^n})^2 - 1} = \frac{1}{2^{2^n} - 1} - \frac{1}{(2^{2^n})^2 - 1} = \frac{1}{2^{2^n} - 1} - \frac{1}{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} - \frac{1}{2^{2^{n+1}} - 1} \right) = \frac{1}{2^{2^0} - 1} = 1.$$ Hence the sum takes the value 1, which is rational.

As in the first solution we find that $F(n) = 2^n - 2^{-n}$. Then $$\begin{align*} \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{\left(\frac12\right)^{2^n}} {1 - \left(\frac12\right)^{2^{n+1}}} \\ &= \sum_{n=0}^{\infty} \left(\tfrac12\right)^{2^n} \sum_{k=0}^{\infty} \left( \left(\tfrac12\right)^{2^{n+1}} \right)^k = \sum_{n=0}^{\infty} \left(\tfrac12\right)^{2^n} \sum_{k=0}^{\infty} \left(\tfrac12\right)^{2k \cdot 2^n} \\ &= \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \left(\tfrac12\right)^{2^n (2k+1)} = \sum_{m=1}^{\infty} \left(\tfrac12\right)^{m} = 1. \end{align*}$$ (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.