1 Introduction and outline
In mathematics and applied science, Fibonacci and Lucas numbers are well known. They are defined by the same recurrence relations
$$ \begin{align*}F_{n}=F_{n-1}+F_{n-2} \quad\text{and}\quad L_{n}=L_{n-1}+L_{n-2}\end{align*} $$
but with different initial conditions
$$ \begin{align*}F_{0}=0,~F_{1}=1 \quad\text{and}\quad L_{0}=2,~L_{1}=1.\end{align*} $$
According to these recurrence relations, it is not hard to check that both definitions for Fibonacci and Lucas numbers can be extended to negative integer indices by
$$ \begin{align*}F_{-n}=(-1)^{n}F_{n} \quad\text{and}\quad L_{-n}=(-1)^{n}L_{n} \quad\text{for}\ n\in\mathbb{N}.\end{align*} $$
In 1965, Carlitz [Reference Carlitz2] discovered an elegant identity for circular sums:
$$ \begin{align} \sum_{0\le k_{1},k_{2},\ldots,k_{m}\le n} \binom{n-k_{1}}{k_{m}} \prod_{i=1}^{m-1}\binom{n-k_{i+1}}{k_{i}} =\frac{F_{mn+m}}{F_{m}}.\end{align} $$
There are three different proofs that can be found in [Reference Benjamin, Rouse and Howard1, Reference Chu5, Reference Mikic8]. Denote an m-tuple of integers by
$\mathbf {k}=(k_{1},k_{2},\ldots ,k_{m})\in \mathbb {N}_{0}^{m}$
. We define two component-related sums by
$$ \begin{align*}|\mathbf{k}|=\sum_{i=1}^{m}k_{i} \quad\text{and}\quad \|\mathbf{k}\|=\sum_{i=1}^{m}ik_{i}.\end{align*} $$
Recently, the author [Reference Chu5] found the following alternating counterpart:
$$ \begin{align*}\sum_{0\le k_{1},k_{2},\ldots,k_{m}\le n} (-1)^{|\mathbf{k}|}\binom{n-k_{1}}{k_{m}} \prod_{i=1}^{m-1}\binom{n-k_{i+1}}{k_{i}} =(-1)^{n\lfloor{{m}/3}\rfloor}\begin{cases} n+1&\text{if } m\equiv_{3}0;\\ u_{n}&\text{if } m\equiv_{3}1;\\ v_{n}&\text{if } m\equiv_{3}2; \end{cases}\end{align*} $$
where
$u_{n}$
and
$v_{n}$
are two periodic sequences (see A010892 and A049347 recorded in [Reference Sloane9]) and related by
$u_{2n+1}=v_{n}$
and given explicitly by
$$ \begin{align*}u_{n}=\begin{cases} ~1&\text{if } n\equiv_{6}0,~1;\\ -1&\text{if } n\equiv_{6}3,~4;\\ ~0&\text{if } n\equiv_{6}2,~5; \end{cases} \quad\text{and}\quad v_{n}=\begin{cases} ~1&\text{if } n\equiv_{3}0;\\ -1&\text{if } n\equiv_{3}1;\\ ~0&\text{if } n\equiv_{3}2. \end{cases}\end{align*} $$
To reduce lengthy expressions, the following abbreviations will be used throughout the paper. For a real number x, the greatest integer not exceeding it will be denoted by
$\lfloor {x}\rfloor $
. We shall use
$\chi $
for the logical function with
$\chi (\text {true})=1$
and
$\chi (\text {false})=0$
. For three integers
$i,j,m$
with
$m>0$
, the notation
$i\equiv _{m}j$
stands for ‘i is congruent to j modulo m’.
The aim of the present paper is to evaluate two further alternating circular sums of binomial coefficients by making use of the generating function approach:
$$ \begin{align}\Phi_{m}(n)&= \sum_{0\le k_{1},k_{2},\ldots,k_{m}\le n} (-1)^{\|\mathbf{k}\|}\binom{n-k_{1}}{k_{m}} \prod_{i=1}^{m-1}\binom{n-k_{i+1}}{k_{i}}; \end{align} $$
$$ \begin{align} \Psi_{m}(n)&= \sum_{0\le k_{1},k_{2},\ldots,k_{m}\le n} (-1)^{\|\mathbf{k}\|-|\mathbf{k}|}\binom{n-k_{1}}{k_{m}} \prod_{i=1}^{m-1}\binom{n-k_{i+1}}{k_{i}}. \end{align} $$
To fulfil this task, the Lagrange expansion formula [Reference Lagrange7] will be crucial. We give it in the following form (see Comtet [Reference Comtet and Reidel6, Section 3.8] and Chu [Reference Chu3, Reference Chu4]). For a formal power series
$\varphi (x)$
subject to the condition
$\varphi (0)\not =0$
, the functional equation
$y=x/\varphi (x)$
determines x as an implicit function of y. Then for another formal power series
$F(x)$
in the variable x, the following expansions hold for both composite series:
$$ \begin{align*} F(x(y))=F(0)+\sum_{n=1}^{\infty} \frac{y^{n}}{n}[x^{n-1}]\{F^{\prime}(x)\varphi^{n}(x)\}, \end{align*} $$
$$ \begin{align} \frac{F(x(y))}{1-x\varphi^{\prime}(x)/\varphi(x)} =\sum_{n=0}^{\infty}{y^{n}} [x^{n}]\{F(x)\varphi^{n}(x)\}; \end{align} $$
where
$[x^{k}]\phi (x)$
denotes the coefficient of
$x^{k}$
in the formal power series
$\phi (x)$
.□
2 The first alternating sum
$\boldsymbol {\Phi _{m}(n)}$
Observe that
$\Phi _{m}(n)$
defined in (1.2) can be rewritten as
$$ \begin{align*}\Phi_{m}(n)=\sum_{0\le k_{1},k_{2},\ldots,k_{m}\le n} (-1)^{\sum k_{2i-1}}\binom{n-k_{1}}{k_{m}} \prod_{i=1}^{m-1}\binom{n-k_{i+1}}{k_{i}},\end{align*} $$
where
$\sum k_{2i-1}$
denotes the sum of the odd indexed components of
$\mathbf {k}$
. Then we have the following theorem.
Theorem 2.1 (generating functions:
$m,n\in \mathbb {N}$
).
We have
$$ \begin{align*}\Phi_{m}(n)=\begin{cases} [y^{n}]\dfrac1{1-yL_{\lambda}+(-1)^{\lambda}y^{2}} &\text{if } {m=2\lambda};\\[5mm] [y^{n}]\dfrac1{1-yF_{\lambda-2}-(-1)^{\lambda}y^{2}} &\text{if } {m=2\lambda-1}. \end{cases}\end{align*} $$
Recall the Binet formulae:
$$ \begin{align*}F_{n}=\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta} \quad\text{and}\quad L_{n}=\alpha^{n}+\beta^{n}, \quad\text{where } \alpha,\beta=\frac{1\pm\sqrt5}2.\end{align*} $$
When m is even with
$m=2\lambda $
, we can rewrite the generating function and then decompose it into partial fractions:
$$ \begin{align*} \frac1{1-yL_{\lambda}+(-1)^{\lambda}y^{2}} =\frac1{1-y(\alpha^{\lambda}+\beta^{\lambda})+y^{2}(-1)^{\lambda}} =\frac1{\alpha^{\lambda}-\beta^{\lambda}} \bigg\{\frac{\alpha^{\lambda}}{1-y\alpha^{\lambda}} -\frac{\beta^{\lambda}}{1-y\beta^{\lambda}}\bigg\}. \end{align*} $$
By extracting the coefficient of
$x^{n}$
across the above equation, we find the following counterpart of Carlitz’ formula (1.1).
Proposition 2.2 (explicit formula:
$n,\lambda \in \mathbb {N}$
).
We have
$$ \begin{align*}{\Phi_{2\lambda}(n)=\frac{F_{n\lambda+\lambda}}{F_{\lambda}}.}\end{align*} $$
However, when m is odd with
$m=2\lambda -1$
, there exists no such closed formula. By expanding the corresponding generating function into power series
$$ \begin{align*} \dfrac1{1-yF_{\lambda-2}-(-1)^{\lambda}y^{2}} =\sum_{i=0}^{\infty}\{yF_{\lambda-2}+(-1)^{\lambda}y^{2}\}^{i} =\sum_{i=0}^{\infty}\sum_{k=0}^{i}(-1)^{k\lambda} \binom{i}{k}y^{i+k}F^{i-k}_{\lambda-2} \end{align*} $$
and then extracting the coefficient of
$y^{n}$
, we get the binomial sum expression.
Proposition 2.3 (explicit formula:
$n,\lambda \in \mathbb {N}$
).
$$ \begin{align*}{\Phi_{2\lambda-1}(n) =\sum_{k=0}^{n}(-1)^{k\lambda} \binom{n-k}{k}F^{n-2k}_{\lambda-2}.}\end{align*} $$
The first five values are highlighted in the following corollary.
Corollary 2.4 (explicit formula:
$n\in \mathbb {N}$
).
We have
$$ \begin{align*}\Phi_{1}(n)&=[y^{n}]\frac1{1-y+y^{2}} =(-1)^{\lfloor{{(n+1)}/3}\rfloor}\chi(n\not\equiv_{3}2);\\[6pt] \Phi_{3}(n)&=[y^{n}]\frac1{1-y^{2}}=\frac{1+(-1)^{n}}{2};\\[6pt] \Phi_{5}(n)&=[y^{n}]\frac1{1-y+y^{2}} =(-1)^{\lfloor{{(n+1)}/3}\rfloor}\chi(n\not\equiv_{3}2);\\[6pt] \Phi_{7}(n)&=[y^{n}]\frac1{1-y-y^{2}}=F_{n+1};\\[6pt] \Phi_{9}(n)&=[y^{n}]\frac1{1-2y+y^{2}}=n+1. \end{align*} $$
Proof of Theorem 2.1.
First, it is routine to verify the relations
$$ \begin{align*} (-1)^{k_{1}}\binom{n-k_{2}}{k_{1}} &=[x^{k_{1}}](1-x)^{n-k_{2}},\\[6pt] \binom{n-k_{1}}{k_{m}} &=[x^{n-k_{1}}]\frac{x^{k_{m}}}{(1-x)^{1+k_{m}}}. \end{align*} $$
They can be used to express the binomial sum with respect to
$k_{1}$
in
$\Phi _{m}(n)$
as
$$ \begin{align*}\Phi^{1}_{m}(n)&=\sum_{k_{1}=0}^{n}(-1)^{k_{1}} \binom{n-k_{2}}{k_{1}}\binom{n-k_{1}}{k_{m}}\\[6pt] &=[x^{n}]\frac{x^{k_{m}}(1-x)^{n-k_{2}}}{(1-x)^{1+k_{m}}}. \end{align*} $$
We proceed next with the binomial sum with respect to
$k_{2}$
in
$\Phi _{m}(n)$
:
$$ \begin{align*}\Phi^{2}_{m}(n)&=\sum_{k_{2}=0}^{n} [x^{n}]\frac{x^{k_{m}}(1-x)^{n-k_{2}}}{(1-x)^{1+k_{m}}} \binom{n-k_{3}}{k_{2}}\\[6pt] &=[x^{n}]\frac{x^{k_{m}}(1-x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{2-x}{1-x}\bigg\}^{n-k_{3}}\\[6pt] &=[x^{n}]\frac{x^{k_{m}}(2-x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{1-x}{2-x}\bigg\}^{k_{3}}. \end{align*} $$
Repeat this process for the binomial sum with respect to
$k_{3}$
in
$\Phi _{m}(n)$
:
$$ \begin{align*}\Phi^{3}_{m}(n)&=\sum_{k_{3}=0}^{n} [x^{n}]\frac{x^{k_{m}}(2-x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{1-x}{2-x}\bigg\}^{k_{3}} \binom{n-k_{4}}{k_{3}}(-1)^{k_{3}}\\[4pt] &=[x^{n}]\frac{x^{k_{m}}(2-x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{1}{2-x}\bigg\}^{n-k_{4}} =[x^{n}]\frac{x^{k_{m}}(2-x)^{k_{4}}}{(1-x)^{1+k_{m}}}\\[4pt] &=[x^{n}]\frac{x^{k_{m}}(F_{2}-xF_{0})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{3}-xF_{1}}{F_{2}-xF_{0}}\bigg\}^{k_{4}}, \end{align*} $$
and then the binomial sum with respect to
$k_{4}$
in
$\Phi _{m}(n)$
:
$$ \begin{align*}\Phi^{4}_{m}(n)&=\sum_{k_{4}=0}^{n} [x^{n}]\frac{x^{k_{m}}(2-x)^{k_{4}}}{(1-x)^{1+k_{m}}} \binom{n-k_{5}}{k_{4}} =[x^{n}]\frac{x^{k_{m}}(3-x)^{n-k_{5}}}{(1-x)^{1+k_{m}}}\\[4pt] &=[x^{n}]\frac{x^{k_{m}}(F_{4}-xF_{2})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{2}-xF_{0}}{F_{4}-xF_{2}}\bigg\}^{k_{5}}. \end{align*} $$
By means of the induction principle, we can show that for
$1\le j\le m/2$
, the binomial sums with respect to
$k_{2j-1}$
and
$k_{2j-2}$
in
$\Phi _{m}(n)$
are respectively given by
$$ \begin{align*}\Phi^{2j-1}_{m}(n)&=\sum_{k_{2j-1}=0}^{n} \Phi^{2j-2}_{m}(n)\binom{n-k_{2j}}{k_{2j-1}}(-1)^{k_{2j-1}}\\[4pt] &=[x^{n}]\frac{x^{k_{m}}(F_{j}-xF_{j-2})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{j+1}-xF_{j-1}}{F_{j}-xF_{j-2}}\bigg\}^{k_{2j}},\\[4pt] \Phi^{2j-2}_{m}(n)&=\sum_{k_{2j-2}=0}^{n} \Phi^{2j-3}_{m}(n)\binom{n-k_{2j-1}}{k_{2j-2}}\\[4pt] &=[x^{n}]\frac{x^{k_{m}}(F_{j+1}-xF_{j-1})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{j-1}-xF_{j-3}}{F_{j+1}-xF_{j-1}}\bigg\}^{k_{2j}}. \end{align*} $$
According to the parity of m, we can determine
$\Phi _{m}(n)$
separately as follows. For even
$m=2\lambda $
, we can evaluate
$$ \begin{align*}\Phi_{m}(n)&=\sum_{k_{m}=0}^{n}\Phi^{m-1}_{m}(n)\\[4pt] &=\sum_{k_{m}=0}^{n}[x^{n}]\frac{x^{k_{m}}(F_{\lambda}-xF_{\lambda-2})^{n}}{(1-x)^{1+k_{m}}} \bigg\{\frac{F_{\lambda+1}-xF_{\lambda-1}}{F_{\lambda}-xF_{\lambda-2}}\bigg\}^{k_{m}}\\&=[x^{n}]\frac{(F_{\lambda}-xF_{\lambda-2})^{n}}{1-x}\sum_{k_{m}=0}^{\infty} \bigg\{\frac{x(F_{\lambda+1}-xF_{\lambda-1})}{(1-x)(F_{\lambda}-xF_{\lambda-2})}\bigg\}^{k_{m}}\\[4pt] &=[x^{n}]\frac{(F_{\lambda}-xF_{\lambda-2})^{n+1}}{(1-x)(F_{\lambda}-xF_{\lambda-2})-x(F_{\lambda+1}-xF_{\lambda-1})}, \end{align*} $$
which simplifies to
$$ \begin{align*}{\Phi_{m}(n)=[x^{n}]\frac{(F_{\lambda}-xF_{\lambda-2})^{n+1}}{F_{\lambda}(1-3x+x^{2})}}.\end{align*} $$
By means of the Lagrange expansion formula, these expressions can be simplified further. In fact, specialise first in (1.4) by
$$ \begin{align*}F(x)=\frac{F_{\lambda}-xF_{\lambda-2}}{F_{\lambda}(1-3x+x^{2})} \quad\text{and}\quad \varphi(x)=F_{\lambda}-xF_{\lambda-2}.\end{align*} $$
Then we can deduce that
$$ \begin{align*}y=x/\varphi(x)\quad\Longleftrightarrow\quad x=\frac{yF_{\lambda}}{1+yF_{\lambda-2}},\end{align*} $$
together with the generating function
$$ \begin{align*}\frac{F(x(y))}{1-x\varphi^{\prime}(x)/\varphi(x)} &=\frac{F_{\lambda}-xF_{\lambda-2}}{F_{\lambda}(1-3x+x^{2})}\bigg/ \bigg\{1+\frac{xF_{\lambda-2}}{F_{\lambda}-xF_{\lambda-2}}\bigg\}\\[4pt] &=\frac{(F_{\lambda}-xF_{\lambda-2})^{2}}{F^{2}_{\lambda}(1-3x+x^{2})}, \quad\mbox{where } {x=\frac{yF_{\lambda}}{1+yF_{\lambda-2}}}\\[2pt] &=\frac1{1+2yF_{\lambda-2}-3yF_{\lambda}+y^{2}F^{2}_{\lambda} +y^{2}F^{2}_{\lambda-2}-3y^{2}F_{\lambda}F_{\lambda-2}}. \end{align*} $$
After some routine simplification, we find the elegant formula
$$ \begin{align*}\Phi_{m}(n)=[y^{n}]\frac1{1-yL_{\lambda}+(-1)^{\lambda}y^{2}}, \quad\text{where } {m=2\lambda}.\end{align*} $$
Analogously for odd
$m=2\lambda -1$
, we can evaluate
$$ \begin{align*}\Phi_{m}(n)&=\sum_{k_{m}=0}^{n}\Phi^{m-1}_{m}(n)\\[4pt] &=\sum_{k_{m}=0}^{n}[x^{n}]\frac{x^{k_{m}}(F_{\lambda+1}-xF_{\lambda-1})^{n}}{(1-x)^{1+k_{m}}} \bigg\{\hspace{-2.5pt}-\frac{F_{\lambda-1}-xF_{\lambda-3}}{F_{\lambda+1}-xF_{\lambda-1}}\bigg\}^{k_{m}}\\&=[x^{n}]\frac{(F_{\lambda+1}-xF_{\lambda-1})^{n}}{1-x}\sum_{k_{m}=0}^{\infty} \bigg\{\frac{-x(F_{\lambda-1}-xF_{\lambda-3})}{(1-x)(F_{\lambda+1}-xF_{\lambda-1})}\bigg\}^{k_{m}}\\[4pt] &=[x^{n}]\frac{(F_{\lambda+1}-xF_{\lambda-1})^{n+1}}{(1-x)(F_{\lambda+1}-xF_{\lambda-1})+x(F_{\lambda-1}-xF_{\lambda-3})}, \end{align*} $$
which simplifies to
$$ \begin{align*}{\Phi_{m}(n)=[x^{n}]\frac{(F_{\lambda+1}-xF_{\lambda-1})^{n+1}}{F_{\lambda+1}(1-x)+x^{2}F_{\lambda-2}}}.\end{align*} $$
By means of the Lagrange expansion formula, these expressions can be simplified further. In fact, specialise now in (1.4) by
$$ \begin{align*}F(x)=\frac{F_{\lambda+1}-xF_{\lambda-1}}{F_{\lambda+1}(1-x)+x^{2}F_{\lambda-2}} \quad\text{and}\quad \varphi(x)=F_{\lambda+1}-xF_{\lambda-1}.\end{align*} $$
Then we can deduce that
$$ \begin{align*}y=x/\varphi(x)\quad\Longleftrightarrow\quad x=\frac{yF_{\lambda+1}}{1+yF_{\lambda-1}},\end{align*} $$
together with the generating function below
$$ \begin{align*}\frac{F(x(y))}{1-x\varphi^{\prime}(x)/\varphi(x)} &=\frac{F_{\lambda+1}-xF_{\lambda-1}}{F_{\lambda+1}(1-x)+x^{2}F_{\lambda-2}}\bigg/ \bigg\{1+\frac{xF_{\lambda-1}}{F_{\lambda+1}-xF_{\lambda-1}}\bigg\}\\[4pt] &=\frac{(F_{\lambda+1}-xF_{\lambda-1})^{2}}{F^{2}_{\lambda+1}(1-x)+x^{2}F_{\lambda+1}F_{\lambda-2}}, \quad\mbox{where } {x=\frac{yF_{\lambda+1}}{1+yF_{\lambda-1}}}\\[2pt] &=\frac1{1+2yF_{\lambda-1}-yF_{\lambda+1}+y^{2}F^{2}_{\lambda-1} +y^{2}F_{\lambda+1}F_{\lambda-2}-y^{2}F_{\lambda+1}F_{\lambda-1}}. \end{align*} $$
After some routine simplification, we confirm another elegant formula,
$$ \begin{align*}\Phi_{m}(n)=[y^{n}]\frac1{1-yF_{\lambda-2}-(-1)^{\lambda}y^{2}}, \quad\text{where } {m=2\lambda-1}.\end{align*} $$
Hence, both statements of Theorem 2.1 are proved.
3 The second alternating sum
$\boldsymbol {\Psi _{m}(n)}$
Analogously, we can reformulate the circular sum
$\Psi _{m}(n)$
as
$$ \begin{align*}\Psi_{m}(n)=\sum_{0\le k_{1},k_{2},\ldots,k_{m}\le n} (-1)^{\sum k_{2i}}\binom{n-k_{1}}{k_{m}} \prod_{i=1}^{m-1}\binom{n-k_{i+1}}{k_{i}},\end{align*} $$
where
$\sum k_{2i}$
stands for the sum of the even indexed components of
$\mathbf {k}$
. We have the following theorem.
Theorem 3.1 (generating functions).
$$ \begin{align*}\Psi_{m}(n)=\begin{cases} [y^{n}]\dfrac1{1-yL_{\lambda}+(-1)^{\lambda}y^{2}} &\text{if } {m=2\lambda};\\[5mm] [y^{n}]\dfrac1{1-yF_{\lambda+1}+(-1)^{\lambda}y^{2}} &\text{if } {m=2\lambda-1}. \end{cases}\end{align*} $$
Remark 3.2. Comparing the generating functions in Theorems 2.1 and 3.1, we can see that
$\Phi _{m}(n)=\Psi _{m}(n)$
for all
$n\in \mathbb {N}$
when m is even. This is not surprising because in this case, both sums
$\Psi _{m}(n)$
and
$\Phi _{m}(n)$
, defined respectively in (1.3) and (1.2), are equivalent if we reverse the order for the components of
$\mathbf {k}$
. When m is odd, we have instead
$\Psi _{m}(n)=\Phi _{m+6}(n)$
for all
$n\in \mathbb {N}$
.
According to this remark, we have the following summation formulae, where
$\Psi _{5}(n)$
,
$\Psi _{7}(n)$
and
$\Psi _{9}(n)$
are integer sequences A006190, A004254 and A041025, respectively, recorded in [Reference Sloane9]:
$$ \begin{align*}\Psi_{1}(n)&=[y^{n}]\frac1{1-y-y^{2}}=F_{n+1};\\[3pt] \Psi_{3}(n)&=[y^{n}]\frac1{(1-y)^{2}}=n+1;\\[3pt] \Psi_{5}(n)&=[y^{n}]\frac1{1-3y-y^{2}} =\sum_{k=0}^{n}\binom{n-k}{k}3^{n-2k};\\[3pt] \Psi_{7}(n)&=[y^{n}]\frac1{1-5y+y^{2}} =\sum_{k=0}^{n}\binom{n+k+1}{2k+1}3^{k};\\[3pt] \Psi_{9}(n)&=[y^{n}]\frac1{1-8y-y^{2}} =\sum_{k=0}^{n}\binom{n-k}{k}8^{n-2k}. \end{align*} $$
Proof of Theorem 3.1.
We only need to prove the case when m is odd with
$m=2\lambda -1$
. According to the binomial relations
$$ \begin{align*}&\binom{n-k_{2}}{k_{1}} =[x^{k_{1}}](1+x)^{n-k_{2}},\\[3pt] &\binom{n-k_{1}}{k_{m}} =[x^{n-k_{1}}]\frac{x^{k_{m}}}{(1-x)^{1+k_{m}}}, \end{align*} $$
we can express the binomial sum with respect to
$k_{1}$
in
$\Psi _{m}(n)$
as
$$ \begin{align*}\Psi^{1}_{m}(n)&=\sum_{k_{1}=0}^{n} \binom{n-k_{2}}{k_{1}}\binom{n-k_{1}}{k_{m}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(1+x)^{n-k_{2}}}{(1-x)^{1+k_{m}}}. \end{align*} $$
We proceed next with the binomial sum with respect to
$k_{2}$
in
$\Psi _{m}(n)$
:
$$ \begin{align*}\Psi^{2}_{m}(n)&=\sum_{k_{2}=0}^{n} [x^{n}]\frac{x^{k_{m}}(1+x)^{n-k_{2}}}{(1-x)^{1+k_{m}}} \binom{n-k_{3}}{k_{2}}(-1)^{k_{2}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(1+x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{x}{1+x}\bigg\}^{n-k_{3}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}+n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{1+x}{x}\bigg\}^{k_{3}}. \end{align*} $$
Repeat this process for the binomial sums with respect to
$k_{3}$
in
$\Psi _{m}(n)$
:
$$ \begin{align*}\Psi^{3}_{m}(n)&=\sum_{k_{3}=0}^{n} [x^{n}]\frac{x^{k_{m}+n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{1+x}{x}\bigg\}^{k_{3}} \binom{n-k_{4}}{k_{3}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(1+2x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{x}{1+2x}\bigg\}^{k_{4}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(F_{2}+xF_{3})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{0}+xF_{1}}{F_{2}+xF_{3}}\bigg\}^{k_{4}}, \end{align*} $$
and then with respect to
$k_{4}$
in
$\Psi _{m}(n)$
:
$$ \begin{align*}\Psi^{4}_{m}(n)&=\sum_{k_{4}=0}^{n} [x^{n}]\frac{x^{k_{m}}(1+2x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{x}{1+2x}\bigg\}^{k_{4}} \binom{n-k_{5}}{k_{4}}(-1)^{k_{4}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(1+x)^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{1+2x}{1+x}\bigg\}^{k_{5}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(F_{1}+xF_{2})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{2}+xF_{3}}{F_{1}+xF_{2}}\bigg\}^{k_{5}}. \end{align*} $$
By means of the induction principle, we can show that for
$1\le j\le m/2$
, the binomial sums with respect to
$k_{2j-1}$
and
$k_{2j-2}$
in
$\Psi _{m}(n)$
are respectively given by
$$ \begin{align*}\Psi^{2j-1}_{m}(n)&=\sum_{k_{2j-1}=0}^{n} \Psi^{2j-2}_{m}(n)\binom{n-k_{2j}}{k_{2j-1}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(F_{j}+xF_{j+1})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{j-2}+xF_{j-1}}{F_{j}+xF_{j+1}}\bigg\}^{k_{2j}},\\[3pt] \Psi^{2j-2}_{m}(n)&=\sum_{k_{2j-2}=0}^{n} \Psi^{2j-3}_{m}(n)\binom{n-k_{2j-1}}{k_{2j-2}}(-1)^{k_{2j-2}}\\[3pt] &=[x^{n}]\frac{x^{k_{m}}(F_{j-2}+xF_{j-1})^{n}}{(1-x)^{1+k_{m}}} \times\bigg\{\frac{F_{j-1}+xF_{j}}{F_{j-2}+xF_{j-1}}\bigg\}^{k_{2j}}. \end{align*} $$
Since
$m=2\lambda -1$
is odd, we can further evaluate
$$ \begin{align*}\Psi_{m}(n)&=\sum_{k_{m}=0}^{n}\Psi^{m-1}_{m}(n) =\sum_{k_{2\lambda-1}=0}^{n}\Psi^{2\lambda-2}_{2\lambda-1}(n)\\[3pt] &=\sum_{k_{m}=0}^{n}[x^{n}]\frac{x^{k_{m}}(F_{\lambda-2}+xF_{\lambda-1})^{n}}{(1-x)^{1+k_{m}}} \bigg\{\frac{F_{\lambda-1}+xF_{\lambda}}{F_{\lambda-2}+xF_{\lambda-1}}\bigg\}^{k_{m}}\\[3pt] &=[x^{n}]\frac{(F_{\lambda-2}+xF_{\lambda-1})^{n}}{1-x}\sum_{k_{m}=0}^{\infty} \bigg\{\frac{x(F_{\lambda-1}+xF_{\lambda})}{(1-x)(F_{\lambda-2}+xF_{\lambda-1})}\bigg\}^{k_{m}}\\[3pt] &=[x^{n}]\frac{(F_{\lambda-2}+xF_{\lambda-1})^{n+1}}{(1-x)(F_{\lambda-2}+xF_{\lambda-1})-x(F_{\lambda-1}+xF_{\lambda})}, \end{align*} $$
which simplifies to
$$ \begin{align*}{\Psi_{m}(n)=[x^{n}]\frac{(F_{\lambda-2}+xF_{\lambda-1})^{n+1}}{F_{\lambda-2}(1-x)-x^{2}F_{\lambda+1}},\quad m\ne3}.\end{align*} $$
Remark 3.3. When
${m=3}$
, the triple sum
$\Psi _{3}(n)$
results in
$$ \begin{align*}{\Psi_{3}(n)=\sum_{k_{3}=0}^{n} [x^{n}]\frac{x^{k_{3}+n}}{(1-x)^{1+k_{3}}} \times\bigg\{\frac{1+x}{x}\bigg\}^{k_{3}} =[x^{0}]\frac{(\frac{1+x}{1-x})^{n+1}-1}{2x}=n+1}.\end{align*} $$
By means of the Lagrange expansion formula, we can further simplify the generating function for
$\Psi _{m}(n)$
. In fact, specialise in (1.4) by
$$ \begin{align*}F(x)=\frac{F_{\lambda-2}+xF_{\lambda-1}}{F_{\lambda-2}(1-x)-x^{2}F_{\lambda+1}} \quad\text{and}\quad \varphi(x)=F_{\lambda-2}+xF_{\lambda-1}.\end{align*} $$
Then we can deduce that
$$ \begin{align*}y=x/\varphi(x)\quad\Longleftrightarrow\quad x=\frac{yF_{\lambda-2}}{1-yF_{\lambda-1}},\end{align*} $$
together with the generating function
$$ \begin{align*}\frac{F(x(y))}{1-x\varphi^{\prime}(x)/\varphi(x)} &=\frac{F_{\lambda-2}+xF_{\lambda-1}}{F_{\lambda-2}(1-x)-x^{2}F_{\lambda+1}}\bigg/ \bigg\{1-\frac{xF_{\lambda-1}}{F_{\lambda-2}+xF_{\lambda-1}}\bigg\}\\[3pt] &=\frac{(F_{\lambda-2}+xF_{\lambda-1})^{2}}{F^{2}_{\lambda-2}(1-x)-x^{2}F_{\lambda+1}F_{\lambda-2}}, \quad\mbox{where } {x=\frac{yF_{\lambda-2}}{1-yF_{\lambda-1}}}\\[3pt] &=\frac1{1-yF_{\lambda-2}-2yF_{\lambda-1}+y^{2}F^{2}_{\lambda-1} +y^{2}F_{\lambda-1}F_{\lambda-2}-y^{2}F_{\lambda+1}F_{\lambda-2}}. \end{align*} $$
After some routine simplification, we arrive at
$$ \begin{align*}\Psi_{m}(n)=[y^{n}]\frac1{1-yF_{\lambda+1}+(-1)^{\lambda}y^{2}}, \quad\text{where } {m=2\lambda-1},\end{align*} $$
which is also valid for
${m=3}$
. This completes the proof of Theorem 3.1.
4 Open problems
For Carlitz’ identity (1.1), there is a combinatorial proof by Benjamin and Rouse [Reference Benjamin, Rouse and Howard1] through the domino tiling. It would be interesting to construct a similar proof for the identity displayed in Proposition 2.2. Another intriguing problem is to find a combinatorial interpretation of the identity
$\Psi _{m}(n)=\Phi _{m+6}(n)$
for all
$n\in \mathbb {N}$
and odd
$m\in \mathbb {N}$
.
Acknowledgement
The author expresses his sincere gratitude to an anonymous referee for the careful reading and valuable comments.
