Polynomials of Fibonacci Numbers

The Fibonacci numbers $\{f_n, n \ge 0\}$ are defined recursively as $f_n = f_{n-1} + f_{n-2}$ with base cases $f_0 = 0$ and $f_1 = 1$.
Define the polynomials $\{F_n, n \ge 0\}$ as $F_n(x) = \displaystyle{\sum_{i=0}^n f_i x^i}$.
For example, $F_7(x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6 + 13x^7$, and $F_7(11) = 268\,357\,683$.
Let $n = 10^{15}$. Find the sum $\displaystyle{\sum_{x=0}^{100} F_n(x)}$ and give your answer modulo $1\,307\,674\,368\,000 \ (= 15!)$.

This problem is related to the Fibonacci sequence and involves combinatorics, number theory and polynomial operations, which are more complex than high school level homework problems. However, I’ll do my best to explain the method to solve this problem.

As you probably know, Fibonacci numbers (f_n) can also be defined using closed form expressions using the golden ratio φ and Ψ (phi and psi), which are the roots of x^2 = x + 1. Here’s the formula: f_n = (φ^n – Ψ^n) / sqrt(5). This formula involves complex numbers, so for the purpose of this problem, we’ll stick to the recursive definition.

The polynomial F_n(x) is essentially sum of products of Fibonacci numbers and powers of x. To calculate sum of F_n(x) from x=0 to 100, we need to sum each term separately i.e., sum of f_1*x for x from 0 to 100, sum of f_2*x^2 for x from 0 to 100, and so on.

Now, the sum of x from 0 to 100 is S = n*(n+1)/2 = 100*101/2 = 5050. And the sum of x^2 from 0 to 100 is S2 = n*(n+1)*(2n+1)/6 = 100*101*201/6 = 338350. Similar formula exists for sum of x^3, x^4, etc. However, for large n (like n = 10^15), these sums are not practical to calculate and take modulo 1,307,674,368,000.

To solve this efficiently, we need to use the property of Fibonacci sequence that f_(n+2) = f_n + f_(n+1), then F_(n+2)(x) – xF_(n+1)(x) – F_n(x) = 0. This creates a recurrence relation and we can calculate F_n(x) modulo m in O(log n) time using matrix exponentiation.

Moreover, to calculate sum of F_n(x) for x from 0 to 100, we can calculate F_n(x) for consecutive x’s and add them all, taking modulo at each step. In this way, we avoid computing sums of large powers of x and yet get the final result modulo 1,307,674,368,000.

Finally, please note that this problem is very high level and requires knowledge of advanced mathematics and programming. It is beyond the level of high school or even most college level mathematics homework problems. It’s more suitable as a problem in a coding or math Olympiad contest.

More Answers: