The Somanacci sequence is generated by three initial terms, each a positive integer smaller than 2012. Each term of the sequence, beginning from the fourth term, is the sum of all preceding numbers. How many distinct Somanacci sequences have 2012 as one of their terms?
Solution
Let Sn be the n-th Somanacci number. Then, for n≥5, Sn=Sn−1+Sn−2+⋯+S1=Sn−1+Sn−1=2Sn−1, because Sn−1=Sn−2+⋯+S1. So, since S4=S3+S2+S1, Sn=(S1+S2+S3)⋅2n−4. Since 2012=2⋅1006=22⋅503, the answer is the number of ways of writing 1006 as sum of three positive integer numbers plus the number of ways of writing 503 as sum of three positive integer numbers, that is (21005)+(2502)=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.