Maths Olympiad Prep

Library / /386 of 520

Algebra Difficulty 5.6 AIME, harder Prove it

一、(Given) f(1)=2f(1)=2, for positive integer n,f(n+1)=ρ(n)+1n, f(n+1)=\rho(n)+1. Prove: when positive integer n2n \geqslant 2, we have 1122n1<1f(1)+1f(2)1-\frac{1}{2^{2^{n-1}}}<\frac{1}{f(1)}+\frac{1}{f(2)} ++1f(n)<11nn+\cdots+\frac{1}{f(n)}<1-\frac{1}{n^{n}}

Solution

Prove f(n1)1=f(n)(f(n)1). \begin{array}{l} \text {Prove } f(n-1)-1 \\ =f(n)(f(n)-1) . \end{array}

Since f(1)=2f(1)=2, from the above equation, we know that f(n)f(n) is monotonically increasing.
1f(n+1)1=1f(n)(f(n)1)=1f(n)11f(n). \begin{array}{l} \frac{1}{f(n+1)-1}=\frac{1}{f(n)(f(n)-1)} \\ =\frac{1}{f(n)-1}-\frac{1}{f(n)} . \end{array}

Thus, we have
1f(n)=1f(n)11f(n+1)1. \frac{1}{f(n)}=\frac{1}{f(n)-1}-\frac{1}{f(n+1)-1} .

Using the above equation, we get
k=1n1f(k)=11f(n+1)1. \sum_{k=1}^{n} \frac{1}{f(k)}=1-\frac{1}{f(n+1)-1} .

We will prove the following by induction:
2^{2^{n-1}}2^{2^{k-1}} 2^{2^{2-1}}=2^{2^{k}} . \end{array}

Since f(k)f(k) is a positive integer (kN)(k \in N),
f(k+1)122k1.f(k+2)1=f(k+1)(f(k+1)1)22k(22k1)<22k+1. \begin{array}{l} f(k+1)-1 \leqslant 2^{2^{k}}-1 . \\ f(k+2)-1=f(k+1)(f(k+1)-1) \\ \leqslant 2^{2 k}\left(2^{2 k}-1\right)<2^{2 k+1} . \end{array}
(*) holds for any positive integer nn. Therefore, the desired inequality is immediately obtained.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.