Maths Olympiad Prep

Library / /273 of 740

Algebra Difficulty 4.9 AIME Prove it United States

Problem:

Define the sequence {xi}i≥0\{x_{i}\}_{i \geq 0} by x0=x1=x2=1x_{0}=x_{1}=x_{2}=1 and xk=xk−1+xk−2+1xk−3x_{k}=\frac{x_{k-1}+x_{k-2}+1}{x_{k-3}} for k>2k>2. Find x2013x_{2013}.

Solution

Solution:

We have x3=1+1+11=3x_{3}=\frac{1+1+1}{1}=3, x4=3+1+11=5x_{4}=\frac{3+1+1}{1}=5, x5=5+3+11=9x_{5}=\frac{5+3+1}{1}=9, x6=9+5+13=5x_{6}=\frac{9+5+1}{3}=5. By the symmetry of our recurrence (or just further computation—it doesn't matter much), x7=3x_{7}=3 and x8=x9=x10=1x_{8}=x_{9}=x_{10}=1, so our sequence has period 88. Thus x2013=x13=x5=9x_{2013}=x_{13}=x_{5}=9.

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.