uniolympiads Ελληνικά

IMC 1996, Day 1, Problem 4

Let a1=1a_1 = 1, an=1n∑k=1n−1akan−ka_n = \dfrac{1}{n}\displaystyle\sum_{k=1}^{n-1} a_k a_{n-k} for n≥2n \ge 2. Show that

(i) lim sup⁡n→∞∣an∣1/n<2−1/2\limsup_{n \to \infty} |a_n|^{1/n} < 2^{-1/2};

(ii) lim sup⁡n→∞∣an∣1/n≥2/3\limsup_{n \to \infty} |a_n|^{1/n} \ge 2/3.

Original from the official PDF(15 points) X 1 n−1 Let a 1 = 1, a n = a k a n−k for n ≥ 2. Show that n k=1 (i) lim sup |a n | 1/n < 2 −1/2 ; n→∞ (ii) lim sup |a n | 1/n ≥ 2/3. n→∞

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

Solution.

(i) We show by induction that

(∗)an≤qnforn≥3,(*) \qquad\qquad a_n \leq q^n \quad \text{for} \quad n \geq 3,

where q=0.7q = 0.7 and use that 0.7<2−1/20.7 < 2^{-1/2}. One has a1=1a_1 = 1, a2=12a_2 = \dfrac12, a3=13a_3 = \dfrac13, a4=1148a_4 = \dfrac{11}{48}. Therefore (∗)(*) is true for n=3n = 3 and n=4n = 4. Assume (∗)(*) is true for n≤N−1n \leq N - 1 for some N≥5N \geq 5. Then

aN=2NaN−1+1NaN−2+1N∑k=3N−3akaN−k≤2NqN−1+1NqN−2+N−5NqN≤qNa_N = \frac{2}{N} a_{N-1} + \frac{1}{N} a_{N-2} + \frac{1}{N} \sum_{k=3}^{N-3} a_k a_{N-k} \leq \frac{2}{N} q^{N-1} + \frac{1}{N} q^{N-2} + \frac{N-5}{N} q^N \leq q^N

because 2q+1q2≤5\dfrac{2}{q} + \dfrac{1}{q^2} \leq 5.

(ii) We show by induction that

an≥qnforn≥2,a_n \geq q^n \quad \text{for} \quad n \geq 2,

where q=23q = \dfrac23. One has a2=12>(23)2=q2a_2 = \dfrac12 > \left(\dfrac23\right)^2 = q^2. Going by induction we have for N≥3N \geq 3

aN=2NaN−1+1N∑k=2N−2akaN−k≥2NqN−1+N−3NqN=qNa_N = \frac{2}{N} a_{N-1} + \frac{1}{N} \sum_{k=2}^{N-2} a_k a_{N-k} \geq \frac{2}{N} q^{N-1} + \frac{N-3}{N} q^N = q^N

because 2q=3\dfrac{2}{q} = 3.

Transcribed from the official solutions, pages 4–5. 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?