Maths Olympiad Prep

Library / Estonija /23 of 32

Estonija, 2010

Algebra Difficulty 6.0 National Olympiad Prove it Estonia

The sequence (an)(a_n) is defined by a1=1a_1 = 1 and an=n⋅(a1+⋯+an−1)a_n = n \cdot (a_1 + \dots + a_{n-1}) for all n>1n > 1. Find all indices nn for which ana_n is divisible by 1⋅2⋅⋯⋅n1 \cdot 2 \cdot \dots \cdot n. (Grade 12.)

Solution

For each n≥2n \ge 2 denote Sn=a1+⋯+an−1S_n = a_1 + \dots + a_{n-1}. Then an=Sn⋅na_n = S_n \cdot n and for all n>2n > 2 we have Sn=Sn−1+an−1=Sn−1+Sn−1⋅(n−1)=Sn−1⋅nS_n = S_{n-1} + a_{n-1} = S_{n-1} + S_{n-1} \cdot (n-1) = S_{n-1} \cdot n. Hence Sn=Sn−1⋅n=Sn−2⋅(n−1)n=⋯=S2⋅3⋅⋯⋅n=n!2S_n = S_{n-1} \cdot n = S_{n-2} \cdot (n-1)n = \dots = S_2 \cdot 3 \cdot \dots \cdot n = \frac{n!}{2} because S2=1=1⋅22S_2 = 1 = \frac{1 \cdot 2}{2}. Consequently an=Sn⋅n=n!⋅n2a_n = S_n \cdot n = n! \cdot \frac{n}{2} for all n≥2n \ge 2. Therefore, for n≥2n \ge 2, ana_n is divisible by n!n! iff nn is even, and n=1n=1 also satisfies the condition.

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