Even Fibonacci Numbers 2

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
square1001
Posts: 27
Joined: Tue Mar 15, 2016 2:58 am
Location: Tokyo, Japan
Contact:

Even Fibonacci Numbers 2

Post by square1001 » Tue Mar 15, 2016 3:22 am

Let's consider about "Fibonacci Numbers". It looks like Problem 2, but it's difficult more than Problem 2.

Let $F_n =
\begin{cases}
1 & n=0 \\
2 & n=1 \\
F_{n-1}+F_{n-2} & n \ge 2
\end{cases}$

So, the sequence $F_i = 1,2,3,5,8,13,21,34,55,89,144,233,...$

By considering the terms in the Fibonacci sequence whose values do not exceed $10^{10^{13}}$, find the sum of the even-valued terms modulo $10^9+7$.
Image

gbroxey
Posts: 1
Joined: Wed Mar 02, 2016 2:37 am

Re: Even Fibonacci Numbers 2

Post by gbroxey » Mon Dec 05, 2016 7:30 pm

Would the answer be... 633730349?
Expand
Just a bit of matrix shuffling here. The linear recurrence for the even Fibonacci numbers is $\{4, 1\}$, and the SUM of these has a recurrence, $\{5, -3, -1\}$.
So define a matrix $M=\{\{5, -3, -1\}, \{1, 0, 0\}, \{0, 1, 0\}\}$ and $b = \{\{44\}, \{10\}, \{2\}\}$. For any integer $n$, the sum of the first $n$ even Fibonacci numbers is the uppermost element in $M^{n-3} * b$. The last part is determining $n$. The formula for this, for large enough bounds $L$, is $n=\text{floor}\left[\frac{\log(5/(5+2\sqrt[]{5})) + \log(n)}{\log(2+\sqrt[]{5})}\right]$, which gives us $n=15949906555939$. The rest is just binary matrix exponentiation with a modulo.
Image
Discord: heteroing#1674.

Post Reply