# Fibonacci progression

In a number sequence, 1, 13, 169 and 2014 are respectively the first four terms of the sequence. The next terms are equal to the sum of the four numbers that precede them. For example, the fifth term of this sequence is 1+13+169+2014=2197. How many digits does the 2014th term have?

If needed, we can use 0.285 for log(1.928) and 0.942 for log(8.748).

• Is this supposed to have a solution that does not involve finding roots of the charateristic equation? Because otherwise it is a standard math problem. Jun 11 '20 at 5:14
• Oh, right. You put no-computer, so it should be so. Jun 11 '20 at 5:20

This is a linear recursion with characteristic polynomial $$x^4 - x^3 - x^2 - x - 1,$$ which has roots $$z_1 = 1.928, z_2 = -0.775, z_{3,4} = -0.076 \pm 0.815i.$$

The general solution is $$x_n = \sum\limits c_i z_i^n,$$ and the number of digits is $$\lfloor \log_{10}(x_n) \rfloor + 1.$$

Since $$|z_2|, |z_3|, |z_4|<1,$$ we have $$|x_{2014} - c_1 z_1^{2014}| \le |c_2|+|c_3|+|c_4|,$$ and the RHS is practically nothing.

Thus, $$\lfloor \log_{10}(x_n) \rfloor \approx \lfloor \log_{10}(c_1 z_1^{2014}) \rfloor = \lfloor \log_{10}(c_1) + 574.0068 \rfloor.$$

You can solve for the $$c_i$$ using the values of $$x_1, \dots, x_4,$$ but at a quick glance (and using the $$y$$-intercept of the graph in Fivesideddice's answer), we expect $$100 \le c_1 \le 200 \Rightarrow \lfloor \log_{10}(x_n) \rfloor = 576,$$ making the number of digits $$577.$$

• $|c_2|+|c_3|+|c_4|$ should be $|c_2 z_2^{2014}| + |c_3 z_3^{2014}| + |c_4 z_4^{2014}|$ Jun 11 '20 at 8:43
• ... but $|c_2|+|c_3|+|c_4|$ also does the job, in fact. Jun 11 '20 at 8:50
• Computer solution has it at $576$ digits, $f(2014)\approx 9.09124\times 10^{575}$ Jun 11 '20 at 9:59
• This is certainly the right way to do the problem if computers are allowed (or at least a right way; just computing the values works OK too, but would be more painful if we wanted the length of the billionth instead of the 2014th number in the sequence). But with the [no-computers] tag? Finding the roots is a little laborious, and then finding the coefficients is a little painful too, if you want to do it in a way that lets you be confident of having the right final answer. Jun 11 '20 at 12:14
• Incidentally, like Daniel I get 576 digits rather than 577. Jun 11 '20 at 12:15