POTW #407: Find the Smallest Value of n for $S_n > 10000 | Mar 4th, 2020

[anemone]

Here is this week's POTW:

-----

Consider the sequence of numbers 4, 7, 1, 8, 9, 7, 6, ... For $n>2$, the $n$th term of the sequence is the units digit of the sum of the two previous terms. Let $S_n$ denote the sum of the first $n$ terms of this sequence. What is the smallest value of $n$ for which $S_n>10000$?

-----

Remember to read the https://mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to https://mathhelpboards.com/forms.php?do=form&fid=2!

 

[anemone]

Congratulations to the following members for their correct solution!(Cool)

1. castor28
2. kaliprasad
3. lfdahl

Solution from castor28:

Spoiler

The sequence is defined by the recurrence relation $x_n=(x_{n-1}+x_{n-2})\bmod{10}$.
Looking at the first five terms, we observe that the period of the sequence is $3\pmod{2}$ and $4\pmod{5}$; the period is therefore $12$.

We list the first $12$ terms, and the cumulative sums:
$$
\begin{array}{c|r|r|r|r|r|r|r|r|r|r|r|r|}
n&1&2&3&4&5&6&7&8&9&10&11&12\\
\hline
a_n&4&7&1&8&9&7&6&3&9&2&1&3\\
\hline
S_n&4&11&12&20&29&36&42&45&54&56&57&60
\end{array}
$$
As each period contributes $60$ to the total, we need $166$ full periods, giving a total of $9960$. To reach $10001$, we must increase that total by at least $41$. Looking at the table, we see that we must include $7$ additional terms, giving a total of $10002$. The total number of terms is therefore $12\times166+7=\bf1999$.