International Mathematics Competition for University Students

July 27 - Aug 2 2015, Blagoevgrad, Bulgaria

Home

Day 1
    Problem 1
    Problem 2
    Problem 3
    Problem 4
    Problem 5

Day 2
    Problem 6
    Problem 7
    Problem 8
    Problem 9
    Problem 10

Results
    Individuals
    Teams

Download
    Day 1 questions
    Day 1 solutions
    Day 2 questions
    Day 2 solutions

Official IMC site

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$.