# An infinite family of internal congruences modulo powers of $2$ for
partitions into odd parts with designated summands

Shane Chern  Department of Mathematics and Statistics, Dalhousie University,
Halifax, NS, B3H 4R2, Canada<EMAIL_ADDRESS>and  James A. Sellers
Department of Mathematics and Statistics, University of Minnesota Duluth,
Duluth, MN 55812, USA<EMAIL_ADDRESS>
###### Abstract.

In 2002, Andrews, Lewis, and Lovejoy introduced the combinatorial objects
which they called _partitions with designated summands_. These are built by
taking unrestricted integer partitions and designating exactly one of each
occurrence of a part. In that same work, Andrews, Lewis, and Lovejoy also
studied such partitions wherein all parts must be odd, and they denoted the
number of such partitions of size $n$ by the function $PDO(n)$. Since then,
numerous authors have proven a variety of divisibility properties satisfied by
$PDO(n)$. Recently, the second author proved the following internal
congruences satisfied by $PDO(n)$: For all $n\geq 0$,

$\displaystyle PDO(4n)$ $\displaystyle\equiv PDO(n)\pmod{4},$ $\displaystyle
PDO(16n)$ $\displaystyle\equiv PDO(4n)\pmod{8}.$

In this work, we significantly extend these internal congruence results by
proving the following new infinite family of congruences: For all $k\geq 0$
and all $n\geq 0$,

$PDO(2^{2k+3}n)\equiv PDO(2^{2k+1}n)\pmod{2^{2k+3}}.$

We utilize several classical tools to prove this family, including generating
function dissections via the unitizing operator of degree two, various modular
relations and recurrences involving a Hauptmodul on the classical modular
curve $X_{0}(6)$, and an induction argument which provides the final step in
proving the necessary divisibilities. It is notable that the construction of
each $2$-dissection slice of our generating function bears an entirely
different nature to those studied in the past literature.

###### Key words and phrases:

partitions, congruences, designated summands, generating functions,
dissections, modular forms

###### 2010 Mathematics Subject Classification:

11P83, 05A17

##  1\. Introduction

In 2002, Andrews, Lewis, and Lovejoy [2] introduced the combinatorial objects
which they called partitions with designated summands. These are built by
taking unrestricted integer partitions and designating exactly one of each
occurrence of a part. For example, there are ten partitions with designated
summands of size $4$:

$\displaystyle 4^{\prime},\ \ \ 3^{\prime}+1^{\prime},\ \ \ 2^{\prime}+2,\ \ \
2+2^{\prime},\ \ \ 2^{\prime}+1^{\prime}+1,\ \ \ 2^{\prime}+1+1^{\prime},$
$\displaystyle 1^{\prime}+1+1+1,\ \ \ 1+1^{\prime}+1+1,\ \ \
1+1+1^{\prime}+1,\ \ \ 1+1+1+1^{\prime}.$

Andrews, Lewis, and Lovejoy denoted the number of partitions with designated
summands of size $n$ by the function $PD(n)$. Hence, using this notation and
the example above, we know $PD(4)=10$.

In the same paper, Andrews, Lewis, and Lovejoy [2] also considered the
restricted partitions with designated summands wherein all parts must be odd,
and they denoted the corresponding enumeration function by $PDO(n)$. Thus,
from the example above, we see that $PDO(4)=5$, where we have counted the
following five objects:

$3^{\prime}+1^{\prime},\ \ \ 1^{\prime}+1+1+1,\ \ \ 1+1^{\prime}+1+1,\ \ \
1+1+1^{\prime}+1,\ \ \ 1+1+1+1^{\prime}.$

Andrews, Lewis, and Lovejoy noted in [2, eq. (1.6)] that the generating
function for $PDO(n)$ is given by

$\sum_{n=0}^{\infty}PDO(n)q^{n}=\frac{E(q^{4})E(q^{6})^{2}}{E(q)E(q^{3})E(q^{12})},$
(1.1)

where

$\displaystyle E(q)=(q;q)_{\infty}:=(1-q)(1-q^{2})(1-q^{3})(1-q^{4})\cdots$

is the usual _$q$ -Pochhammer symbol_.

Beginning with [2], a wide variety of Ramanujan-like congruences have been
proven for $PD(n)$ and $PDO(n)$ under different moduli. See [1, 3, 4, 5, 6, 7,
10, 12, 18] for such work. Recently, Sellers [15] proved a number of
arithmetic properties satisfied by $PDO(n)$ modulo powers of $2$ in response
to a conjecture of Herden et. al. [11]. As part of that work, Sellers proved
the following internal congruences on the way to proving infinite families of
divisibility properties satisfied by $PDO(n)$: For all $n\geq 0$,

$\displaystyle PDO(4n)$ $\displaystyle\equiv PDO(n)\pmod{4},$ (1.2)
$\displaystyle PDO(16n)$ $\displaystyle\equiv PDO(4n)\pmod{8}.$ (1.3)

While searching for such internal congruences computationally, it became clear
that the above internal congruences are part of a much larger family. The
ultimate goal of this paper is to prove the existence of the following
infinite family:

######  Theorem 1.

For all $k\geq 0$ and all $n\geq 0$,

$\displaystyle PDO(2^{2k+3}n)\equiv PDO(2^{2k+1}n)\pmod{2^{2k+3}}.$ (1.4)

It should be noted that replacing $n$ by $2n$ in the above immediately yields
the following corollary:

######  Corollary 2.

For all $k\geq 0$ and all $n\geq 0$,

$\displaystyle PDO(2^{2k+4}n)\equiv PDO(2^{2k+2}n)\pmod{2^{2k+3}}.$ (1.5)

Notice that the $k=0$ case of this corollary states that, for all $n\geq 0$,

$PDO(16n)\equiv PDO(4n)\pmod{8}$

which is (1.3) mentioned above. It is also necessary to point out that the
above families of congruences are not optimal in several isolated cases,
especially when $k$ is small. For instance, we will show in (6.1) that

$PDO(32n)\equiv PDO(8n)\pmod{64},$

which also yields

$PDO(64n)\equiv PDO(16n)\pmod{64}.$

In order to prove Theorem 1, we introduce the following auxiliary functions:

$\displaystyle\delta=\delta(q)$
$\displaystyle:=\frac{E(q^{4})E(q^{6})^{2}}{E(q)E(q^{3})E(q^{12})},$
$\displaystyle\gamma=\gamma(q)$
$\displaystyle:=\frac{E(q)^{5}E(q^{2})^{5}E(q^{6})^{5}}{E(q^{3})^{15}},$
$\displaystyle\xi=\xi(q)$
$\displaystyle:=\frac{E(q^{2})^{5}E(q^{6})}{E(q)E(q^{3})^{5}},$

and

$\displaystyle\kappa=\kappa(q):=\frac{\gamma(q^{2})^{2}}{\gamma(q)}.$

Note from (1.1) that

$\displaystyle\delta(q)=\sum_{n=0}^{\infty}PDO(n)q^{n}.$

We further define for $k\geq 2$,

$\displaystyle\Lambda_{k}=\Lambda_{k}(q):=\gamma(q)^{2^{k-2}}\sum_{n=0}^{\infty}PDO(2^{k}n)q^{n}.$
(1.6)

Finally, let $U$ be the _unitizing operator of degree two_ , given by

$\displaystyle U\left(\sum_{n}a_{n}q^{n}\right):=\sum_{n}a_{2n}q^{n}.$

These will allow us to represent each $2$-dissection slice of the generating
function of $PDO(n)$, accompanied by a certain multiplier:

$\displaystyle\lambda_{k}\sum_{n=0}^{\infty}PDO(2^{k}n)q^{n},$

as a polynomial in the Hauptmodul $\xi$ on the classical modular curve
$X_{0}(6)$ of genus $0$. We then complete our analysis on these functions in
order to prove Theorem 1.

This paper is organized as follows: Sect. 2 is devoted to proving several
required modular equations. In particular, one important component of this
section, as discussed in Sect. 2.2, concerns the representation of the degree
two unitizations $\zeta_{i,j}=U\big{(}\kappa^{i}\xi^{j}\big{)}$ in
$\mathbb{Z}[\xi]$ for arbitrary exponents $i$ and $j$, where $\kappa$ is one
of the auxiliary functions we introduced and $\xi$ is the aforementioned
Hauptmodul. The next two sections will then be devoted to the $2$-adic
behavior for these $\zeta_{i,j}$ series. Recall that in Theorem 1, we are
indeed considering internal congruences for $PDO(n)$. Hence, we introduce
another family of auxiliary functions in Sect. 5:

$\displaystyle\lambda^{\prime}_{k}\sum_{n=0}^{\infty}\big{(}PDO(2^{k+2}n)-PDO(2^{k}n)\big{)}q^{n},$

so as to capture this internal nature. Here the new multipliers
$\lambda^{\prime}_{k}$ are closely related to the original $\lambda_{k}$. We
will then move on to the divisibility properties for the above new family of
series, and in particular, we offer our proof of Theorem 1 in Sect. 6. It is
notable that the construction of each $2$-dissection slice of our generating
function bears an entirely different nature to those studied in the past
literature, in the sense that the multipliers $\lambda_{k}$ are pairwise
distinct. This fact makes our $2$-adic analysis far more complicated but in
the meantime very unique. We present a discussion of the difference between
our machinery and past work in Sect. 7.

##  2\. Modular equations

In this section, we collect a number of necessary modular relations that will
be utilized in the sequel.

###  2.1. Modular relations for $\gamma$ and $\xi$

Let us begin with the functions $\gamma$ and $\xi$. It is clear that both
$\gamma^{6}$ and $\xi$ are modular functions on the classical modular curve
$X_{0}(6)$.

######  Theorem 3.

We have

$\displaystyle\gamma^{6}$
$\displaystyle=59049\xi^{10}-262440\xi^{11}+466560\xi^{12}-414720\xi^{13}$
$\displaystyle\quad+184320\xi^{14}-32768\xi^{15}.$ (2.1)

###### Proof.

We only need to analyze the order of $\gamma^{6}$ and $\xi$ at each of the
cusps (cf. [13, p. 18, Theorem 1.65]):

$\displaystyle\operatorname{ord}_{0}\gamma^{6}$ $\displaystyle=5,$
$\displaystyle\operatorname{ord}_{0}\xi$ $\displaystyle=0,$
$\displaystyle\operatorname{ord}_{1/2}\gamma^{6}$ $\displaystyle=10,$
$\displaystyle\operatorname{ord}_{1/2}\xi$ $\displaystyle=1,$
$\displaystyle\operatorname{ord}_{1/3}\gamma^{6}$ $\displaystyle=-15,$
$\displaystyle\operatorname{ord}_{1/3}\xi$ $\displaystyle=-1,$
$\displaystyle\operatorname{ord}_{\infty}\gamma^{6}$ $\displaystyle=0,$
$\displaystyle\operatorname{ord}_{\infty}\xi$ $\displaystyle=0.$

We see that both functions have a pole at the cusp $[\tfrac{1}{3}]_{6}$, with
the pole for $\xi$ being simple. Since $X_{0}(6)$ has genus $0$, we can write
$\gamma^{6}$ as a polynomial in $\xi$ of degree $15$, as given above. A more
streamlined computer-aided analysis could be achieved automatically by
Garvan’s Maple package ETA [8]. ∎

###  2.2. Modular relations for $\kappa$ and $\xi$

Our objective in this subsection is as follows:

######  Theorem 4.

For any $i,j\geq 0$,

$\displaystyle U\big{(}\kappa^{i}\xi^{j}\big{)}\in\mathbb{Z}[\xi].$ (2.2)

We briefly postpone the proof of Theorem 4 in order to complete some necessary
analysis.

####  2.2.1. Initial cases

Let us focus on the following five initial relations:

######  Theorem 5.

We have

$\displaystyle U\big{(}\kappa\big{)}$
$\displaystyle=5\xi^{3}-20\xi^{4}+16\xi^{5},$ (2.3) $\displaystyle
U\big{(}\xi\big{)}$ $\displaystyle=5\xi-4\xi^{2},$ (2.4) $\displaystyle
U\big{(}\kappa^{2}\big{)}$
$\displaystyle=-\xi^{5}+50\xi^{6}-400\xi^{7}+1120\xi^{8}-1280\xi^{9}+512\xi^{10},$
(2.5) $\displaystyle U\big{(}\kappa\xi\big{)}$
$\displaystyle=3\xi^{3}-18\xi^{4}+16\xi^{5},$ (2.6) $\displaystyle
U\big{(}\xi^{2}\big{)}$ $\displaystyle=-9\xi+58\xi^{2}-80\xi^{3}+32\xi^{4}.$
(2.7)

###### Proof.

These results can be shown by standard techniques from the theory of modular
cusp analysis. Here we shall turn to a computer-aided proof by applying
Smoot’s Mathematica implementation RaduRK [16] of the Radu–Kolberg algorithm
[14]. For example, with the RaduRK package, we can express
$U\big{(}\xi\big{)}$ as a multiplier times a polynomial in a Hauptmodul
$t=t(q)$ on $X_{0}(12)$ that has a pole only at the cusp $[\infty]_{12}$:

$\displaystyle
U\big{(}\xi\big{)}\cdot\frac{E(q^{3})^{12}E(q^{4})^{4}}{q^{4}E(q)^{4}E(q^{12})^{12}}=15t-t^{2}+t^{3}+t^{4},$

where

$\displaystyle t=\frac{E(q^{4})^{4}E(q^{6})^{2}}{qE(q^{2})^{2}E(q^{12})^{4}}.$

Now to show the above expression equals $5\xi-4\xi^{2}$ as claimed in (2.4),
we only need to examine that the alleged linear combination of eta-products is
identical to $0$, i.e.,

$\displaystyle\big{(}5\xi-4\xi^{2}\big{)}-\big{(}15t-t^{2}+t^{3}+t^{4}\big{)}\cdot\frac{q^{4}E(q)^{4}E(q^{12})^{12}}{E(q^{3})^{12}E(q^{4})^{4}}=0.$

This task can be performed readily by Garvan’s Maple package ETA [8], as
pointed out in the proof of Theorem 3. The remaining identities can be proven
in the same way. ∎

####  2.2.2. Recurrences

We start by considering two generic formal power series $\alpha=\alpha(q)$ and
$\beta=\beta(q)$ such that each of $U\big{(}\alpha\big{)}$ and
$U\big{(}\alpha^{2}\big{)}$ is representable as a _polynomial_ with _rational_
(usually _integer_) coefficients in a generic formal power series
$\rho=\rho(q)$. Now we define

$\displaystyle\sigma_{\alpha,1}$ $\displaystyle:=\alpha(q)+\alpha(-q)$
$\displaystyle\;=2U\big{(}\alpha\big{)},$ $\displaystyle\sigma_{\alpha,2}$
$\displaystyle:=\alpha(q)\alpha(-q)$
$\displaystyle\;=\tfrac{1}{2}\big{[}\big{(}\alpha(q)+\alpha(-q)\big{)}^{2}-\big{(}\alpha(q)^{2}+\alpha(-q)^{2}\big{)}\big{]}$
$\displaystyle\;=2U\big{(}\alpha\big{)}^{2}-U\big{(}\alpha^{2}\big{)}.$

Clearly, both $\sigma_{\alpha,1}$ and $\sigma_{\alpha,2}$ are in
$\mathbb{Q}[\rho]$. Meanwhile, writing $\alpha_{0}=\alpha(q)$ and
$\alpha_{1}=\alpha(-q)$, then $X=\alpha_{0}$ and $\alpha_{1}$ are the two
roots of

$\displaystyle\big{(}X-\alpha(q)\big{)}\big{(}X-\alpha(-q)\big{)}=X^{2}-\sigma_{\alpha,1}X+\sigma_{\alpha,2}.$

That is, for $t=0,1$,

$\displaystyle\alpha_{t}^{2}-\sigma_{\alpha,1}\alpha_{t}+\sigma_{\alpha,2}=0.$

Let $\beta_{0}=\beta(q)$ and $\beta_{1}=\beta(-q)$. Now we see that, for
$k\geq 2$,

$\displaystyle 2U\big{(}\alpha^{k}\beta\big{)}$
$\displaystyle=\alpha_{0}^{k}\beta_{0}+\alpha_{1}^{k}\beta_{1}$
$\displaystyle=\big{(}\sigma_{\alpha,1}\alpha_{0}^{k-1}-\sigma_{\alpha,2}\alpha_{0}^{k-2}\big{)}\beta_{0}+\big{(}\sigma_{\alpha,1}\alpha_{1}^{k-1}-\sigma_{\alpha,2}\alpha_{1}^{k-2}\big{)}\beta_{1}$
$\displaystyle=2\sigma_{\alpha,1}U\big{(}\alpha^{k-1}\beta\big{)}-2\sigma_{\alpha,2}U\big{(}\alpha^{k-2}\beta\big{)}.$

Namely,

$\displaystyle
U\big{(}\alpha^{k}\beta\big{)}=\sigma_{\alpha,1}U\big{(}\alpha^{k-1}\beta\big{)}-\sigma_{\alpha,2}U\big{(}\alpha^{k-2}\beta\big{)}.$

Hence, if $U\big{(}\beta\big{)}$ and $U\big{(}\alpha\beta\big{)}$ are also in
$\mathbb{Q}[\rho]$, we obtain recursively that
$U\big{(}\alpha^{k}\beta\big{)}\in\mathbb{Q}[\rho]$ for all $k\geq 0$.

Now moving back to our scenario, we define for $i,j\geq 0$,

$\displaystyle\zeta_{i,j}:=U\big{(}\kappa^{i}\xi^{j}\big{)}.$ (2.8)

######  Theorem 6.

For any $i\geq 2$ and $j\geq 0$,

$\displaystyle\zeta_{i,j}=\big{(}10\xi^{3}-40\xi^{4}+32\xi^{5}\big{)}\cdot\zeta_{i-1,j}-\big{(}\xi^{5}\big{)}\cdot\zeta_{i-2,j}.$
(2.9)

Also, for any $i\geq 0$ and $j\geq 2$,

$\displaystyle\zeta_{i,j}=\big{(}10\xi-8\xi^{2}\big{)}\cdot\zeta_{i,j-1}-\big{(}9\xi-8\xi^{2}\big{)}\cdot\zeta_{i,j-2}.$
(2.10)

######  Remark 1.

We may combine the two recurrences (2.9) and (2.10) and derive that for
$i,j\geq 2$,

$\displaystyle\zeta_{i,j}$
$\displaystyle=\big{(}10\xi-8\xi^{2}\big{)}\big{(}10\xi^{3}-40\xi^{4}+32\xi^{5}\big{)}\cdot\zeta_{i-1,j-1}$
$\displaystyle\quad-\big{(}9\xi-8\xi^{2}\big{)}\big{(}10\xi^{3}-40\xi^{4}+32\xi^{5}\big{)}\cdot\zeta_{i-1,j-2}$
$\displaystyle\quad-\big{(}10\xi-8\xi^{2}\big{)}\big{(}\xi^{5}\big{)}\cdot\zeta_{i-2,j-1}$
$\displaystyle\quad+\big{(}9\xi-8\xi^{2}\big{)}\big{(}\xi^{5}\big{)}\cdot\zeta_{i-2,j-2}.$
(2.11)

###### Proof.

Let us first choose $(\alpha,\beta,\xi)\mapsto(\kappa,\xi^{j},\xi)$ with
$j\geq 0$. It is clear from (2.3) and (2.5) that

$\displaystyle\sigma_{\kappa,1}$
$\displaystyle=10\xi^{3}-40\xi^{4}+32\xi^{5},$
$\displaystyle\sigma_{\kappa,2}$ $\displaystyle=\xi^{5}.$

Hence, (2.9) follows. In the same fashion, we choose
$(\alpha,\beta,\xi)\mapsto(\xi,\kappa^{i},\xi)$ with $i\geq 0$. By (2.3) and
(2.5), we compute that

$\displaystyle\sigma_{\xi,1}$ $\displaystyle=10\xi-8\xi^{2},$
$\displaystyle\sigma_{\xi,2}$ $\displaystyle=9\xi-8\xi^{2},$

and therefore, (2.10) is true. ∎

Now we are in a position to complete the proof of Theorem 4.

###### Proof of Theorem 4.

With Theorem 5 in hand, we currently have two sets of initial relations for
the recurrence (2.9). Namely, $\\{\zeta_{0,0},\zeta_{1,0}\\}$ gives us the
representation of each $\zeta_{i,0}$ in terms of $\xi$, while
$\\{\zeta_{0,1},\zeta_{1,1}\\}$ gives us the representation of each
$\zeta_{i,1}$. With these recipes, (2.10) further produces the representation
of each $\zeta_{i,j}$ in $\mathbb{Z}[\xi]$, thereby confirming (2.2). ∎

###  2.3. Modular relations for $\Lambda$ and $\xi$

We begin with a relation connecting $\gamma(q^{2})\delta(q)^{2}$ and $\xi(q)$.

######  Theorem 7.

We have

$\displaystyle
U\big{(}\gamma(q^{2})\delta(q)^{2}\big{)}=3\xi(q)^{2}-2\xi(q)^{3}.$ (2.12)

###### Proof.

This relation can be shown in a way similar to that for Theorem 5. ∎

Now we move to relations for $\Lambda_{k}$ and $\xi$ for each $k\geq 2$.

######  Theorem 8.

For any $k\geq 2$,

$\displaystyle\Lambda_{k}\in\mathbb{Z}[\xi].$ (2.13)

More precisely, if we write

$\displaystyle\Lambda_{k}:=\sum_{m}c_{k}(m)\xi^{m},$ (2.14)

then

$\displaystyle\Lambda_{2}=3\xi^{2}-2\xi^{3},$ (2.15)

and for $k\geq 3$, we recursively have

$\displaystyle\Lambda_{k}=\sum_{\ell}c_{k-1}(\ell)\cdot\zeta_{2^{k-3},\ell},$
(2.16)

where $\zeta_{2^{k-3},\ell}$ is given by (2.8).

###### Proof.

We begin with the proof of (2.15). It was already shown in [2, Theorem 21]
that

$\displaystyle\sum_{n=0}^{\infty}PDO(2n)q^{n}=\delta(q)^{2}.$

Thus,

$\displaystyle\Lambda_{2}$
$\displaystyle=\gamma(q)\sum_{n=0}^{\infty}PDO(4n)q^{n}=U\left(\gamma(q^{2})\sum_{n=0}^{\infty}PDO(2n)q^{n}\right)=U\big{(}\gamma(q^{2})\delta(q)^{2}\big{)}.$

Invoking (2.12) gives the claimed expression for $\Lambda_{2}$.

For (2.16), we make use of the fact that, for $k\geq 3$,

$\displaystyle\Lambda_{k}$
$\displaystyle=\gamma(q)^{2^{k-2}}\sum_{n=0}^{\infty}PDO(2^{k}n)q^{n}$
$\displaystyle=U\left(\gamma(q^{2})^{2^{k-2}}\sum_{n=0}^{\infty}PDO(2^{k-1}n)q^{n}\right)$
$\displaystyle=U\left(\left(\frac{\gamma(q^{2})^{2}}{\gamma(q)}\right)^{2^{k-3}}\gamma(q)^{2^{k-3}}\sum_{n=0}^{\infty}PDO(2^{k-1}n)q^{n}\right)$
$\displaystyle=U\left(\left(\frac{\gamma(q^{2})^{2}}{\gamma(q)}\right)^{2^{k-3}}\Lambda_{k-1}\right).$

Noting that $\kappa=\gamma(q^{2})^{2}/\gamma(q)$ and writing $\Lambda_{k-1}$
in the above as a polynomial in $\xi$ by virtue of (2.14), we finally obtain
that

$\displaystyle\Lambda_{k}=\sum_{\ell}c_{k-1}(\ell)U\left(\kappa^{2^{k-3}}\xi^{\ell}\right).$

Recalling (2.8), the required result follows. ∎

######  Example 1.

We give a few examples to illustrate what $\Lambda_{k}$ looks like when $k\geq
3$:

  1. (1).

In light of the recurrences in Sect. 2.2.2, it is plain that

$\displaystyle\zeta_{1,2}$ $\displaystyle=-15\xi^{4}+16\xi^{5},$
$\displaystyle\zeta_{1,3}$ $\displaystyle=-27\xi^{4}+36\xi^{5}-8\xi^{6}.$

Hence, from the relation that $\Lambda_{2}=3\xi^{2}-2\xi^{3}$, we have

$\displaystyle\Lambda_{3}$ $\displaystyle=3\zeta_{1,2}-2\zeta_{1,3}$
$\displaystyle=3\big{(}{-15}\xi^{4}+16\xi^{5}\big{)}-2\big{(}{-27}\xi^{4}+36\xi^{5}-8\xi^{6}\big{)},$

thereby giving us

$\displaystyle\Lambda_{3}$ $\displaystyle=9\xi^{4}-24\xi^{5}+16\xi^{6}.$
(2.17)

  2. (2).

In the same vein,

$\displaystyle\zeta_{2,4}$
$\displaystyle=-81\xi^{7}+594\xi^{8}-1024\xi^{9}+512\xi^{10},$
$\displaystyle\zeta_{2,5}$ $\displaystyle=405\xi^{8}-900\xi^{9}+496\xi^{10},$
$\displaystyle\zeta_{2,6}$
$\displaystyle=729\xi^{8}-1944\xi^{9}+1728\xi^{10}-640\xi^{11}+128\xi^{12}.$

Therefore,

$\displaystyle\Lambda_{4}$
$\displaystyle=-729\xi^{7}+7290\xi^{8}-18720\xi^{9}+20352\xi^{10}$
$\displaystyle\quad-10240\xi^{11}+2048\xi^{12}.$ (2.18)

  3. (3).

With a lengthier computation, we have

$\displaystyle\Lambda_{5}$
$\displaystyle=34543665\xi^{14}-400588416\xi^{15}+2073171024\xi^{16}-6214952448\xi^{17}$
$\displaystyle\quad+11906611200\xi^{18}-15261990912\xi^{19}+13313703936\xi^{20}$
$\displaystyle\quad-7841251328\xi^{21}+2994733056\xi^{22}-671088640\xi^{23}$
$\displaystyle\quad+67108864\xi^{24}.$ (2.19)

##  3\. Minimal $\xi$-power in $\zeta$

For each $i,j\geq 0$, let the coefficients $Z_{i,j}(m)$ with $m\geq 0$ be such
that

$\displaystyle\zeta_{i,j}:=\sum_{m}Z_{i,j}(m)\xi^{m}.$

It is notable that $Z_{i,j}(m)$ eventually vanishes as
$\zeta_{i,j}\in\mathbb{Z}[\xi]$, so the above summation is indeed finite.

From the evaluations in Sect. 2.2, we have also seen that for each
$\zeta_{i,j}$ as a polynomial in $\xi$, the terms $\xi^{m}$ with a lower
degree usually vanish. In the next theorem, we characterize the minimal
$\xi$-power in the polynomial expression of $\zeta_{i,j}$.

######  Theorem 9.

For any $i,j\geq 0$, define

$\displaystyle d_{i,j}:=\begin{cases}5I+J,&\text{if $(i,j)=(2I,2J)$},\\\
5I+J+1,&\text{if $(i,j)=(2I,2J+1)$},\\\ 5I+J+3,&\text{if
$(i,j)=(2I+1,2J)$},\\\ 5I+J+3,&\text{if $(i,j)=(2I+1,2J+1)$}.\end{cases}$

Then for any $m$ with $0\leq m<d_{i,j}$, we have

$\displaystyle Z_{i,j}(m)=0.$

Furthermore, the coefficient $Z_{i,j}(d_{i,j})$ is an odd integer.

###### Proof.

Clearly, $\zeta_{0,0}=1$, from which we find that it starts with the power
$\xi^{0}$ with $Z_{0,0}(d_{0,0})=Z_{0,0}(0)=1$ being odd. We further know from
(2.3) that $\zeta_{1,0}$ starts with the power $5\xi^{3}$, while
$Z_{1,0}(d_{1,0})=Z_{1,0}(3)=5$ is also odd. Inductively, it follows from the
recurrence (2.9) that $\zeta_{2I+2,0}$ starts with the power
$Z_{2I+2,0}(5I+5)\xi^{5I+5}$ with

$\displaystyle Z_{2I+2,0}(d_{2I+2,0})$ $\displaystyle=Z_{2I+2,0}(5I+5)$
$\displaystyle=-Z_{2I,0}(5I),$

which is an odd integer. Similarly, we deduce by the same recurrence that
$\zeta_{2I+3,0}$ starts with the power $Z_{2I+3,0}(5I+8)\xi^{5I+8}$ with

$\displaystyle Z_{2I+3,0}(d_{2I+3,0})$ $\displaystyle=Z_{2I+3,0}(5I+8)$
$\displaystyle=10Z_{2I+2,0}(5I+5)-Z_{2I+1,0}(5I+3),$

again being odd.

In the same fashion, we find from (2.4) that $\zeta_{0,1}$ starts with the
power $5\xi^{1}$ with an odd coefficient $5$, and from (2.6) that
$\zeta_{1,1}$ starts with the power $3\xi^{3}$ also with its coefficient $3$
being odd. By induction under the rule of the recurrence (2.9), it follows
that $\zeta_{2I+2,1}$ starts with the power $Z_{2I+2,1}(5I+6)\xi^{5I+6}$,
where the coefficient is

$\displaystyle Z_{2I+2,1}(5I+6)=10Z_{2I+1,1}(5I+3)-Z_{2I,1}(5I+1),$

and it is an odd integer. Also, $\zeta_{2I+3,1}$ starts with the power
$Z_{2I+3,1}(5I+8)\xi^{5I+8}$, where the coefficient is the odd integer

$\displaystyle Z_{2I+3,1}(5I+8)=-Z_{2I+1,1}(5I+3).$

Now we have shown the desired result for each $\zeta_{i,0}$ and $\zeta_{i,1}$,
and we will then apply induction on $j$. In light of the recurrence (2.10), we
find that $\zeta_{2I,2J+2}$ starts with the power
$Z_{2I,2J+2}(5I+J+1)\xi^{5I+J+1}$, where the coefficient is an odd integer
given by

$\displaystyle Z_{2I,2J+2}(5I+J+1)=-9Z_{2I,2J}(5I+J).$

Likewise, $\zeta_{2I,2J+3}$ starts with the power
$Z_{2I,2J+3}(5I+J+2)\xi^{5I+J+2}$, where the coefficient is an odd integer
given by

$\displaystyle
Z_{2I,2J+3}(5I+J+2)=10Z_{2I,2J+2}(5I+J+1)-9Z_{2I,2J+1}(5I+J+1).$

Moreover, $\zeta_{2I+1,2J+2}$ starts with the power $Z_{2I+1,2J+2}(5I+J+4)$,
where the coefficient is

$\displaystyle
Z_{2I+1,2J+2}(5I+J+4)=10Z_{2I+1,2J+1}(5I+J+3)-9Z_{2I+1,2J}(5I+J+3),$

which is odd. Meanwhile, $\zeta_{2I+1,2J+3}$ starts with the power
$Z_{2I+1,2J+3}(5I+J+4)$, where the coefficient is

$\displaystyle Z_{2I+1,2J+3}(5I+J+4)=-9Z_{2I+1,2J+1}(5I+J+3),$

once again being odd. ∎

##  4\. $2$-Adic analysis for $\zeta$

With all of the above preparations in hand, we are now in a position to begin
thinking about the divisibility of various objects by powers of $2$.
Throughout the remainder of this work, we denote by $\nu(n)$ the _$2$ -adic
evaluation_ of $n$, that is, $\nu(n)$ is the _largest_ nonnegative integer
$\alpha$ such that $2^{\alpha}\mid n$. We also adopt the convention that
$\nu(0)=\infty$.

The following trivial result on $2$-adic evaluations will be frequently used:

######  Lemma 10.

Let $a$ and $b$ be two integers. Then

$\displaystyle\nu(a+b)\begin{cases}\,\,=\,\,\min\\{\nu(a),\nu(b)\\},&\text{if
$\nu(a)\neq\nu(b)$},\\\\[6.0pt] \,\,\geq\,\,2\nu(a)=2\nu(b),&\text{if
$\nu(a)=\nu(b)$}.\end{cases}$ (4.1)

Let us start by analyzing the $2$-adic behavior of the coefficients
$Z_{i,0}(m)$ for each $i\geq 0$ whenever $m\geq d_{i,0}$.

######  Theorem 11.

For any $i\geq 0$, we have

$\displaystyle\nu\big{(}Z_{i,0}(d_{i,0})\big{)}=0,$

and

$\displaystyle\nu\big{(}Z_{i,0}(d_{i,0}+1)\big{)}\begin{cases}=1,&\text{if
$i\equiv 2\bmod{4}$},\\\ \geq 2,&\text{if $i\not\equiv
2\bmod{4}$}.\end{cases}$

Furthermore, for $M\geq 2$,

$\displaystyle\nu\big{(}Z_{i,0}(d_{i,0}+M)\big{)}\geq M+1.$

###### Proof.

We first note that the theorem is true for $i=0$ and $1$ by the fact that
$\zeta_{0,0}=1$ and the relation given in (2.3), respectively. Hence, we may
apply induction to prove the required result for $i=4I+2$, $4I+3$, $4I+4$ and
$4I+5$ with the assumption that it holds for $i=4I+0$ and $4I+1$.

The $i=4I+2$ case can be illustrated by the following table:

Here the last column holds for any $M\geq 10$. Recalling the recurrence (2.9),
we have

$\displaystyle\zeta_{4I+2,0}=\big{(}10\xi^{3}-40\xi^{4}+32\xi^{5}\big{)}\cdot\zeta_{4I+1,0}-\big{(}\xi^{5}\big{)}\cdot\zeta_{4I+0,0}.$

Hence, the third line provides the $2$-adic evaluations of the coefficients
$Z_{4I+2,0}$ contributed from $\big{(}\xi^{5}\big{)}\cdot\zeta_{4I+0,0}$,
while the fourth line provides the contribution from
$\big{(}10\xi^{3}-40\xi^{4}+32\xi^{5}\big{)}\cdot\zeta_{4I+1,0}$. For example,
the $2$-adic evaluation of the coefficient of the $\xi^{d_{4I+0,0}+5}$ term in
$\big{(}\xi^{5}\big{)}\cdot\zeta_{4I+0,0}$ is clearly $0$, while in
$\big{(}10\xi^{3}-40\xi^{4}+32\xi^{5}\big{)}\cdot\zeta_{4I+1,0}$, the power
$\xi^{d_{4I+0,0}+5}$ vanishes, thereby having coefficient $0$ and $2$-adic
evaluation $\infty$. Consequently,

$\displaystyle\nu\big{(}Z_{4I+2,0}(d_{4I+0,0}+5)\big{)}=0.$

By Theorem 9, we have $d_{4I+2,0}=d_{4I+0,0}+5$, so as to give us

$\displaystyle\nu\big{(}Z_{4I+2,0}(d_{4I+2,0})\big{)}=0.$

Likewise, the $2$-adic evaluation of the coefficient of the
$\xi^{d_{4I+0,0}+6}$ term in $\big{(}\xi^{5}\big{)}\cdot\zeta_{4I+0,0}$ is
$\geq 2$, while in
$\big{(}10\xi^{3}-40\xi^{4}+32\xi^{5}\big{)}\cdot\zeta_{4I+1,0}$, the
corresponding $2$-adic evaluation is $1$. So we have

$\displaystyle\nu\big{(}Z_{4I+2,0}(d_{4I+0,0}+6)\big{)}=\min\\{\geq 2,1\\}=1,$

thereby yielding that

$\displaystyle\nu\big{(}Z_{4I+2,0}(d_{4I+2,0}+1)\big{)}=1.$

This process can be continued to all remaining coefficients $Z_{4I+2,0}$.

For $i=4I+3$, we shall make use of the following table and argue in the same
vein:

For $i=4I+4$, the required table is

It is notable that for the $2$-adic evaluation of

$\displaystyle\nu\big{(}Z_{4I+4,0}(d_{4I+4,0}+1)\big{)}=\nu\big{(}Z_{4I+4,0}(d_{4I+2,0}+6)\big{)},$

we shall use the second case of (4.1) so as to get

$\displaystyle\nu\big{(}Z_{4I+4,0}(d_{4I+2,0}+6)\big{)}\geq 2\cdot 1=2,$

as given in the table.

Finally, for $i=4I+5$, we require the table:

and then perform a similar analysis to that for the above $i=4I+2$ case. ∎

In the same fashion, we have parallel results for $Z_{i,1}(m)$.

######  Theorem 12.

For any $i\geq 0$, we have

$\displaystyle\nu\big{(}Z_{i,1}(d_{i,1})\big{)}=0,$

and

$\displaystyle\nu\big{(}Z_{i,1}(d_{i,1}+1)\big{)}\begin{cases}=1,&\text{if
$i\equiv 1\bmod{4}$},\\\ \geq 2,&\text{if $i\not\equiv
1\bmod{4}$}.\end{cases}$

Furthermore, for $M\geq 2$,

$\displaystyle\nu\big{(}Z_{i,1}(d_{i,1}+M)\big{)}\geq M+1.$

###### Proof.

By (2.4) and (2.6), the theorem holds true for $i=0$ and $1$. We may then
apply a similar inductive argument to that for Theorem 11. ∎

Now we are ready to perform the $2$-adic evaluations for the coefficients
$Z_{2^{k},j}(m)$ for each $k\geq 0$ and $j\geq 0$ whenever $m\geq
d_{2^{k},j}$.

######  Theorem 13.

For any $k\geq 2$ and $j\geq 0$, we have

$\displaystyle\nu\big{(}Z_{2^{k},j}(d_{2^{k},j})\big{)}=0,$

and

$\displaystyle\nu\big{(}Z_{2^{k},j}(d_{2^{k},j}+1)\big{)}\begin{cases}=1,&\text{if
$j\equiv 2\bmod{4}$},\\\ \geq 2,&\text{if $j\not\equiv
2\bmod{4}$}.\end{cases}$

Furthermore, for $M\geq 2$,

$\displaystyle\nu\big{(}Z_{2^{k},j}(d_{2^{k},j}+M)\big{)}\geq M+1.$

###### Proof.

In view of Theorems 11 and 12, it is known that the results are true for
$Z_{2^{k},0}(m)$ and $Z_{2^{k},1}(m)$ with any $k\geq 2$. Now we apply
induction on $j$ and prove for $j=4J+2$, $4J+3$, $4J+4$ and $4J+5$ under the
assumption of validity for $j=4J+0$ and $4J+1$. Here a similar strategy to
that for Theorem 11 will be used, with (2.10) being invoked:

$\displaystyle\zeta_{2^{k},j}=\big{(}10\xi-8\xi^{2}\big{)}\cdot\zeta_{2^{k},j-1}-\big{(}9\xi-8\xi^{2}\big{)}\cdot\zeta_{2^{k},j-2}.$

For $j=4J+2$, we require this table:

For $j=4J+3$, we require this table:

For $j=4J+4$, we require this table:

For $j=4J+5$, we require this table:

Concrete analyses can be mimicked by consulting the $i=4I+2$ case in the proof
of Theorem 11, and we will omit the details. ∎

##  5\. New auxiliary functions and the associated minimal $\xi$-powers

All of the work above has revolved around the generating function for the
function $PDO(n)$. However, we keep in mind that Theorem 1 is really focused
on the internal congruences for the $PDO$ function. To capture this nature,
let us introduce a new family of auxiliary functions for $k\geq 3$,

$\displaystyle\Phi_{k}=\Phi_{k}(q):=\gamma(q)^{2^{k}}\left(\sum_{n=0}^{\infty}PDO(2^{k+2}n)q^{n}-\sum_{n=0}^{\infty}PDO(2^{k}n)q^{n}\right).$

In light of (1.6), we have

$\displaystyle\Phi_{k}$ $\displaystyle=\Lambda_{k+2}-\gamma^{3\cdot
2^{k-2}}\Lambda_{k}$
$\displaystyle=\Lambda_{k+2}-\left(\gamma^{6}\right)^{2^{k-3}}\Lambda_{k}.$

######  Theorem 14.

For any $k\geq 3$,

$\displaystyle\Phi_{k}\in\mathbb{Z}[\xi].$ (5.1)

More precisely, if we write

$\displaystyle\Phi_{k}:=\sum_{m}F_{k}(m)\xi^{m},$ (5.2)

then

$\displaystyle\Phi_{3}$
$\displaystyle=34012224\xi^{14}-396809280\xi^{15}+2061728640\xi^{16}-6195823488\xi^{17}$
$\displaystyle\quad+11887534080\xi^{18}-15250636800\xi^{19}+13309968384\xi^{20}$
$\displaystyle\quad-7840727040\xi^{21}+2994733056\xi^{22}-671088640\xi^{23}$
$\displaystyle\quad+67108864\xi^{24},$ (5.3)

and for $k\geq 4$, we recursively have

$\displaystyle\Phi_{k}=\sum_{\ell}F_{k-1}(\ell)\cdot\zeta_{2^{k-1},\ell},$
(5.4)

where $\zeta_{2^{k-1},\ell}$ is given by (2.8).

###### Proof.

Since both $\Lambda_{k}$ and $\Lambda_{k+2}$ are in $\mathbb{Z}[\xi]$ by
(2.13), while $\gamma^{6}$ is also in $\mathbb{Z}[\xi]$ as we have shown in
(3), it follows that $\Phi_{k}\in\mathbb{Z}[\xi]$. In particular,
$\Phi_{3}=\Lambda_{5}-\gamma^{6}\Lambda_{3}$. Applying (2.17) and ((3). )
together with (3) gives (14). For (5.4), we note that

$\displaystyle\Phi_{k}$
$\displaystyle=U\left(\gamma(q^{2})^{2^{k}}\left(\sum_{n=0}^{\infty}PDO(2^{k+1}n)q^{n}-\sum_{n=0}^{\infty}PDO(2^{k-1}n)q^{n}\right)\right)$
$\displaystyle=U\left(\left(\frac{\gamma(q^{2})^{2}}{\gamma(q)}\right)^{2^{k-1}}\gamma(q)^{2^{k-1}}\left(\sum_{n=0}^{\infty}PDO(2^{k+1}n)q^{n}-\sum_{n=0}^{\infty}PDO(2^{k-1}n)q^{n}\right)\right)$
$\displaystyle=U\left(\kappa^{2^{k-1}}\Phi_{k-1}\right).$

Finally, we recall (5.2) and invoke (2.8) to obtain the desired recurrence. ∎

Next, in analogy to Theorem 9, we show that the lower powers of $\xi$ in each
$\Phi_{k}$ shall vanish.

######  Theorem 15.

For any $k\geq 3$, define

$\displaystyle\tau_{k}:=\begin{cases}7\cdot
2^{2K-3}-\tfrac{2}{3}\big{(}4^{K-2}-1\big{)},&\text{if $k=2K-1$},\\\\[6.0pt]
7\cdot 2^{2K-2}-\tfrac{1}{3}\big{(}4^{K-1}-1\big{)},&\text{if
$k=2K$}.\end{cases}$

Then for any $m$ with $0\leq m<\tau_{k}$, we have

$\displaystyle F_{k}(m)=0.$

######  Remark 2.

A straightforward computation reveals that

$\displaystyle\tau_{2K-1}$ $\displaystyle\equiv 2\pmod{4},$ (5.5)
$\displaystyle\tau_{2K}$ $\displaystyle\equiv 3\pmod{4},$ (5.6)

for any choice of $K\geq 2$.

###### Proof.

From (14), we see that $\Phi_{3}$ starts with the power $\xi^{14}$, while

$\displaystyle 14=7\cdot 2^{1}-\tfrac{2}{3}\big{(}4^{0}-1\big{)}.$

Now we assume that the theorem is true for a certain $k=2K-1$, and we prove
inductively for $k=2K$ and $2K+1$.

For $k=2K$, we know from (5.4) that

$\displaystyle\Phi_{2K}=F_{2K-1}(\tau_{2K-1})\cdot\zeta_{2^{2K-1},\tau_{2K-1}}+\cdots.$
(5.7)

By virtue of Theorem 9, $\zeta_{2^{2K-1},\tau_{2K-1}}$ starts with the power
$\xi^{d}$ where

$\displaystyle d$ $\displaystyle=d_{2^{2K-1},\tau_{2K-1}}$
$\displaystyle=5\cdot 2^{2K-2}+\tfrac{1}{2}\tau_{2K-1}$ $\displaystyle=5\cdot
2^{2K-2}+7\cdot 2^{2K-4}-\tfrac{1}{3}\big{(}4^{K-2}-1\big{)}$
$\displaystyle=7\cdot 2^{2K-2}-\tfrac{1}{3}\big{(}4^{K-1}-1\big{)}$
$\displaystyle=\tau_{2K}.$

Here we make use of the fact that both $2^{2K-1}$ and $\tau_{2K-1}$ are even.
In the meantime, each of the $\zeta\in\mathbb{Z}[\xi]$ component in the
remaining summands in (5.7) starts with a power higher than $\xi^{d}$. Hence,
$\Phi_{2K}$ starts with _at least_ $\xi^{\tau_{2K}}$.

For $k=2K+1$, we also deduce from (5.4) that

$\displaystyle\Phi_{2K+1}=F_{2K}(\tau_{2K})\cdot\zeta_{2^{2K},\tau_{2K}}+F_{2K}(\tau_{2K}+1)\cdot\zeta_{2^{2K},\tau_{2K}+1}+\cdots.$
(5.8)

Invoking Theorem 9 and noting that $\tau_{2K}$ is odd, it follows that
$\zeta_{2^{2K},\tau_{2K}}$ starts with the power $\xi^{d}$ where

$\displaystyle d$ $\displaystyle=d_{2^{2K},\tau_{2K}}$ $\displaystyle=5\cdot
2^{2K-1}+\tfrac{1}{2}\big{(}\tau_{2K}-1\big{)}+1$ $\displaystyle=5\cdot
2^{2K-1}+7\cdot 2^{2K-3}-\tfrac{1}{6}\big{(}4^{K-1}-1\big{)}+\tfrac{1}{2}$
$\displaystyle=7\cdot 2^{2K-1}-\tfrac{2}{3}\big{(}4^{K-1}-1\big{)}$
$\displaystyle=\tau_{2K+1}.$

For the second summand in (5.8), we find that $\zeta_{2^{2K},\tau_{2K}+1}$
starts with the power $\xi^{d^{\prime}}$ where

$\displaystyle d^{\prime}$ $\displaystyle=d_{2^{2K},\tau_{2K}+1}$
$\displaystyle=5\cdot 2^{2K-1}+\tfrac{1}{2}\big{(}\tau_{2K}+1\big{)}$
$\displaystyle=\tau_{2K+1},$

according to a similar computation. Furthermore, each of the
$\zeta\in\mathbb{Z}[\xi]$ components in the remaining summands in (5.8) starts
with a power higher than $\xi^{d}=\xi^{d^{\prime}}$. Hence, we can claim that
$\Phi_{2K+1}$ starts with _at least_ $\xi^{\tau_{2K+1}}$. ∎

##  6\. $2$-Adic analysis for $\Phi$

We are now in a position to prove our main result, Theorem 1. To do so, we
only need to confirm that for each $K\geq 1$,

$\displaystyle\nu\big{(}F_{2K+1}(m)\big{)}\geq 2K+3$

whenever $m\geq\tau_{2K+1}$. In what follows, we first manually analyze the
initial cases where $K\in\\{1,2\\}$ and then move on to general $K$ by
induction.

###  6.1. Initial cases

Recall that $\Phi_{3}$ was already formulated in (14). Meanwhile, we may
obtain an explicit expression in $\mathbb{Z}[\xi]$ (containing $43$ terms!)
for $\Phi_{5}$ by applying the recurrence (5.4) twice. Consequently, we get
the following $2$-adic evaluations, where $\tau$ stands for $\tau_{3}=14$ or
$\tau_{5}=54$ accordingly:

In the above table, the last column is true for all $M\geq 3$. So we indeed
have the following two congruences, with the former being even stronger than
the general scenario in Theorem 1:

$\displaystyle PDO(2^{3}n)\equiv PDO(2^{5}n)\pmod{2^{6}},$ (6.1)
$\displaystyle PDO(2^{5}n)\equiv PDO(2^{7}n)\pmod{2^{7}}.$ (6.2)

###  6.2. Induction

Now we perform induction on $K\geq 2$ and establish the following lower bounds
for the $2$-adic evaluations.

######  Theorem 16.

For any $K\geq 2$, it is true that

$\displaystyle\nu\big{(}F_{2K+1}(\tau_{2K+1})\big{)}$ $\displaystyle\geq
2K+3,$ (6.3)

and that for $M\geq 1$,

$\displaystyle\nu\big{(}F_{2K+1}(\tau_{2K+1}+M)\big{)}$ $\displaystyle\geq
2K+M+2.$ (6.4)

Note that the $K=2$ case was already covered in Sect. 6.1. So in the sequel,
we first prove the inequality (6.4) for $K\geq 3$ under the inductive
assumption that it is true for $K-1$. For the sake of notational convenience,
let us denote

$\displaystyle\tau^{\prime\prime}:=\tau_{2K-1},\qquad\tau^{\prime}:=\tau_{2K},\qquad\tau:=\tau_{2K+1}.$

Also, we write

$\displaystyle\\{Z^{\prime\prime}(j,m):j,m\geq 0\\}$
$\displaystyle:=\\{Z_{2^{2K-1},j}(m):j,m\geq 0\\},$
$\displaystyle\\{Z^{\prime}(j,m):j,m\geq 0\\}$
$\displaystyle:=\\{Z_{2^{2K},j}(m):j,m\geq 0\\}.$

###### Proof of (6.4).

To produce $\Phi_{2K+1}$ from $\Phi_{2K-1}$, we need to employ the recurrence
(5.4) twice. Writing

$\displaystyle\Phi_{2K-1}=\sum_{M^{\prime\prime}\geq
0}F_{2K-1}(\tau^{\prime\prime}+M^{\prime\prime})\xi^{\tau^{\prime\prime}+M^{\prime\prime}},$

we deduce from (5.4) that

$\displaystyle\Phi_{2K}=\sum_{M^{\prime\prime}\geq
0}F_{2K-1}(\tau^{\prime\prime}+M^{\prime\prime})\zeta_{2^{2K-1},\tau^{\prime\prime}+M^{\prime\prime}}.$

Recall that $\tau^{\prime\prime}$ is even according to (5.5). It then follows
from Theorems 9 and 15 that the minimal degree of the $\xi$-powers in
$\zeta_{2^{2K-1},\tau^{\prime\prime}+M^{\prime\prime}}$ is
$\tau^{\prime}+\lfloor\tfrac{M^{\prime\prime}+1}{2}\rfloor$, i.e.,

$\displaystyle
d_{2^{2K-1},\tau^{\prime\prime}+M^{\prime\prime}}=\tau^{\prime}+\lfloor\tfrac{M^{\prime\prime}+1}{2}\rfloor.$
(6.5)

Hence,

$\displaystyle\Phi_{2K}=\sum_{\begin{subarray}{c}M^{\prime\prime}\geq 0\\\
M^{\prime}\geq\lfloor\frac{M^{\prime\prime}+1}{2}\rfloor\end{subarray}}F_{2K-1}(\tau^{\prime\prime}+M^{\prime\prime})Z^{\prime\prime}(\tau^{\prime\prime}+M^{\prime\prime},\tau^{\prime}+M^{\prime})\xi^{\tau^{\prime}+M^{\prime}}.$

Applying the recurrence (5.4) once again gives us that

$\displaystyle\Phi_{2K+1}=\sum_{\begin{subarray}{c}M^{\prime\prime}\geq 0\\\
M^{\prime}\geq\lfloor\frac{M^{\prime\prime}+1}{2}\rfloor\end{subarray}}F_{2K-1}(\tau^{\prime\prime}+M^{\prime\prime})Z^{\prime\prime}(\tau^{\prime\prime}+M^{\prime\prime},\tau^{\prime}+M^{\prime})\zeta_{2^{2K},\tau^{\prime}+M^{\prime}}.$

Noting that $\tau^{\prime}$ is odd according to (5.6), Theorems 9 and 15 then
imply that the minimal degree of the $\xi$-powers in
$\zeta_{2^{2K},\tau^{\prime}+M^{\prime}}$ is
$\tau+\lfloor\tfrac{M^{\prime}}{2}\rfloor$, i.e.,

$\displaystyle
d_{2^{2K},\tau^{\prime}+M^{\prime}}=\tau^{\prime}+\lfloor\tfrac{M^{\prime}}{2}\rfloor.$
(6.6)

Hence,

$\displaystyle\Phi_{2K+1}=\sum_{\begin{subarray}{c}M^{\prime\prime}\geq 0\\\
M^{\prime}\geq\lfloor\frac{M^{\prime\prime}+1}{2}\rfloor\\\
M\geq\lfloor\frac{M^{\prime}}{2}\rfloor\end{subarray}}C(M,M^{\prime\prime},M^{\prime\prime})\xi^{\tau+M},$

where

$\displaystyle
C(M,M^{\prime\prime},M^{\prime\prime}):=F_{2K-1}(\tau^{\prime\prime}+M^{\prime\prime})Z^{\prime\prime}(\tau^{\prime\prime}+M^{\prime\prime},\tau^{\prime}+M^{\prime})Z^{\prime}(\tau^{\prime}+M^{\prime},\tau+M).$

Note that to complete the inductive step, it is sufficient to show the
inequality

$\displaystyle\nu\big{(}C(M,M^{\prime\prime},M^{\prime\prime})\big{)}\geq
2K+M+2$ (6.7)

for every tuple $(M,M^{\prime\prime},M^{\prime\prime})$ such that
$M^{\prime\prime}\geq 0$,
$M^{\prime}\geq\lfloor\tfrac{M^{\prime\prime}+1}{2}\rfloor$ and
$M\geq\lfloor\tfrac{M^{\prime}}{2}\rfloor$.

We first consider the following two generic cases where (i).
$M^{\prime\prime}\geq 2$ and (ii). $M^{\prime\prime}=0$ or $1$ and
$M^{\prime}\geq 3$. By our inductive assumption,

$\displaystyle\nu\big{(}F_{2K-1}(\tau^{\prime\prime}+M^{\prime\prime})\big{)}\geq
2K+M^{\prime\prime}.$

Also, by a weaker form of Theorem 13 with recourse to (6.5) and (6.6),
respectively, we have

$\displaystyle\nu\big{(}Z^{\prime\prime}(\tau^{\prime\prime}+M^{\prime\prime},\tau^{\prime}+M^{\prime})\big{)}$
$\displaystyle\geq M^{\prime}-\lfloor\tfrac{M^{\prime\prime}+1}{2}\rfloor,$
$\displaystyle\nu\big{(}Z^{\prime}(\tau^{\prime}+M^{\prime},\tau+M)\big{)}$
$\displaystyle\geq M-\lfloor\tfrac{M^{\prime}}{2}\rfloor.$

It follows that

$\displaystyle\nu\big{(}C(M,M^{\prime\prime},M^{\prime\prime})\big{)}\geq
2K+M+\big{(}M^{\prime\prime}-\lfloor\tfrac{M^{\prime\prime}+1}{2}\rfloor\big{)}+\big{(}M^{\prime}-\lfloor\tfrac{M^{\prime}}{2}\rfloor\big{)}.$

Now (i). if $M^{\prime\prime}\geq 2$, then $M^{\prime}\geq 1$ so that
$M^{\prime\prime}-\lfloor\tfrac{M^{\prime\prime}+1}{2}\rfloor\geq 1$ and that
$M^{\prime}-\lfloor\tfrac{M^{\prime}}{2}\rfloor\geq 1$; (ii). if
$M^{\prime\prime}=0$ or $1$ and $M^{\prime}\geq 3$, then
$M^{\prime\prime}-\lfloor\tfrac{M^{\prime\prime}+1}{2}\rfloor=0$ but
$M^{\prime}-\lfloor\tfrac{M^{\prime}}{2}\rfloor\geq 2$. Thus, in both cases
the inequality (6.7) holds.

Now there are five sporadic cases to be investigated, and we work on them
separately. Note that for (6.4), we have the condition that $M\geq 1$.

  1. (a).

$(M^{\prime},M^{\prime\prime})=(0,0)$: In this case, it is known by the
inductive assumption,

$\displaystyle\nu\big{(}F_{2K-1}(\tau^{\prime\prime}+0)\big{)}\geq 2K+1,$

that by Theorem 13,

$\displaystyle\nu\big{(}Z^{\prime\prime}(\tau^{\prime\prime}+0,\tau^{\prime}+0)\big{)}=0,$

and that also by Theorem 13 (noting that $\tau^{\prime}+0\equiv 3\pmod{4}$),

$\displaystyle\nu\big{(}Z^{\prime}(\tau^{\prime}+0,\tau+M)\big{)}\geq M+1.$

  2. (b).

$(M^{\prime},M^{\prime\prime})=(1,0)$: In this case, it is known by the
inductive assumption,

$\displaystyle\nu\big{(}F_{2K-1}(\tau^{\prime\prime}+0)\big{)}\geq 2K+1,$

that by Theorem 13 (noting that $\tau^{\prime\prime}+0\equiv 2\pmod{4}$),

$\displaystyle\nu\big{(}Z^{\prime\prime}(\tau^{\prime\prime}+0,\tau^{\prime}+1)\big{)}=1,$

and that also by Theorem 13 (noting that $\tau^{\prime}+1\equiv 0\pmod{4}$),

$\displaystyle\nu\big{(}Z^{\prime}(\tau^{\prime}+1,\tau+M)\big{)}\geq M+1.$

  3. (c).

$(M^{\prime},M^{\prime\prime})=(2,0)$: In this case, it is known by the
inductive assumption,

$\displaystyle\nu\big{(}F_{2K-1}(\tau^{\prime\prime}+0)\big{)}\geq 2K+1,$

that by Theorem 13,

$\displaystyle\nu\big{(}Z^{\prime\prime}(\tau^{\prime\prime}+0,\tau^{\prime}+2)\big{)}\geq
3,$

and that by a weaker form of Theorem 13,

$\displaystyle\nu\big{(}Z^{\prime}(\tau^{\prime}+2,\tau+M)\big{)}\geq M-1.$

  4. (d).

$(M^{\prime},M^{\prime\prime})=(1,1)$: In this case, it is known by the
inductive assumption,

$\displaystyle\nu\big{(}F_{2K-1}(\tau^{\prime\prime}+1)\big{)}\geq 2K+1,$

that by Theorem 13,

$\displaystyle\nu\big{(}Z^{\prime\prime}(\tau^{\prime\prime}+1,\tau^{\prime}+1)\big{)}=0,$

and that also by Theorem 13 (noting that $\tau^{\prime}+1\equiv 0\pmod{4}$),

$\displaystyle\nu\big{(}Z^{\prime}(\tau^{\prime}+1,\tau+M)\big{)}\geq M+1.$

  5. (e).

$(M^{\prime},M^{\prime\prime})=(2,1)$: In this case, it is known by the
inductive assumption,

$\displaystyle\nu\big{(}F_{2K-1}(\tau^{\prime\prime}+1)\big{)}\geq 2K+1,$

that by Theorem 13 (noting that $\tau^{\prime\prime}+1\equiv 3\pmod{4}$),

$\displaystyle\nu\big{(}Z^{\prime\prime}(\tau^{\prime\prime}+1,\tau^{\prime}+2)\big{)}\geq
2,$

and that by a weaker form of Theorem 13,

$\displaystyle\nu\big{(}Z^{\prime}(\tau^{\prime}+2,\tau+M)\big{)}\geq M-1.$

We find that in each of these cases, the inequality (6.7) is also valid,
thereby closing our proof of (6.4). ∎

Finally, for (6.3), we shall make use of completely different logic without
consulting the relevant recurrences.

###### Proof of (6.3).

Recall that we have shown that the $2$-adic evaluations satisfy

$\displaystyle\nu\big{(}F_{2K+1}(\tau_{2K+1}+M)\big{)}\geq 2^{2K+3}$

whenever $M\geq 1$ in the proof of (6.4). Modulo $2^{2K+3}$, we have

$\displaystyle\Phi_{2K+1}\equiv
F_{2K+1}(\tau_{2K+1})\cdot\xi^{\tau_{2K+1}}\pmod{2^{2K+3}}.$ (6.8)

Note that the constant term on the left-hand side is $0$ since

$\displaystyle\Phi_{2K+1}=\gamma(q)^{2^{2K+1}}\left(\sum_{n=0}^{\infty}PDO(2^{2K+3}n)q^{n}-\sum_{n=0}^{\infty}PDO(2^{2K+1}n)q^{n}\right),$

while within the parentheses it is clear that

$\displaystyle PDO(2^{2K+3}\cdot 0)q^{0}-PDO(2^{2K+1}\cdot 0)q^{0}=0.$

Meanwhile, the constant term on the right-hand side of (6.8) is
$F_{2K+1}(\tau_{2K+1})$ as the constant term of $\xi(q)$ is $1$. Since the
congruence (6.8) is valid, we must have that their constant terms are also
congruent under the same modulus, so as to give us

$\displaystyle F_{2K+1}(\tau_{2K+1})\equiv 0\pmod{2^{2K+3}},$

which is equivalent to (6.3). ∎

##  7\. Conclusion

We close with two sets of comments. First, we remind the reader of one of the
original goals for proving such internal congruences. As was mentioned above,
the second author [15] used two corollaries of Theorem 1 to prove the
following Ramanujan-like congruences via induction on $\alpha$:

######  Theorem 17.

For all $\alpha\geq 0$ and all $n\geq 0,$

$\displaystyle PDO\big{(}2^{\alpha}(4n+3)\big{)}$ $\displaystyle\equiv
0\pmod{4},$ $\displaystyle PDO\big{(}2^{\alpha}(8n+7)\big{)}$
$\displaystyle\equiv 0\pmod{8}.$

It would be gratifying to see other cases of Theorem 1 used to assist in
proving divisibility properties satisfied by $PDO(n)$ for higher powers of
$2$.

Secondly, in the course of proving congruences modulo arbitrary powers for the
coefficients of an eta-product

$\displaystyle\mathrm{H}(q)=\sum_{n=0}^{\infty}h(n)q^{n},$

the usual strategy is to find a suitable basis
$\\{\xi_{1},\xi_{2},\ldots,\xi_{L}\\}$ of the corresponding modular space such
that each dissection slice, accompanied by a certain multiplier (usually an
eta-product),

$\displaystyle\lambda_{m}\sum_{n=0}^{\infty}h(p^{m}n+t_{m})q^{n},$

can be represented as a polynomial in
$\mathbb{Z}[\xi_{1},\xi_{2},\ldots,\xi_{L}]$. For example, when proving the
congruences modulo powers of 5 for the partition function [17] or the
congruences modulo powers of $7$ for the distinct partition function [9], two
specific multipliers typically take turns showing up, i.e.,
$\lambda_{2M-1}=\lambda$ and $\lambda_{2M}=\lambda^{\prime}$ for two certain
series $\lambda$ and $\lambda^{\prime}$. However, in our study here, the
multipliers $\gamma$, $\gamma^{2}$, $\gamma^{4}$, $\gamma^{8}$, $\ldots$ never
overlap. Meanwhile, an important outcome of cycling the multipliers in the
previous studies is that it is typically sufficient to represent each degree
$p$ unitization $U_{p}\big{(}\kappa^{i}\xi^{j}\big{)}$ as a polynomial in
$\xi$ for a certain series $\kappa$, with the exponent $i$ restricted to
$\\{0,1\\}$; here we use the case where the basis of the modular space is
given by $\\{\xi\\}$ as an illustration. However, as shown in Sect. 2.2, when
there are endless possibilities for the multipliers, we have to extend the
consideration of $i$ to infinity, thereby substantially increasing the amount
of required $p$-adic analysis. These striking facts distinguish our work from
the past literature.

## References

  * [1] P. Adansie, S. Chern, and E. X. W. Xia, New infinite families of congruences for the number of tagged parts over partitions with designated summands, Int. J. Number Theory 14 (2018), no. 7, 1935–1942.
  * [2] G. E. Andrews, R. P. Lewis, and J. Lovejoy, Partitions with designated summands, Acta Arith. 105 (2002), no. 1, 51–66.
  * [3] N. D. Baruah and M. Kaur, A note on some recent results of da Silva and Sellers on congruences for $k$-regular partitions with designated summands, Integers 20 (2020), Paper No. A74, 6 pp.
  * [4] N. D. Baruah and K. K. Ojah, Partitions with designated summands in which all parts are odd, Integers 15 (2015), Paper No. A9, 16 pp.
  * [5] W. Y. C. Chen, K. Q. Ji, H.-T. Jin, and E. Y. Y. Shen, On the number of partitions with designated summands, J. Number Theory 133 (2013), no. 9, 2929–2938.
  * [6] R. da Silva and J. A. Sellers, New congruences for $3$-regular partitions with designated summands, Integers 20A (2020), Paper No. A6, 11 pp.
  * [7] R. da Silva and J. A. Sellers, Infinitely many congruences for $k$-regular partitions with designated summands, Bull. Braz. Math. Soc. (N.S.) 51 (2020), no. 2, 357–370.
  * [8] F. Garvan, A $q$-product tutorial for a $q$-series MAPLE package, Sém. Lothar. Combin. 42 (1999), Art. B42d, 27 pp.
  * [9] B. Gordon and K. Hughes, Ramanujan congruences for $q(n)$, In: Analytic Number Theory (Philadelphia, Pa., 1980), 333–359, Lecture Notes in Math., 899, Springer, Berlin-New York, 1981.
  * [10] B. Hemanthkumar, H. S. Sumanth Bharadwaj, and M. S. Mahadeva Naika, Congruences modulo small powers of $2$ and $3$ for partitions into odd designated summands, J. Integer Seq. 20 (2017), no. 4, Art. 17.4.3, 25 pp.
  * [11] D. Herden, M. R. Sepanski, J. Stanfill, C. C. Hammon, J. Henningsen, H. Ickes, and I. Ruiz, Partitions with designated summands not divisible by $2^{\ell}$, $2$, and $3^{\ell}$ modulo $2$, $4$, and $3$, Integers 23 (2023), Paper No. A43, 23 pp.
  * [12] M. S. Mahadeva Naika and D. S. Gireesh, Congruences for $3$-regular partitions with designated summands, Integers 16 (2016), Paper No. A25, 14 pp.
  * [13] K. Ono, The Web of Modularity: Arithmetic of the Coefficients of Modular Forms and $q$-Series, American Mathematical Society, Providence, RI, 2004.
  * [14] C.-S. Radu, An algorithmic approach to Ramanujan–Kolberg identities, J. Symbolic Comput. 68 (2015), part 1, 225–253.
  * [15] J. A. Sellers, New infinite families of congruences modulo powers of $2$ for $2$-regular partitions with designated summands, submitted.
  * [16] N. A. Smoot, On the computation of identities relating partition numbers in arithmetic progressions with eta quotients: an implementation of Radu’s algorithm, J. Symbolic Comput. 104 (2021), 276–311.
  * [17] G. N. Watson, Ramanujans Vermutung über Zerfällungszahlen, J. Reine Angew. Math. 179 (1938), 97–128.
  * [18] E. X. W. Xia, Arithmetic properties of partitions with designated summands, J. Number Theory 159 (2016), 160–175.


# Some applications of the Lagrange inversion formula for the $k$-Fibonacci
numbers

Bakir FARHI
Laboratoire de Mathématiques appliquées
Faculté des Sciences Exactes
Université de Bejaia, 06000 Bejaia, Algeria
<EMAIL_ADDRESS>
http://farhi.bakir.free.fr/

###### Abstract

The aim of this paper consists of providing summation formulas for the
$k$-Fibonacci numbers ($k\in{\mathbb{Z}}$, $k\geq 2$) and their asymptotic
equivalents in terms of generalized binomial coefficients. Our main tools are
the Lagrange inversion formula and one of its consequences due to Hermite.

MSC 2020: Primary 11B39; Secondary 11B83, 11B65, 11B37.
Keywords: $k$-Fibonacci numbers, Fibonacci numbers, linear recurrent
sequences, binomial coefficients, the Lagrange inversion formula.

##  1 Introduction and Notation

Throughout this paper, we let ${\mathbb{N}}$ denote the set of positive
integers and ${\mathbb{N}}_{0}:={\mathbb{N}}\cup\\{0\\}$ the set of
nonnegative integers. Next, the (compositional) inverse function of a function
$f$ is denoted by $f^{<-1>}$ and the coefficient of $z^{n}$
($n\in{\mathbb{N}}_{0}$) in a power series $\varphi(z)$ is denoted by
$[z^{n}]\varphi(z)$. Further, we let $\binom{a}{b}$ ($a,b\in{\mathbb{Z}}$)
denote the generalized binomial coefficient defined by:

$\binom{a}{b}:=\begin{cases}\frac{a(a-1)\cdots(a-b+1)}{b!}&\text{if }b\geq
0\\\ \binom{a}{a-b}&\text{if }a\geq b\\\ 0&\text{if }a<b<0\end{cases}.$ (1.1)

Using this definition, we easily cheek the following formulas:

$\displaystyle\binom{a}{b}$
$\displaystyle=\binom{a-1}{b-1}+\binom{a-1}{b}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\forall(a,b)\in{\mathbb{Z}}^{2}\setminus\\{(0,0)\\}),$
(1.2) $\displaystyle\binom{a}{b}$
$\displaystyle=\begin{cases}(-1)^{b-1}\binom{b-a-1}{b}&\text{if }b\leq a<0\\\
(-1)^{b}\binom{b-a-1}{b}&\text{else}\end{cases}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\forall(a,b)\in{\mathbb{Z}}^{2}).$
(1.3)

For a given integer $k\geq 2$, the $k$-Fibonacci sequence is the integer
sequence ${(F_{n}^{(k)})}_{n\in{\mathbb{N}}_{0}}$ given by the recurrence
relation

$F_{n+k}^{(k)}=F_{n}^{(k)}+F_{n+1}^{(k)}+\dots+F_{n+k-1}^{(k)}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\forall
n\in{\mathbb{N}}_{0}),$ (1.4)

with the initial values $F_{0}^{(k)}=F_{1}^{(k)}=\dots=F_{k-2}^{(k)}=0$ and
$F_{k-1}^{(k)}=1$. The special case $k=2$ corresponds to the usual Fibonacci
sequence, simply denoted by ${(F_{n})}_{n\in{\mathbb{N}}_{0}}$ and given by

$\left\\{\begin{array}[]{l}F_{0}=0,F_{1}=1,\\\
F_{n+2}=F_{n}+F_{n+1}~{}~{}~{}~{}(\forall
n\in{\mathbb{N}}_{0})\end{array}\right..$

The above linear recurrence relation (1.4) of order $k$ for the $k$-Fibonacci
sequence easily implies the following simpler linear recurrence relation of
order $(k+1)$:

$F_{n+k+1}^{(k)}=2F_{n+k}^{(k)}-F_{n}^{(k)}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\forall
n\in{\mathbb{N}}_{0})$ (1.5)

(see [4] for the details). By relying on (1.5), we easily check that we have

$\begin{split}F_{n}^{(k)}&=2^{n-k}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{for
}k\leq n<2k,\\\ F_{2k}^{(k)}&=2^{k}-1.\end{split}$ (1.6)

The $k$-Fibonacci sequence plays an important role in many areas of
Mathematics, including Discrete Mathematics and Combinatorics. Here is a
simple combinatorial interpretation: given an integer $k\geq 2$, the number of
possible ways of writing a positive integer $n$ as a sum of numbers, all
belonging to the set $\\{1,2,\dots,k\\}$ (taking into account the
permutations), is exactly $F_{n+k-1}^{(k)}$. To find a closed form of
$F_{n}^{(k)}$, the theory of linear recurrence sequences associates to the
linear recurrence (1.4) the polynomial equation (known as its characteristic
equation)

$x^{k}=x^{k-1}+x^{k-2}+\dots+x+1.$ (${\mathbb{E}}_{k}$)

Multiplying the both sides of (${\mathbb{E}}_{k}$) by $(x-1)$ and rearranging,
we obtain the simpler polynomial equation

$x^{k+1}-2x^{k}+1=0,$ (${\mathbb{E}}_{k}^{\prime}$)

which is nothing else the characteristic equation associated to the linear
recurrence (1.5). The closed form of $F_{n}^{(k)}$ then depends on the complex
roots of Equation (${\mathbb{E}}_{k}$) and their multiplicities. Furthermore,
in order to establish a simple asymptotic equivalent for $F_{n}^{(k)}$ (as
$n\rightarrow+\infty$), it is necessary to locate the complex roots of
Equation (${\mathbb{E}}_{k}$) in the complex plane, a topic that has been
investigated by several authors. Using the famous Rouché theorem of complex
analysis, Miles [6] proved that Equation (${\mathbb{E}}_{k}$) has exactly
$(k-1)$ pairwise distinct complex roots in the open unit disk $D(0,1)$ of the
complex plane and a unique complex root $\rho_{k}$ of modulus greater than
$1$; precisely, $\rho_{k}$ is real and belongs to the interval $(1,2)$. In
[10], Wolfram showed that we have more precisely

$2-\frac{2}{2^{k}}<\rho_{k}<2.$ (1.7)

For the special case $k=2$, $\rho_{k}$ is nothing else the famous golden
ratio, commonly denoted by $\phi$ ($\phi=\frac{\sqrt{5}+1}{2}=1.618\dots$). In
[7], Miller founded an elementary way to prove the Miles result, which relies
on Descartes’s rules of signs. Denoting by
$\alpha_{k,1},\alpha_{k,2},\dots,\alpha_{k,k}=\rho_{k}$ the complex roots of
Equation (${\mathbb{E}}_{k}$), the theory of linear recurrence sequences shows
that $F_{n}^{(k)}$ has the closed form
$F_{n}^{(k)}=\sum_{\ell=1}^{k}\lambda_{k,\ell}\alpha_{k,\ell}^{n}$ ($\forall
n\in{\mathbb{N}}_{0}$), where the $\lambda_{k,\ell}$’s are complex numbers
(independent on $n$) which can be calculated by relying on the initial values
of the sequence ${(F_{n}^{(k)})}_{n}$. In [8], Spickerman and Joyner showed
that

$\lambda_{k,\ell}=\frac{\alpha_{k,\ell}^{k+1}-\alpha_{k,\ell}^{k}}{\alpha_{k,\ell}\left[2\alpha_{k,\ell}^{k}-(k+1)\right]}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\forall\ell\in\\{1,2,\dots,k\\}),$

and in [3], Dresden simplified this to

$\lambda_{k,\ell}=\frac{\alpha_{k,\ell}-1}{\alpha_{k,\ell}\left[2+(k+1)(\alpha_{k,\ell}-2)\right]}=\frac{\alpha_{k,\ell}-1}{\alpha_{k,\ell}\left[(k+1)\alpha_{k,\ell}-2k\right]}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\forall\ell\in\\{1,2,\dots,k\\}).$

So we have for all $n\in{\mathbb{N}}_{0}$:

$F_{n}^{(k)}=\sum_{\ell=1}^{k}\frac{\alpha_{k,\ell}-1}{(k+1)\alpha_{k,\ell}-2k}\,\alpha_{k,\ell}^{n-1}.$

Then, since $\rho_{k}$ is the largest root of (${\mathbb{E}}_{k}$) in modulus,
we derive the following asymptotic equivalence (as $n\rightarrow+\infty$):

$F_{n}^{(k)}\sim_{+\infty}\frac{\rho_{k}-1}{(k+1)\rho_{k}-2k}\,\rho_{k}^{n-1}.$
(1.8)

Let us denote by $\mathrm{As}_{n}^{(k)}$ the expression of the right-hand side
of (1.8); that is

$\mathrm{As}_{n}^{(k)}:=\frac{\rho_{k}-1}{(k+1)\rho_{k}-2k}\,\rho_{k}^{n-1}$
(1.9)

(for all integer $k\geq 2$ and all $n\in{\mathbb{N}}_{0}$). Next, for all
integer $k\geq 2$, define

$\varepsilon_{k}:=2-\rho_{k}.$

From (1.7), we have that $\varepsilon_{k}\in(0,2^{1-k})\subset(0,1/2)$.
Furthermore, from the fact that $\rho_{k}$ is a root of Equation
(${\mathbb{E}}_{k}^{\prime}$), we derive that

$\varepsilon_{k}=\frac{1}{(2-\varepsilon_{k})^{k}},$ (1.10)

which is a crucial equality for our purpose.

The goal of this paper is first to represent $\rho_{k}^{n}$ and
$\mathrm{As}_{n}^{(k)}$ as series involving binomial coefficients. Then, by
truncating judiciously the series related to $\mathrm{As}_{n}^{(k)}$, we
derive a representation of $F_{n}^{(k)}$ as a finite sum involving binomial
coefficients. Our results are essentially obtained by employing the Lagrange
inversion formula and one of its consequences due to Hermite (see §2). While
some of these results have been previously pointed out by other authors, they
were often accompanied by ad hoc proofs, and in some instances, contained
mistakes (see §3 for detailed discussion).

##  2 The Lagrange inversion formula

The Lagrange inversion formula is one of the most important formulas of
combinatorics. In its general form, it can be stated as follows

######  Theorem 1 (The Lagrange inversion formula).

Let $\alpha,z_{0}\in{\mathbb{C}}$ and $f$ be a complex analytic function of
$z$ at a neighborhood of $z_{0}$. Let also $w=w(z)$ be a complex analytic
function of $z$ at a neighborhood of $z_{0}$, which is implicitly defined by:

$w=z_{0}+\alpha f(w).$ (2.1)

Then for every complex analytic function $g$ of $z$ at a neighborhood of
$z_{0}$, we have (for $|\alpha|$ sufficiently small)

$g(w)=g(z_{0})+\sum_{n=1}^{+\infty}\frac{\alpha^{n}}{n!}\left[\left(\frac{d}{dz}\right)^{n-1}\\!\\!\\!\left(f^{n}g^{\prime}\right)\right](z_{0}).$

Taking in particular $g(z)=z$, we get (for $|\alpha|$ sufficiently small)

$w=z_{0}+\sum_{n=1}^{+\infty}\frac{\alpha^{n}}{n!}\left[\left(\frac{d}{dz}\right)^{n-1}\\!\\!\\!\left(f^{n}\right)\right](z_{0}).$

Note that the last part of this important theorem was proved in 1770 by
Lagrange [5], who applied it to solve the Kepler equation $y=x+\alpha\sin{y}$,
while its generalization (i.e., the first part of Theorem 1) was obtained by
Bürmann [1] in 1798. One simple way to prove Theorem 1 uses contour
integration in the complex plane, while other more elementary approaches
employ algebraic techniques on formal series (see e.g., [2, 9]). From Theorem
1, we derive the following interesting corollary, which is due to Hermite (see
[2]):

######  Corollary 2 (Hermite).

Let $\varphi$ be a complex analytic function at a neighborhood of $0$ such
that $\varphi(0)\neq 0$ and let $\psi$ be the compositional inverse function
of the function $z\rightarrow\frac{z}{\varphi(z)}$ at a neighborhood of $0$
($\psi$ exists because
$\left(\frac{z}{\varphi(z)}\right)^{\prime}(0)=\frac{1}{\varphi(0)}\neq 0$).
Then for every complex function $g$, which is analytic at a neighborhood of
$0$, we have

$\frac{z\cdot(g\circ\psi)(z)}{\psi(z)\cdot\left(\left(\frac{z}{\varphi(z)}\right)^{\prime}\circ\psi(z)\right)}=\sum_{n=0}^{+\infty}z^{n}[z^{n}]\left(g(z)\varphi(z)^{n}\right).$

Since this last result of Hermite is unfamiliar, we have preferred to include
its proof in this paper.

###### Proof of Corollary 2.

Let f be a primitive of the function $\frac{g}{\varphi}$ at a neighborhood of
$0$. By definition of $\psi$, we have
$\left(\frac{z}{\varphi(z)}\circ\psi\right)(z)=z$; that is $\psi$ is
implicitly given by:

$\psi(z)=0+z\cdot\left(\varphi\circ\psi\right)(z).$ (2.2)

So by applying the first part of Theorem 1 with (2.2) filling the role of
(2.1); that is with $w$ replaced by $\psi$, $f$ by $\varphi$, $\alpha$ by $z$,
$z_{0}$ by $0$, and $g$ by $f$, we get

$\displaystyle\left(f\circ\psi\right)(z)$
$\displaystyle=f(0)+\sum_{n=1}^{+\infty}\frac{z^{n}}{n!}\left[\left(\frac{d}{dz}\right)^{n-1}\\!\\!\\!\left(\varphi(z)^{n}f^{\prime}(z)\right)\right](0)$
$\displaystyle=f(0)+\sum_{n=1}^{+\infty}\frac{z^{n}}{n}\left[z^{n-1}\right]\left(g(z)\varphi(z)^{n-1}\right)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\text{since
}f^{\prime}=\frac{g}{\varphi})$
$\displaystyle=f(0)+\sum_{n=0}^{+\infty}\frac{z^{n+1}}{n+1}\left[z^{n}\right]\left(g(z)\varphi(z)^{n}\right).$

By differentiating with respect to $z$, we get

$\psi^{\prime}(z)\cdot\left(f^{\prime}\circ\psi\right)(z)=\sum_{n=0}^{+\infty}z^{n}\left[z^{n}\right]\left(g(z)\varphi(z)^{n}\right).$

But since

$\psi^{\prime}(z)=\left(\left(\frac{z}{\varphi(z)}\right)^{<-1>}\right)^{\prime}=\frac{1}{\left(\frac{z}{\varphi(z)}\right)^{\prime}\circ\psi(z)}$

and

$\left(f^{\prime}\circ\psi\right)(z)=\left(\frac{g}{\varphi}\circ\psi\right)(z)=\frac{(g\circ\psi)(z)}{(\varphi\circ\psi)(z)}=\frac{1}{\psi(z)}\cdot\frac{\psi(z)}{(\varphi\circ\psi)(z)}\cdot\left(g\circ\psi\right)(z)\\\
=\frac{1}{\psi(z)}\cdot\underbrace{\left(\frac{z}{\varphi(z)}\circ\psi(z)\right)}_{=z}\cdot\left(g\circ\psi\right)(z)=\frac{z}{\psi(z)}\cdot\left(g\circ\psi\right)(z),$

it follows that:

$\frac{z\cdot(g\circ\psi)(z)}{\psi(z)\cdot\left(\left(\frac{z}{\varphi(z)}\right)^{\prime}\circ\psi(z)\right)}=\sum_{n=0}^{+\infty}z^{n}[z^{n}]\left(g(z)\varphi(z)^{n}\right),$

as required. ∎

##  3 The results and the proofs

We begin with the following result which express the powers of $\rho_{k}$
($k\geq 2$) as real series involving binomial coefficients.

######  Theorem 3.1.

For every positive integers $k$ and $n$, with $k\geq 2$, we have

$\rho_{k}^{n}=2^{n}-n2^{n-k-1}\sum_{\ell=0}^{+\infty}\frac{1}{\ell+1}\binom{k(\ell+1)+\ell-n}{\ell}\frac{1}{2^{(k+1)\ell}}.$

In particular, we have

$\rho_{k}=2-\frac{1}{2^{k}}\sum_{\ell=0}^{+\infty}\frac{1}{\ell+1}\binom{k(\ell+1)+\ell-1}{\ell}\frac{1}{2^{(k+1)\ell}}.$

###### Proof.

Let $k$ and $n$ be two fixed positive integers with $k\geq 2$. By applying the
first part of Theorem 1 with (1.10) filling the role of (2.1); that is with
$w=\varepsilon_{k}$, $f(z)=(2-z)^{-k}$, $\alpha=1$, $z_{0}=0$, and
$g(z)=(2-z)^{n}$, we get

$\displaystyle\left(2-\varepsilon_{k}\right)^{n}$
$\displaystyle=2^{n}+\sum_{\ell=1}^{+\infty}\frac{1}{\ell!}\left[\left(\frac{d}{dz}\right)^{\ell-1}\\!\\!\\!\left((2-z)^{-k\ell}(-n(2-z)^{n-1})\right)\right](0)$
$\displaystyle=2^{n}-n\sum_{\ell=1}^{+\infty}\frac{1}{\ell!}\left[\left(\frac{d}{dz}\right)^{\ell-1}\\!\\!\\!(2-z)^{-k\ell+n-1}\right](0)$
$\displaystyle=2^{n}-n\sum_{\ell=1}^{+\infty}\frac{1}{\ell}\left[z^{\ell-1}\right](2-z)^{-k\ell+n-1}.$

But according to the generalized binomial formula, we have for all
$\ell\in{\mathbb{N}}$:

$\left[z^{\ell-1}\right](2-z)^{-k\ell+n-1}=\binom{-k\ell+n-1}{\ell-1}2^{-k\ell+n-\ell}(-1)^{\ell-1}=\binom{k\ell-n+\ell-1}{\ell-1}\frac{2^{n}}{2^{(k+1)\ell}}$

(according to (1.3)). Thus

$\displaystyle\left(2-\varepsilon_{k}\right)^{n}$
$\displaystyle=2^{n}-n\sum_{\ell=1}^{+\infty}\frac{1}{\ell}\binom{k\ell-n+\ell-1}{\ell-1}\frac{2^{n}}{2^{(k+1)\ell}}$
$\displaystyle=2^{n}-n\sum_{\ell=0}^{+\infty}\frac{1}{\ell+1}\binom{k(\ell+1)+\ell-n}{\ell}\frac{2^{n}}{2^{(k+1)(\ell+1)}};$

that is

$\rho_{k}^{n}=2^{n}-n2^{n-k-1}\sum_{\ell=0}^{+\infty}\frac{1}{\ell+1}\binom{k(\ell+1)+\ell-n}{\ell}\frac{1}{2^{(k+1)\ell}},$

as required. ∎

######  Remarks 3.2.

  1. 1.

In the proof of Theorem 3.1, we have omitted the verification of the
convergence of the series
$\sum_{\ell=0}^{+\infty}\frac{1}{\ell+1}\binom{k(\ell+1)+\ell-n}{\ell}\frac{1}{2^{(k+1)\ell}}$.
Note that this convergence can be easily confirmed by using for example the
elementary upper bounds $\binom{m}{\ell}\leq\frac{2^{m}}{\sqrt{m+2}}$ (for
$1\leq\ell\leq m$).

  2. 2.

Actually, the formula of $\rho_{k}$ in the second part of Theorem 3.1 has
already been discovered by Wolfram [10], who obtained it in a more complicated
way.

By specializing in Theorem 3.1 the integer $k$ to $2$, we derive important
formulas for the golden ration $\phi$ and its powers. Precisely, we obtain the
following corollary:

######  Corollary 3.3.

For every positive integer $n$, we have

$\phi^{n}=2^{n}-n2^{n-3}\sum_{\ell=0}^{+\infty}\frac{1}{\ell+1}\binom{3\ell+2-n}{\ell}\frac{1}{2^{3\ell}}.$

In particular, we have

$\phi=2-\sum_{\ell=0}^{+\infty}\frac{1}{\ell+1}\binom{3\ell+1}{\ell}\frac{1}{2^{3\ell+2}}.$
$\square$

More interestingly, we are going to find representations as series (analogous
to those of Theorem 3.1) for the asymptotic equivalent $\mathrm{As}_{n}^{(k)}$
of $F_{n}^{(k)}$. To achieve this, we rely on the following key theorem:

######  Theorem 3.4.

For every integers $k$ and $a$, with $k\geq 2$, we have

$\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell+a}{\ell}2^{-(k+1)\ell}=2^{a+1}\cdot\frac{\rho_{k}^{-a}}{(k+1)\rho_{k}-2k}.$

###### Proof.

Let $k$ and $a$ be fixed integers, with $k\geq 2$. We apply Corollary 2 for
the functions $\varphi(z)=(2-z)^{-k}$ and $g(z)=(2-z)^{-a-1}$, which are both
analytic at a neighborhood of $0$ and we have $\varphi(0)=2^{-k}\neq 0$. In
this situation, the compositional inverse function $\psi$ of the function
$z\mapsto\frac{z}{\varphi(z)}=z(2-z)^{k}$ (at a neighborhood of $0$) satisfies
(according to (1.10)): $\psi(1)=\varepsilon_{k}$. So by specializing in
formula of Corollary 2 the variable $z$ to $1$, we get

$\frac{1\cdot(g\circ\psi)(1)}{\psi(1)\cdot\left(\left(z(2-z)^{k}\right)^{\prime}\circ\psi\right)(1)}=\sum_{\ell=0}^{+\infty}1^{\ell}[z^{\ell}](2-z)^{-k\ell-a-1}.$

But since $\psi(1)=\varepsilon_{k}$ (as clarified above),
$\left(z(2-z)^{k}\right)^{\prime}=(2-z)^{k-1}\left(2-(k+1)z\right)$, and for
all $\ell\in{\mathbb{N}}_{0}$:
$[z^{\ell}](2-z)^{-k\ell-a-1}=\binom{-k\ell-a-1}{\ell}2^{-k\ell-a-1-\ell}(-1)^{\ell}=\binom{(k+1)\ell+a}{\ell}2^{-(k+1)\ell-a-1}$
(by using the generalized binomial formula and then (1.3)), it follows that

$\frac{(2-\varepsilon_{k})^{-a-1}}{\varepsilon_{k}(2-\varepsilon_{k})^{k-1}\left(2-(k+1)\varepsilon_{k}\right)}=\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell+a}{\ell}2^{-(k+1)\ell-a-1}.$

Finally, since $\varepsilon_{k}(2-\varepsilon_{k})^{k}=1$ (according to
(1.10)), $2-\varepsilon_{k}=\rho_{k}$, and $2-(k+1)\varepsilon_{k}=$
$2-(k+1)(2-\rho_{k})=(k+1)\rho_{k}-2k$, we conclude to

$\frac{\rho_{k}^{-a}}{(k+1)\rho_{k}-2k}=\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell+a}{\ell}2^{-(k+1)\ell-a-1},$

which immediately gives the required formula of the theorem. ∎

######  Remark 3.5.

The convergence of the series in the formula of Theorem 3.4 can be verified by
using for example the Stirling formula $n!\sim_{+\infty}n^{n}e^{-n}\sqrt{2\pi
n}$.

Relying on Theorem 3.4, we are now able to provide a series representation
(involving binomial coefficients) for the asymptotic equivalent
$\mathrm{As}_{n}^{(k)}$ of $F_{n}^{(k)}$. This is the subject of the following
theorem:

######  Theorem 3.6.

For every nonnegative integers $k$ and $n$, with $k\geq 2$ and $n\neq 1$, we
have

$\mathrm{As}_{n}^{(k)}=2^{n-2}\sum_{\ell=0}^{+\infty}\left[\binom{(k+1)\ell-n}{\ell}-\binom{(k+1)\ell-n}{\ell-1}\right]2^{-(k+1)\ell}.$

###### Proof.

Let $k$ and $n$ be two fixed nonnegative integers such that $k\geq 2$ and
$n\neq 1$. By applying Theorem 3.4 for $a=-n$, we get

$\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell-n}{\ell}2^{-(k+1)\ell}=2^{-n+1}\cdot\frac{\rho_{k}^{n}}{(k+1)\rho_{k}-2k}.$
(3.1)

Similarly, by applying Theorem 3.4 for $a=k+1-n$, we get

$\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell+k+1-n}{\ell}2^{-(k+1)\ell}=2^{k+2-n}\cdot\frac{\rho_{k}^{n-k-1}}{(k+1)\rho_{k}-2k}.$
(3.2)

But we remark that

$\displaystyle\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell+k+1-n}{\ell}2^{-(k+1)\ell}$
$\displaystyle=\sum_{\ell=0}^{+\infty}\binom{(k+1)(\ell+1)-n}{\ell}2^{-(k+1)\ell}$
$\displaystyle=\sum_{\ell=1}^{+\infty}\binom{(k+1)\ell-n}{\ell-1}2^{-(k+1)(\ell-1)}$
$\displaystyle=2^{k+1}\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell-n}{\ell-1}2^{-(k+1)\ell}$

(since $\binom{(k+1)\ell-n}{\ell-1}=0$ for $\ell=0$, because $n\neq 1$). Thus
Formula (3.2) is simplified to

$\sum_{\ell=0}^{+\infty}\binom{(k+1)\ell-n}{\ell-1}2^{-(k+1)\ell}=2^{-n+1}\frac{\rho_{k}^{n-k-1}}{(k+1)\rho_{k}-2k}.$
(3.3)

Next, by subtracting side by side Eq. (3.3) from Eq. (3.1) and then
multiplying by $2^{n-2}$, we get

$\displaystyle
2^{n-2}\sum_{\ell=0}^{+\infty}\left[\binom{(k+1)\ell-n}{\ell}-\binom{(k+1)\ell-n}{\ell-1}\right]2^{-(k+1)\ell}$
$\displaystyle=\frac{1}{2}\cdot\frac{\rho_{k}^{n}-\rho_{k}^{n-k-1}}{(k+1)\rho_{k}-2k}$
$\displaystyle=\frac{1}{2}\cdot\frac{\rho_{k}-\rho_{k}^{-k}}{(k+1)\rho_{k}-2k}\cdot\rho_{k}^{n-1}$
$\displaystyle=\frac{1}{2}\cdot\frac{\rho_{k}-(2-\rho_{k})}{(k+1)\rho_{k}-2k}\cdot\rho_{k}^{n-1}~{}~{}~{}~{}~{}~{}(\text{in
view of \eqref{eq9}})$
$\displaystyle=\frac{\rho_{k}-1}{(k+1)\rho_{k}-2k}\rho_{k}^{n-1}$
$\displaystyle=\mathrm{As}_{n}^{(k)}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\text{according
to \eqref{eq8}}),$

as required. ∎

Observing Formula of Theorem 3.6, and because $As_{n}^{(k)}$ is close to
$F_{n}^{(k)}$ for $n$ large, a natural question arises: can replacing the
series therein with its truncation at some positive integer $N(n,k)$
(depending on $n$ and $k$) yield the $k$-Fibonacci numbers? Working in this
direction, we have established the following curious result:

######  Theorem 3.7.

For every integers $n,k\geq 2$, we have

$F_{n+k-2}^{(k)}=2^{n-2}\sum_{0\leq\ell\leq\frac{n-1}{k+1}}\left[\binom{(k+1)\ell-n}{\ell}-\binom{(k+1)\ell-n}{\ell-1}\right]2^{-(k+1)\ell}.$

To prepare for the proof of Theorem 3.7, let us provisionally define (for
every integers $n,k\geq 2$)

$G_{n}^{(k)}:=2^{n-2}\sum_{0\leq\ell\leq\frac{n-1}{k+1}}\left[\binom{(k+1)\ell-n}{\ell}-\binom{(k+1)\ell-n}{\ell-1}\right]2^{-(k+1)\ell}.$

We first establish the two following propositions:

######  Proposition 3.8.

Let $n,k\geq 2$ be two integers. Then we have

$\begin{split}G_{n}^{(k)}&=2^{n-2}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{for
}2\leq n\leq k+1,\\\ G_{k+2}^{(k)}&=2^{k}-1.\end{split}$ (3.4)

###### Proof.

For $2\leq n\leq k+1$, the only integer $\ell$ in the range
$[0,\frac{n-1}{k+1}]$ is $\ell=0$. So the definition of $G_{n}^{(k)}$ gives

$G_{n}^{(k)}=2^{n-2}\left[\binom{-n}{0}-\binom{-n}{-1}\right]=2^{n-2}$

(since $\binom{-n}{0}=1$ and $\binom{-n}{-1}=0$), as required.

Next, for $n=k+2$, the only integers in the range $[0,\frac{n-1}{k+1}]=[0,1]$
are $0$ and $1$. So the definition of $G_{k+2}^{(k)}$ gives

$\displaystyle G_{k+2}^{(k)}$
$\displaystyle=2^{k}\left\\{\left[\underbrace{\binom{-k-2}{0}}_{=1}-\underbrace{\binom{-k-2}{-1}}_{=0}\right]+\left[\underbrace{\binom{-1}{1}}_{=-1}-\underbrace{\binom{-1}{0}}_{=1}\right]2^{-k-1}\right\\}$
$\displaystyle=2^{k}\left(1-2^{-k}\right)$ $\displaystyle=2^{k}-1,$

as required. This completes the proof of the proposition. ∎

######  Proposition 3.9.

For all integers $n,k\geq 2$, we have

$G_{n+k+1}^{(k)}=2G_{n+k}^{(k)}-G_{n}^{(k)}.$

###### Proof.

Let $n,k\geq 2$ be two fixed integers. We have by definition

$2G_{n+k}^{(k)}=2^{n+k-1}\sum_{0\leq\ell\leq\frac{n+k-1}{k+1}}\left[\binom{(k+1)\ell-
n-k}{\ell}-\binom{(k+1)\ell-n-k}{\ell-1}\right]2^{-(k+1)\ell}.$ (3.5)

But summing on $\ell$ such that $0\leq\ell\leq\frac{n+k-1}{k+1}$ is equivalent
to sum on $\ell$ such that $0\leq\ell\leq\frac{n+k}{k+1}$, except perhaps in
the case where $\frac{n+k}{k+1}$ is an integer. Suppose that we are in the
last case (i.e., $\frac{n+k}{k+1}\in{\mathbb{Z}}$). Then since
$\frac{n+k}{k+1}\geq\frac{k+2}{k+1}>1$, we have $\frac{n+k}{k+1}\geq 2$. Thus
for $\ell=\frac{n+k}{k+1}\geq 2$, we find that $\binom{(k+1)\ell-
n-k}{\ell}-\binom{(k+1)\ell-n-k}{\ell-1}=\binom{0}{\ell}-\binom{0}{\ell-1}=0$,
implying that the sum for $0\leq\ell\leq\frac{n+k-1}{k+1}$ in (3.5) can be
replaced by the sum for $0\leq\ell\leq\frac{n+k}{k+1}$ even in the case where
$\frac{n+k}{k+1}\in{\mathbb{Z}}$. So we have in all cases

$2G_{n+k}^{(k)}=2^{n+k-1}\sum_{0\leq\ell\leq\frac{n+k}{k+1}}\left[\binom{(k+1)\ell-
n-k}{\ell}-\binom{(k+1)\ell-n-k}{\ell-1}\right]2^{-(k+1)\ell}.$ (3.6)

Next, we have by definition

$\displaystyle G_{n}^{(k)}$
$\displaystyle=2^{n-2}\sum_{0\leq\ell\leq\frac{n-1}{k+1}}\left[\binom{(k+1)\ell-n}{\ell}-\binom{(k+1)\ell-n}{\ell-1}\right]2^{-(k+1)\ell}$
$\displaystyle=2^{n-2}\sum_{1\leq\ell\leq\frac{n+k}{k+1}}\left[\binom{(k+1)(\ell-1)-n}{\ell-1}-\binom{(k+1)(\ell-1)-n}{\ell-2}\right]2^{-(k+1)(\ell-1)}$
$\displaystyle=2^{n+k-1}\sum_{1\leq\ell\leq\frac{n+k}{k+1}}\left[\binom{(k+1)\ell-
n-k-1}{\ell-1}-\binom{(k+1)\ell-n-k-1}{\ell-2}\right]2^{-(k+1)\ell}.$

But since $\ell=0$ gives $\binom{(k+1)\ell-n-k-1}{\ell-1}-\binom{(k+1)\ell-
n-k-1}{\ell-2}=\binom{-n-k-1}{-1}-\binom{-n-k-1}{-2}=0$ (because
$-n-k-1\leq-5$), we have even

$G_{n}^{(k)}=2^{n+k-1}\sum_{0\leq\ell\leq\frac{n+k}{k+1}}\left[\binom{(k+1)\ell-
n-k-1}{\ell-1}-\binom{(k+1)\ell-n-k-1}{\ell-2}\right]2^{-(k+1)\ell}.$ (3.7)

By subtracting (side to side) (3.7) from (3.6) and using the formulas

$\displaystyle\binom{(k+1)\ell-n-k}{\ell}-\binom{(k+1)\ell-
n-k-1}{\ell-1}=\binom{(k+1)\ell-n-k-1}{\ell}$ and
$\displaystyle\binom{(k+1)\ell-n-k}{\ell-1}-\binom{(k+1)\ell-
n-k-1}{\ell-2}=\binom{(k+1)\ell-n-k-1}{\ell-1}$

that result from (1.2), we get

$\displaystyle 2G_{n+k}^{(k)}-G_{n}^{(k)}$
$\displaystyle=2^{n+k-1}\sum_{0\leq\ell\leq\frac{n+k}{k+1}}\left[\binom{(k+1)\ell-
n-k-1}{\ell}-\binom{(k+1)\ell-n-k-1}{\ell-1}\right]2^{-(k+1)\ell}$
$\displaystyle=G_{n+k+1}^{(k)},$

as required. ∎

We are now ready to prove Theorem 3.7.

###### Proof of Theorem 3.7.

Let $k\geq 2$ be a fixed integer. We have to show that
$F_{n+k-2}^{(k)}=G_{n}^{(k)}$ for all integer $n\geq 2$. Since the two
sequences ${(F_{n+k-2}^{(k)})}_{n\geq 2}$ and ${(G_{n}^{(k)})}_{n\geq 2}$
satisfy the same linear recurrence relation of order $(k+1)$, which is

$u_{n+k+1}=2u_{n+k}-u_{n}$

(according to (1.5) and to Proposition 3.9) then it suffices to show that
$F_{n+k-2}^{(k)}$ and $G_{n}^{(k)}$ coincide at the first $(k+1)$ consecutive
values of $n$; that is

$F_{n+k-2}^{(k)}=G_{n}^{(k)}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\text{for }2\leq
n\leq k+2.$ (3.8)

To confirm (3.8), we distinguish the two following cases:
• 1st case: (if $2\leq n\leq k+1$). In this case, we have $k\leq n+k-2\leq
2k-1$, implying (according to (1.6)) that $F_{n+k-2}^{(k)}=2^{n-2}$. Since we
have also (according to (3.4)) $G_{n}^{(k)}=2^{n-2}$ then
$F_{n+k-2}^{(k)}=G_{n}^{(k)}$ for this case.
• 2nd case: (If $n=k+2$). In this case, we have
$F_{n+k-2}^{(k)}=F_{2k}^{(k)}=2^{k}-1$ (according to (1.6)) and
$G_{n}^{(k)}=G_{k+2}^{(k)}=2^{k}-1$ (according to (3.4)). Hence
$F_{n+k-2}^{(k)}=G_{n}^{(k)}$ also for this case. This confirms (3.8) and
completes this proof. ∎

By shifting the index $n$ to $(n-k+2)$ in Theorem 3.7, we derive the following
corollary:

######  Corollary 3.10.

For every integers $n$ and $k$ such that $n\geq k\geq 2$, we have

$F_{n}^{(k)}=2^{n-k}\sum_{0\leq\ell\leq\frac{n-k+1}{k+1}}\left[\binom{(k+1)\ell-n+k-2}{\ell}-\binom{(k+1)\ell-n+k-2}{\ell-1}\right]2^{-(k+1)\ell}.$
$\square$

By taking $k=2$ in Corollary 3.10, we derive in particular an expression of
the usual Fibonacci numbers as finite sums involving binomial coefficients and
nonpositive powers of $8$. This is given by the following corollary:

######  Corollary 3.11.

For all integer $n\geq 2$, we have

$F_{n}=2^{n-2}\sum_{0\leq\ell\leq\frac{n-1}{3}}\left[\binom{3\ell-n}{\ell}-\binom{3\ell-n}{\ell-1}\right]2^{-3\ell}.$
$\square$

We end this paper by deriving from Corollary 3.10 a result which corrects that
of Howard and Cooper [4, Theorem 2.4].

######  Corollary 3.12.

For every integers $n$ and $k$ such that $n\geq k\geq 2$ and $n\neq 2k-1$, we
have

$F_{n}^{(k)}=2^{n-k}+\sum_{1\leq\ell\leq\frac{n-k+1}{k+1}}(-1)^{\ell}\left[\binom{n-(\ell+1)k+2}{\ell}-\binom{n-(\ell+1)k}{\ell-2}\right]2^{n-(k+1)\ell-k}.$

###### Proof.

Let $n,k\in{\mathbb{Z}}$ be fixed with $n\geq k\geq 2$ and $n\neq 2k-1$.
According to Formula (1.2), we have for all
$(a,\ell)\in{\mathbb{Z}}^{2}\setminus\\{(0,0),(0,1)\\}$:

$\binom{a}{\ell}-\binom{a}{\ell-1}=\binom{a-1}{\ell}-\binom{a-1}{\ell-2}.$

By applying this last formula for each of the couples
$(a,\ell)=((k+1)\ell-n+k-2,\ell)$ ($0\leq\ell\leq\frac{n-k+1}{k+1}$), which
are all different from $(0,0)$ and $(0,1)$, we transform Formula of Corollary
3.10 to

$F_{n}^{(k)}=2^{n-k}\sum_{0\leq\ell\leq\frac{n-k+1}{k+1}}\left[\binom{(k+1)\ell+k-n-3}{\ell}-\binom{(k+1)\ell+k-n-3}{\ell-2}\right]2^{-(k+1)\ell}.$

Then, by applying Formula (1.3) for all the binomial coefficients occurring in
the last formula, we conclude to

$\displaystyle F_{n}^{(k)}$
$\displaystyle=2^{n-k}\sum_{0\leq\ell\leq\frac{n-k+1}{k+1}}(-1)^{\ell}\left[\binom{n-(\ell+1)k+2}{\ell}-\binom{n-(\ell+1)k}{\ell-2}\right]2^{-(k+1)\ell}$
$\displaystyle=2^{n-k}+\sum_{1\leq\ell\leq\frac{n-k+1}{k+1}}(-1)^{\ell}\left[\binom{n-(\ell+1)k+2}{\ell}-\binom{n-(\ell+1)k}{\ell-2}\right]2^{n-(k+1)\ell-k},$

as required. ∎

######  Remarks 3.13.

  1. 1.

In [4, Theorem 2.4], Formula of Corollary 3.12 is stated with the erroneous
condition of summation $1\leq\ell\leq\frac{n-1}{k+1}$. This condition
coincides with ours only for $k=2$. Therefore, Corollary 3.12 corrects Theorem
2.4 of [4].

  2. 2.

Applying (1.3) for all the binomial coefficients appearing in Formula of
Corollary 3.10, we transform this later to

$F_{n}^{(k)}=2^{n-k}+\sum_{1\leq\ell\leq\frac{n-k+1}{k+1}}(-1)^{\ell}\left[\binom{n-(\ell+1)k+1}{\ell}+\binom{n-(\ell+1)k}{\ell-1}\right]2^{n-(k+1)\ell-k}$

(valid for $n\geq k\geq 2$). Note that the last formula and the formula of
Corollary 3.12 have the advantage that the binomial coefficients which appear
in them are ordinary (i.e., have nonnegative entries). Note also that the two
formulas in question are equivalent (we pass from the one to the other via
Formula (1.2)).

## References

  * [1] H. H. Bürmann. Essai de calcul fonctionnaire aux constantes ad-libitum, submitted in 1796 to the Institut National de France.
  * [2] L. Comtet. Advanced Combinatorics. The Art of Finite and Infinite Expansions, revised and enlarged ed., D. Reidel Publ. Co., Dordrecht, 1974.
  * [3] Gregory P. B. Dresden. A simplified Binet formula for $k$-generalized Fibonacci numbers, J. Integer Seq., 17 (2014), Article 14.4.7.
  * [4] F. T. Howard & Curtis Cooper. Some Identities for r-Fibonacci Numbers, Fibonacci Quart., 49 (2011), p. 231-243.
  * [5] J-L. Lagrange. Nouvelle méthode pour résoudre les équations littérales par le moyen des séries, Histoire de l’Académie Royale des Sciences et Belles-Lettres de Berlin, (1770), p. 251-326.
  * [6] E. P. Miles. Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly, 67 (1960), p. 745-752.
  * [7] M. D. Miller. On generalized Fibonacci numbers, Amer. Math. Monthly, 78 (1971), p. 1108-1109.
  * [8] W. R. Spickerman & R. N. Joyner. Binet’s formula for the recursive sequence of order $k$, Fibonacci Quart., 22 (1984), p. 327-331.
  * [9] R. P. Stanley. Enumerative Combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge, 1999.
  * [10] D. A. Wolfram. Solving generalized Fibonacci recurrences, Fibonacci Quart., 36 (1998), p. 129-145.