uniolympiads English

IMC 2024, Ημέρα 2, Θέμα 8

Define the sequence x1,x2,…x_1, x_2, \dots by the initial terms x1=2x_1 = 2, x2=4x_2 = 4, and the recurrence relation

xn+2=3xn+1−2xn+2nxnfor n≥1.x_{n+2} = 3x_{n+1} - 2x_n + \frac{2^n}{x_n} \quad \text{for } n \ge 1.

Prove that lim⁡n→∞xn2n\lim_{n \to \infty} \frac{x_n}{2^n} exists and satisfies

1+32≤lim⁡n→∞xn2n≤32.\frac{1 + \sqrt{3}}{2} \le \lim_{n \to \infty} \frac{x_n}{2^n} \le \frac{3}{2}.
Πρωτότυπο από το επίσημο PDFDefine the sequence x 1 , x 2 , . . . by the initial terms x 1 = 2, x 2 = 4, and the recurrence relation 2 n for n ≥ 1. x n+2 = 3x n+1 − 2x n + x n x n Prove that lim n exists and satisfies n→∞ 2 √ x n 3 1+ 3 ≤ lim n ≤ . n→∞ 2 2 2

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

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

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

Επίσημη λύση

(proposed by Karen Keryan, Yerevan State University & American University of Armenia, Armenia)

Hint: Prove that 2xn≤xn+1≤2xn+n2x_n \le x_{n+1} \le 2x_n + n.

Solution. Let's prove by induction that xn+1≥2xnx_{n+1} \ge 2x_n. It holds for n=1n = 1. Assume it holds for nn. Then by the induction hypothesis we have that xn≥2xn−1≥⋯≥2n−1x1>0x_n \ge 2x_{n-1} \ge \dots \ge 2^{n-1}x_1 > 0 and

xn+2=2xn+1+(xn+1−2xn)+2nxn>2xn+1.x_{n+2} = 2x_{n+1} + (x_{n+1} - 2x_n) + \frac{2^n}{x_n} > 2x_{n+1}.

Similarly we prove that xn+1≤2xn+nx_{n+1} \le 2x_n + n. Again it holds for n=1n = 1. Assume that the inequality holds for nn. Then using that xn≥2nx_n \ge 2^n and the induction hypothesis we obtain

xn+2≤3xn+1−2xn+1≤2xn+1+(2xn+n)−2xn+1=2xn+1+n+1.x_{n+2} \le 3x_{n+1} - 2x_n + 1 \le 2x_{n+1} + (2x_n + n) - 2x_n + 1 = 2x_{n+1} + n + 1.

Using the previous inequalities we obtain that the sequence yn=xn2ny_n = \dfrac{x_n}{2^n} is increasing and yn+1≤yn+n2n≤⋯≤y1+∑k=1nk2k<∞y_{n+1} \le y_n + \frac{n}{2^n} \le \dots \le y_1 + \sum_{k=1}^{n}\frac{k}{2^k} < \infty, thus lim⁡n→∞yn=xn2n=c\lim\limits_{n\to\infty} y_n = \dfrac{x_n}{2^n} = c exists.

The recurrence relation has the following form for yny_n:

4yn+2−2yn+1=4yn+1−2yn+12n⋅yn.4y_{n+2} - 2y_{n+1} = 4y_{n+1} - 2y_n + \frac{1}{2^n \cdot y_n}.

By summing up the above equality for n=1,…,mn = 1, \dots, m we obtain

4ym+2−2ym+1=4y2−2y1+∑n=1m12n⋅yn=2+∑n=1m12n⋅yn.(1)4y_{m+2} - 2y_{m+1} = 4y_2 - 2y_1 + \sum_{n=1}^{m}\frac{1}{2^n \cdot y_n} = 2 + \sum_{n=1}^{m}\frac{1}{2^n \cdot y_n}. \tag{1}

Now using the facts that y1=1y_1 = 1, yny_n increases and lim⁡n→∞yn=c\lim_{n\to\infty} y_n = c we obtain 1≤yn≤c1 \le y_n \le c. Hence

1c≤∑n=1∞12n⋅yn≤1.\frac{1}{c} \le \sum_{n=1}^{\infty}\frac{1}{2^n \cdot y_n} \le 1.

Thus we get from (1)

2c=lim⁡m→∞(4ym+2−2ym+1)=2+∑n=1∞12n⋅yn∈[2+1c,3].2c = \lim_{m\to\infty}(4y_{m+2} - 2y_{m+1}) = 2 + \sum_{n=1}^{\infty}\frac{1}{2^n \cdot y_n} \in \left[2 + \frac{1}{c}, 3\right].

So we have 2c2≥2c+12c^2 \ge 2c + 1 and 2c≤32c \le 3. Recall that c≥1c \ge 1. Therefore 1+3≤2c≤31 + \sqrt{3} \le 2c \le 3, which finishes the proof.

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

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

Πώς πήγε;