Maths Olympiad Prep

Library / /3 of 120

Algebra Difficulty 4.4 AIME Prove it Croatia

Sequence (an)(a_n) is defined recursively: a1=2a_1 = 2, an=2(n+an1)a_n = 2(n + a_{n-1}) for n2n \ge 2. Prove that an<2n+2a_n < 2^{n+2} for all nNn \in \mathbb{N}.

Solution

First few elements of the sequence are
a1=2a_1 = 2, a2=2(2+2)=8a_2 = 2(2+2) = 8, a3=2(3+8)=22a_3 = 2(3+8) = 22, a4=2(4+22)=52a_4 = 2(4+22) = 52, \dots
Let us look at the differences 2n+2an2^{n+2} - a_n:
23a1=82=6,24a2=168=8,25a3=3222=10,26a4=6452=12. \begin{align*} 2^3 - a_1 &= 8 - 2 = 6, \\ 2^4 - a_2 &= 16 - 8 = 8, \\ 2^5 - a_3 &= 32 - 22 = 10, \\ 2^6 - a_4 &= 64 - 52 = 12. \end{align*}

We assume that an=2n+22(n+2)a_n = 2^{n+2} - 2(n+2) and we will prove it using mathematical induction.
The basis was already checked.
Assume that an=2n+22(n+2)a_n = 2^{n+2} - 2(n+2) for some nNn \in \mathbb{N}.
Using the given recursion we get
an+1=2((n+1)+an)=2(n+1+2n+22(n+2))=22n+22(n+3)=2n+32(n+3). \begin{align*} a_{n+1} &= 2((n+1) + a_n) = 2(n+1+2^{n+2}-2(n+2)) \\ &= 2 \cdot 2^{n+2} - 2(n+3) = 2^{n+3} - 2(n+3). \end{align*}
This completes the inductive step and we conclude that for all nNn \in \mathbb{N}
an=2n+22(n+2)<2n+2. a_n = 2^{n+2} - 2(n+2) < 2^{n+2}.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.