Maths Olympiad Prep

Library / /3 of 7

Algebra Difficulty 5.9 AIME, harder Prove it Austria

We consider the sequences (an)n0(a_n)_{n \ge 0} and (bn)n0(b_n)_{n \ge 0} which are defined by a0=b0=2a_0 = b_0 = 2 and a1=b1=14a_1 = b_1 = 14 and by
an=14an1+an2, a_n = 14a_{n-1} + a_{n-2},
bn=6bn1bn2 b_n = 6b_{n-1} - b_{n-2}
for n2n \ge 2.
Decide whether there are infinitely many integers which occur in both sequences.

Solution

Answer. Yes.

Sequence (an)(a_n) starts with values 22, 1414, 198198, 27862786, 3920239202, 551614551614. Sequence (bn)(b_n) starts with values 22, 1414, 8282, 478478, 27862786, 1623816238, 9464294642, 551614551614. We therefore conjecture that a2k+1=b3k+1a_{2k+1} = b_{3k+1} holds for k0k \ge 0.
Shifting the recurrence yields
an+214an+1an=0,an+114anan1=0,an14an1an2=0 a_{n+2} - 14a_{n+1} - a_n = 0, \\ a_{n+1} - 14a_n - a_{n-1} = 0, \\ a_n - 14a_{n-1} - a_{n-2} = 0
for n2n \ge 2. Multiplying these recurrences by 11, 1414 and 1-1, respectively, and taking the sum yields an+2198an+an2=0a_{n+2} - 198a_n + a_{n-2} = 0 and thus
an+2=198anan2 a_{n+2} = 198a_n - a_{n-2}
for n2n \ge 2.

Shifting the recurrence of (bn)(b_n) yields
bn+36bn+2+bn+1=0,bn+26bn+1+bn=0,bn+16bn+bn1=0,bn6bn1+bn2=0,bn16bn2+bn3=0 \begin{align*} b_{n+3} - 6b_{n+2} + b_{n+1} &= 0, \\ b_{n+2} - 6b_{n+1} + b_n &= 0, \\ b_{n+1} - 6b_n + b_{n-1} &= 0, \\ b_n - 6b_{n-1} + b_{n-2} &= 0, \\ b_{n-1} - 6b_{n-2} + b_{n-3} &= 0 \end{align*}
for n3n \ge 3. Multiplying these recurrences by 11, 66, 3535, 66 and 11, respectively, and taking the sum yields bn+3198bn+bn3=0b_{n+3} - 198b_n + b_{n-3} = 0 and thus
bn+3=198bnbn3 b_{n+3} = 198b_n - b_{n-3}
for n3n \ge 3.
We see that the subsequences (a2k+1)(a_{2k+1}) and (b3k+1)(b_{3k+1}) have the same initial values a1=b1=14a_1 = b_1 = 14 and a3=b4=2786a_3 = b_4 = 2786 and fulfil the same recurrence. This implies that a2k+1=b3k+1a_{2k+1} = b_{3k+1} for all k0k \ge 0.
From the given recurrence, it is obvious that the sequence (an)(a_n) is strictly increasing. Thus we also get infinitely many values which occur in both sequences.

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 and solution reproduced as published; topic and difficulty added by this site.