uniolympiads Ελληνικά

IMC 2015, Day 1, Problem 3

Let F(0)=0F(0) = 0, F(1)=32F(1) = \frac{3}{2}, and F(n)=52F(n−1)−F(n−2)F(n) = \frac{5}{2}F(n-1) - F(n-2) for n≥2n \ge 2.

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

Original from the official PDF3 5 Let F (0) = 0 , F (1) = 2 , and F (n) = 2 F (n − 1) − F (n − 2) for n ≥ 2 . Determine whether or not ∞ X 1 is a rational number. F (2 n ) n=0

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Gerhard Woeginger, Eindhoven University of Technology)

Solution 1. The characteristic equation of our linear recurrence is x2−52x+1=0x^2-\frac{5}{2}x+1 = 0, with roots x1=2x_1 = 2 and x2=12x_2 = \frac{1}{2}. So F(n)=a⋅2n+b⋅(12)nF(n) = a\cdot 2^n + b\cdot(\frac{1}{2})^n with some constants a,ba,b. By F(0)=0F(0) = 0 and F(1)=32F(1) = \frac{3}{2}, these constants satisfy a+b=0a+b = 0 and 2a+b2=322a+\frac{b}{2} = \frac{3}{2}. So a=1a = 1 and b=−1b = -1, and therefore

F(n)=2n−2−n.F(n) = 2^n - 2^{-n}.

Observe that

1F(2n)=22n(22n)2−1=122n−1−1(22n)2−1=122n−1−122n+1−1,\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
∑n=0∞1F(2n)=∑n=0∞(122n−1−122n+1−1)=1220−1=1.\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.

Solution 2. As in the first solution we find that F(n)=2n−2−nF(n) = 2^n-2^{-n}. Then

∑n=0∞1F(2n)=∑n=0∞122n−2−2n=∑n=0∞(12)2n1−(12)2n+1=∑n=0∞(12)2n∑k=0∞((12)2n+1)k=∑n=0∞(12)2n∑k=0∞(12)2k⋅2n=∑n=0∞∑k=0∞(12)2n(2k+1)=∑m=1∞(12)m=1.\begin{aligned} \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{(\frac{1}{2})^{2^n}}{1-(\frac{1}{2})^{2^{n+1}}} \\ &= \sum_{n=0}^{\infty}(\tfrac{1}{2})^{2^n}\sum_{k=0}^{\infty}\left((\tfrac{1}{2})^{2^{n+1}}\right)^k = \sum_{n=0}^{\infty}(\tfrac{1}{2})^{2^n}\sum_{k=0}^{\infty}(\tfrac{1}{2})^{2k\cdot 2^n} \\ &= \sum_{n=0}^{\infty}\sum_{k=0}^{\infty}(\tfrac{1}{2})^{2^n(2k+1)} = \sum_{m=1}^{\infty}(\tfrac{1}{2})^m = 1. \end{aligned}
(Here we used the fact that every positive integer mm has a unique representation m=2n(2k+1)m = 2^n(2k+1) with non-negative integers nn and kk.)

This shows that the series converges to 1.

Transcribed from the official solutions, page 3. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?