uniolympiads English

IMC 2015, Ημέρα 1, Θέμα 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.

Πρωτότυπο από το επίσημο 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

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;