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
| CREATOR | Helmut Prodinger |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 5220 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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}}.