Maths Olympiad Prep

Library / /15 of 73

Algebra Difficulty 4.9 AIME Prove it Brazil

The Somanacci sequence is generated by three initial terms, each a positive integer smaller than 20122012. Each term of the sequence, beginning from the fourth term, is the sum of all preceding numbers. How many distinct Somanacci sequences have 20122012 as one of their terms?

Solution

Let SnS_n be the nn-th Somanacci number. Then, for n5n \ge 5, Sn=Sn1+Sn2++S1=Sn1+Sn1=2Sn1S_n = S_{n-1} + S_{n-2} + \dots + S_1 = S_{n-1} + S_{n-1} = 2S_{n-1}, because Sn1=Sn2++S1S_{n-1} = S_{n-2} + \dots + S_1. So, since S4=S3+S2+S1S_4 = S_3 + S_2 + S_1, Sn=(S1+S2+S3)2n4S_n = (S_1 + S_2 + S_3) \cdot 2^{n-4}. Since 2012=21006=225032012 = 2 \cdot 1006 = 2^2 \cdot 503, the answer is the number of ways of writing 10061006 as sum of three positive integer numbers plus the number of ways of writing 503503 as sum of three positive integer numbers, that is (10052)+(5022)=630261\binom{1005}{2} + \binom{502}{2} = 630261.

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.