Maths Olympiad Prep

Library / HMMT November /257 of 672

HMMT November

Algebra Difficulty 4.9 AIME Find the answer

Define the sequence {xi}i≥\left\{x_{i}\right\}_{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}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We have x3=1+1+11=3,x4=3+1+11=5,x5=5+3+11=9,x6=9+5+13=5x_{3}=\frac{1+1+1}{1}=3, x_{4}=\frac{3+1+1}{1}=5, x_{5}=\frac{5+3+1}{1}=9, x_{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 8. 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.