Summation of Summations

Take a sequence of length $n$. Discard the first term then make a sequence of the partial summations. Continue to do this over and over until we are left with a single term. We define this to be $f(n)$.

Consider the example where we start with a sequence of length 8:

$
\begin{array}{rrrrrrrr}
1&1&1&1&1&1&1&1\\
&1&2&3&4&5& 6 &7\\
& &2&5&9&14&20&27\\
& & &5&14&28&48&75\\
& & & &14&42&90&165\\
& & & & & 42 & 132 & 297\\
& & & & & & 132 &429\\
& & & & & & &429\\
\end{array}
$

Then the final number is $429$, so $f(8) = 429$.

For this problem we start with the sequence $1,3,4,7,11,18,29,47,\ldots$
This is the Lucas sequence where two terms are added to get the next term.
Applying the same process as above we get $f(8) = 2663$.
You are also given $f(20) = 742296999 $ modulo $1\,000\,000\,007$

Find $f(10^8)$. Give your answer modulo $1\,000\,000\,007$.

Given the nature of the problem, it’s expressed in matrix form to calculate $f(n)$. The process of eliminating the first element of the sequence and replacing the rest of the sequence with a partial sum can be expressed as a matrix multiplication by a triangular matrix.

The $n \times n$ triangular matrix, $T_n$, that fulfills this operation is:

$T_n = \begin{bmatrix}
0 & 0 & \cdots & 0 & 0 \\
1 & 0 & \cdots & 0 & 0 \\
1 & 1 & \cdots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
1 & 1 & \cdots & 1 & 0 \\
\end{bmatrix}$

Therefore, $ f(n) = (1, 1, 1, …, 1) * T_n^{n-1} * (1, 1, 1, …, 1)^T \mod 1,000,000,007$.

Given that $T_n$ is a triangular matrix with a rather simple structure, it can be observed that raising $T_n$ to the power of $(n-1)$ results in another triangular matrix, with the last row being our answer $f(n)$.

However, calculating this operation directly for large values of n (e.g. $10^8$) may not be computationally feasible.

Therefore, we use the concept of exponentiation by squaring where we calculate the power in a logarithmic number of multiplications.

Also we notice an interesting property that $T_n^m$ is equivalent to $T_{n*m}$, where we treat all indices larger than $n$ as the operand to the multiplication to be 0. This property greatly reduces the number of calculations and storage.

Finally, by properly applying matrix multiplication and reducing the modulo operation at each step, we are effectively reducing the problem size. Hence, this allows us to calculate large $f(n)$ values modulo $1,000,000,007$ in a feasible manner.

Since the full calculation of $f(10^8)$ requires significant computational power, it’s not possible to perform within this text-based format. You would implement this method in a computer program capable of handling these large computations under modulo $1,000,000,007$.

More Answers: