0

Let $F(n)$ be the $n$-th Fibonacci number. That is, $F(n)$ satisfies

$F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2) (if n≥2).$

Let $f_k(n)$ be the function such that

$f_0(n) = F(n)$,

$f_k(n) = \sum\limits_{i=1}^n f_{k-1}(i)\ \ ({\rm if}\ k \ge 1)$.

You are given that $f_1(1) = 1$, $f_2(2) = 3$ and $f_{10}(10) = 130965$.

Find $f_{10^8}(10^8) \pmod{1\ 000\ 000\ 007}$.

  • 1
    This is https://erdos.sdslabs.co/problems/49. – Martin R Jan 10 '15 at 20:58
  • @MartinR ... right .. U got any idea how to solve these recurrences ? !! –  Jan 10 '15 at 21:01
  • It is not very hard to workout the numerical values of first few terms of $f_n(n)$. If you perform a search over OEIS, it return OEIS A176085 and the sequence $f_n(n)$ has generation function:

    $$\sum_{n=1}^\infty f_n(n) t^n = \left(1 - \frac{t}{\sqrt{1-4t}}\right)\frac{t}{1-4t-t^2}$$

    No idea how to proceed, just give you some ideas...

     – achille hui Jan 10 '15 at 21:43
  • If you let $M = \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}$, and $L = M^{-2} = \begin{bmatrix} 1 & -1 \ -1 & 2 \end{bmatrix}$, then $$f_k(n) = M^{2k} \left(M^n - \sum_{i = 0}^{k - 1} {n + i - 1 \choose i}L^i\right){2, 1}$$ which looks conspicuously similar to the series $$|x| < 1 \Longrightarrow \sum{i = 0}^{\infty}{n + i - 1 \choose i}x^i = (1 - x)^{-n}$$ Maybe someone knows how to compute the partial sum of the series. – DanielV Jan 11 '15 at 01:39
  • Let $a_n = f_n(n)$ and $b_n = \binom{2n}{n}$, they satisfy recurrence relations

    $$ a_{n} = \begin{cases} 4 a_{n-1} + a_{n-2} - b_{n-2}, &n \ge 2\1,&n = 1\0,&n = 0\end{cases} \quad\text{ and }\quad b_{n} = \begin{cases} \frac{4n - 2}{n} b_{n-1}, & n \ge 1\ \1, & n = 0\end{cases} $$ Assume one has an efficient way to compute modular inverse of $n$ modulo $p = 10^9 + 7$. Using these recurrence relations, even for $N$ as large as $10^8$, computing $f_N(N) = a_N \pmod p$ by brute force still looks doable.

     – achille hui Jan 11 '15 at 02:45
  • Yup, it is doable, it takes less than an hour to compute $a_{10^8} \pmod {10^9 + 7}$ on my old laptop. It turns out $f_n(n)$ also has a sort of closed form expression: $$f_n(n) = \frac12 \left[F_{3n} - \sum_{k=0}^{n-2} \binom{2k}{k} F_{3(n-k-1)} \right]$$ which is pretty useless for actual computation. – achille hui Jan 12 '15 at 14:05

1 Answers1

0

Work out for $f_0(n)$ , $f_1(n)$ , $f_2(n)$ , $f_3(n)$ and soon you will end up with a formula that can produce the answer under one minute if properly computed !

I do solve it using the same ... Good luck !!

Adarsh Kumar
  • 1