Fibonacci numbers along residue classes and convolutions

Helmut Prodinger · 2026

Read Fibonacci numbers along residue classes and convolutions by Helmut Prodinger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15718.txt.

Introduction

Prodinger extends a recent study of Fibonacci numbers along residue classes. The sequence F at steps dn+h was covered before only for h equal to zero. The general h case proves more involved. Chebyshev polynomials supply the main tool for the harder case. Convolutions of the sequence fall under the same treatment. The short note builds directly on the earlier arXiv study. It completes the picture for all residue shifts h.

Catalog record

CREATORHelmut Prodinger
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE5220
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.15718

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fibonacci numbers along residue classes and convolutions
Helmut Prodinger

Abstract
. The sequence F d ​ n + h F_{dn+h} and its convolutions have (for h = 0 h=0 ) been studied in a recent paper at the arxiv. The instance with general h h is more involved and uses Chebyshev polynomials.



2010 Mathematics Subject Classification
11B39

1.
A review of the Chebyshev polynomials of the second kind

These polynomials might be defined and studied in many ways
[
1
]
, but we consider
U_{n}(x)
via the generating function:

\frac{1}{1-2tx+t^{2}}=\sum_{n\geq 0}U_{n}(x)t^{n}.

The denominator
1-2tx+t^{2}
leads to the recursion
U_{n}(x)-2xU_{n-1}(x)+U_{n-2}(x)=0
, with
U_{0}(x)=1
and
U_{1}(x)=2x
.
From this one can obtain via induction the explicit formula

\begin{cases}U_{2n}(x)=\sum_{k}x^{2k}(-1)^{n-k}\binom{n+k}{2k}2^{2k},\\
U_{2n+1}(x)=\sum_{k}x^{2k+1}(-1)^{n-k}\binom{n+k+1}{2k+1}2^{2k+1}.\end{cases}

Since

\frac{\partial}{\partial x}\frac{1}{1-2tx+t^{2}}=\frac{2t}{(1-2tx+t^{2})^{2}}\quad\text{and}\quad\frac{\partial}{\partial x}\frac{1}{(1-2tx+t^{2})^{s}}=\frac{2st}{(1-2tx+t^{2})^{s+1}},

we may set

\frac{1}{(1-2tx+t^{2})^{s+1}}=\sum_{n\geq 0}U_{n}^{(s)}(x)t^{n}

and find again explicit formulæ

\begin{cases}U_{2n}^{(s)}(x)=\sum_{k}x^{2k}(-1)^{n-k}\binom{n+k+s}{2k+s}\binom{2k+s}{s}2^{2k},\\
U_{2n+1}^{(s)}(x)=\sum_{k}x^{2k+1}(-1)^{n-k}\binom{n+k+s+1}{2k+s+1}\binom{2k+s+1}{s}2^{2k+1}.\end{cases}

This may be derived via induction on the parameter
s
.

A small variation is via the introduction of a
\pm
sign; let
\epsilon\in\{-1,+1\}
and

\frac{1}{(1-2tx-\epsilon t^{2})^{s+1}}=\sum_{n\geq 0}\overline{U}_{n}^{(s)}(x)t^{n}

then

\begin{cases}\overline{U}_{2n}^{(s)}(x)=\sum_{k}x^{2k}\epsilon^{n-k}\binom{n+k+s}{2k+s}\binom{2k+s}{s}2^{2k},\\
\overline{U}_{2n+1}^{(s)}(x)=\sum_{k}x^{2k+1}\epsilon^{n-k}\binom{n+k+s+1}{2k+s+1}\binom{2k+s+1}{s}2^{2k+1}.\end{cases}

2.
The
d
-section of Fibonacci numbers

The recent paper
[
2
]
considers for Fibonacci numbers
F_{n+2}=F_{n+1}+F_{n}
,
F_{0}=0
,
F_{1}=1

\sum_{n\geq 0}F_{2n}z^{n}=\frac{z}{1-3z+z^{2}}\quad\text{and, more generally,}\quad\sum_{n\geq 0}F_{dn}z^{n}.

Here, we are interested in

\sum_{n\geq 0}F_{dn+h}z^{n}

which makes the analysis more complete and also more challenging.

Proposition 1
.

\sum_{n\geq 0}F_{nd+h}z^{n}=\frac{F_{h}+(-1)^{h}zF_{d-h}}{1-zL_{d}+(-1)^{d}z^{2}}.

Proof.
We will use the Binet formulæ

F_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta},\ L_{n}=\alpha^{n}+\beta^{n}\quad\text{with}\quad\alpha=\frac{1+\sqrt{5}}{2},\ \beta=\frac{1-\sqrt{5}}{2}.

Then

\displaystyle X

\displaystyle:=(1-zL_{d}+(-1)^{d}z^{2})\sum_{n\geq 0}F_{nd+h}z^{n}

\displaystyle=(1-z(\alpha^{d}+\beta^{d})+(-1)^{d}z^{2})\sum_{n\geq 0}\frac{\alpha^{nd+h}-\beta^{nd+h}}{\alpha-\beta}z^{n}

\displaystyle=\frac{1-z(\alpha^{d}+\beta^{d})+(-1)^{d}z^{2}}{\alpha-\beta}\sum_{n\geq 0}(\alpha^{nd+h}-\beta^{nd+h})z^{n}

\displaystyle=\frac{1-z(\alpha^{d}+\beta^{d})+(-1)^{d}z^{2}}{\alpha-\beta}\bigg[\frac{\alpha^{h}}{1-z\alpha^{d}}-\frac{\beta^{h}}{1-z\beta^{d}}\bigg]

\displaystyle=\frac{1-z(\alpha^{d}+\beta^{d})+(-1)^{d}z^{2}}{\alpha-\beta}\frac{\alpha^{h}(1-z\beta^{d})-\beta^{h}(1-z\alpha^{d})}{1-z(\alpha^{d}+\beta^{d})+(-1)^{d}z^{2}}

\displaystyle=\frac{\alpha^{h}(1-z\beta^{d})-\beta^{h}(1-z\alpha^{d})}{\alpha-\beta}

\displaystyle=F_{h}-z\frac{\alpha^{h}(\beta^{d})-\beta^{h}(\alpha^{d})}{\alpha-\beta}

\displaystyle=F_{h}-z(-1)^{h}\frac{\beta^{d-h}-\alpha^{d-h}}{\alpha-\beta}

\displaystyle=F_{h}+z(-1)^{h}F_{d-h}.\qed

The
s
-fold convolution of the sequence
\langle F_{nd+h}\rangle_{n}
is (in
[
2
]
for
h=0
only) defined via the generating function

\biggl(\sum_{n\geq 0}F_{nd+h}z^{n}\biggr)^{s+1}.

Indeed, for
h=0
, we have

\frac{F_{h}+(-1)^{h}zF_{d-h}}{1-zL_{d}+(-1)^{d}z^{2}}\bigg|_{h=0}=\frac{zF_{d}}{1-zL_{d}+(-1)^{d}z^{2}},

and the simpler numerator makes life a bit easier. We have to deal with

(F_{h}+(-1)^{h}zF_{d-h})^{s+1}=\sum_{j=0}^{s+1}\binom{s+1}{j}F_{h}^{s+1-j}(-1)^{jh}z^{j}F_{d-h}^{j}

and eventually with

\sum_{j=0}^{s+1}\binom{s+1}{j}F_{h}^{s+1-j}(-1)^{jh}z^{j}F_{d-h}^{j}\frac{1}{(1-zL_{d}+(-1)^{d}z^{2})^{s+1}}

Fortunately, following the introduction, the expansion of

\frac{1}{(1-zL_{d}+(-1)^{d}z^{2})^{s+1}}=\sum_{n\geq 0}\overline{U}_{n}^{(s)}(L_{d})z^{n}

is known, and
\epsilon=(-1)^{d-1}
.

Therefore we have the fully explicit
s
-fold convolution of the sequence
\langle F_{nd+h}\rangle_{n}
via its generating function:

Theorem 1
.

\biggl(\frac{F_{h}+(-1)^{h}zF_{d-h}}{1-zL_{d}+(-1)^{d}z^{2}}\biggr)^{s+1}=\sum_{j=0}^{s+1}\binom{s+1}{j}F_{h}^{s+1-j}(-1)^{jh}z^{j}F_{d-h}^{j}\sum_{n\geq 0}\overline{U}_{n}^{(s)}(L_{d})z^{n}.

Expanded,

\biggl(\frac{F_{h}+(-1)^{h}zF_{d-h}}{1-zL_{d}+(-1)^{d}z^{2}}\biggr)^{s+1}=\sum_{n\geq 0}z^{n}\sum_{j=0}^{s+1}\binom{s+1}{j}F_{h}^{s+1-j}(-1)^{jh}F_{d-h}^{j}\overline{U}_{n-j}^{(s)}(L_{d}).\qed

The special case
h=0
leads to

\sum_{n\geq 0}z^{n}F_{d}^{s+1}\overline{U}_{n-j}^{(s)}(L_{d}).

Remark.
The
d
-section of Lucas numbers can also be considered:

\sum_{n\geq 0}L_{nd+h}z^{n}=\frac{L_{h}+(-1)^{h-1}zL_{d-h}}{1-zL_{d}+(-1)^{d}z^{2}}.

Read the complete text