Fibonacci numbers along residue classes and convolutions

Based on the provided text from the paper "Fibonacci Numbers Along Residue Classes and Convolutions" by Helmut Prodinger, here is a detailed technical summary.

1. Problem Statement

The paper addresses the study of Fibonacci numbers along residue classes, specifically focusing on the subsequence $F_{dn+h}$, where $d$ and $h$ are integers, and $F_n$ denotes the standard Fibonacci sequence ($F_0=0, F_1=1, F_{n+2}=F_{n+1}+F_n$).

While a recent paper (referenced as [2]) analyzed the specific case where $h=0$ (i.e., $F_{dn}$), this work extends the investigation to the general case where $h$ is arbitrary. The primary objectives are:

1. To derive the generating function for the sequence $\sum_{n \ge 0} F_{dn+h} z^n$.
2. To determine the $s$-fold convolution of this sequence, defined via the generating function raised to the power of $s+1$.

The author notes that the general $h$ case is more complex than the $h=0$ case because the numerator of the generating function does not vanish, requiring more intricate algebraic manipulation.

2. Methodology

The author employs a combination of generating functions, Binet's formulas, and Chebyshev polynomials of the second kind ($U_n(x)$).

A. Chebyshev Polynomials of the Second Kind

The paper begins by reviewing the properties of $U_n(x)$, defined via the generating function:
$$\frac{1}{1 - 2tx + t^2} = \sum_{n \ge 0} U_n(x) t^n$$
Key properties utilized include:

• Recursion: $U_n(x) - 2xU_{n-1}(x) + U_{n-2}(x) = 0$.
• Explicit Formulas: Derived via induction for even and odd indices.
• Generalization: The author introduces a generalized polynomial $U_n^{(s)}(x)$ related to the expansion of $\frac{1}{(1 - 2tx + t^2)^{s+1}}$.
• Sign Variation: A variation is introduced with a parameter $\epsilon \in \{-1, +1\}$ to handle the term $(1 - 2tx - \epsilon t^2)$, which is crucial for matching the Fibonacci generating function structure.

B. Derivation of the Generating Function

To find the generating function for $F_{dn+h}$, the author uses Binet's formulas:
$$F_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}, \quad L_n = \alpha^n + \beta^n$$
where $\alpha = \frac{1+\sqrt{5}}{2}$ and $\beta = \frac{1-\sqrt{5}}{2}$.

By summing the geometric series for $\alpha^{dn+h}$ and $\beta^{dn+h}$, the author derives a rational function. The denominator is identified as $1 - zL_d + (-1)^d z^2$, which corresponds to the characteristic equation of the recurrence relation for the subsequence.

C. Convolution Analysis

The $s$-fold convolution is analyzed by raising the generating function to the power $s+1$.
$$\left( \sum_{n \ge 0} F_{dn+h} z^n \right)^{s+1}$$
The numerator $(F_h + (-1)^h z F_{d-h})^{s+1}$ is expanded using the Binomial Theorem. The denominator is expanded using the previously defined generalized Chebyshev polynomials $U_n^{(s)}(L_d)$, noting that the parameter $\epsilon$ in the Chebyshev definition corresponds to $(-1)^{d-1}$ in this context.

3. Key Contributions and Results

Proposition 1: Generating Function for $F_{dn+h}$

The paper establishes the closed-form generating function for the general residue class:
$$\sum_{n \ge 0} F_{dn+h} z^n = \frac{F_h + (-1)^h z F_{d-h}}{1 - zL_d + (-1)^d z^2}$$

• Significance: This generalizes previous results limited to $h=0$. The proof relies on algebraic simplification of the Binet forms, showing that the denominator cancels out the infinite series terms, leaving a linear numerator.

Theorem 1: The $s$-fold Convolution

The main result provides an explicit formula for the coefficients of the $s$-fold convolution. The generating function for the convolution is:
$$\left( \frac{F_h + (-1)^h z F_{d-h}}{1 - zL_d + (-1)^d z^2} \right)^{s+1} = \sum_{n \ge 0} z^n \sum_{j=0}^{s+1} \binom{s+1}{j} F_h^{s+1-j} (-1)^{jh} F_{d-h}^j U_{n-j}^{(s)}(L_d)$$

• Mechanism: The result is a convolution of the binomial expansion of the numerator and the series expansion of the denominator (expressed via $U_n^{(s)}$).
• Special Case ($h=0$): When $h=0$, the formula simplifies significantly because $F_0=0$, reducing the sum to a single term involving $F_d^{s+1}$.

Extension to Lucas Numbers

The author briefly notes that the same methodology applies to Lucas numbers ($L_{dn+h}$), yielding a similar generating function with a modified numerator:
$$\sum_{n \ge 0} L_{dn+h} z^n = \frac{L_h + (-1)^{h-1} z L_{d-h}}{1 - zL_d + (-1)^d z^2}$$

4. Significance

• Completeness: This work completes the analysis of Fibonacci subsequences along arithmetic progressions by solving the general $h$ case, which was previously considered "more involved."
• Unification: It demonstrates a deep connection between Fibonacci numbers, Lucas numbers, and Chebyshev polynomials. Specifically, it shows that the $s$-fold convolution of these sequences can be explicitly computed using generalized Chebyshev polynomials evaluated at $L_d$.
• Explicit Formulas: The paper moves beyond existence proofs to provide fully explicit combinatorial formulas involving binomial coefficients, Fibonacci/Lucas numbers, and Chebyshev polynomials, which are valuable for further computational or theoretical investigations in number theory and combinatorics.

In summary, Prodinger successfully generalizes the study of Fibonacci subsequences and their convolutions by leveraging the structural properties of Chebyshev polynomials to derive explicit generating functions and coefficient formulas for arbitrary residue classes.