Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-06T17:54:39.710Z Has data issue: false hasContentIssue false

ALTERNATING CIRCULAR SUMS OF BINOMIAL COEFFICIENTS

Published online by Cambridge University Press:  13 April 2022

WENCHANG CHU*
Affiliation:
School of Mathematics and Statistics, Zhoukou Normal University, Zhoukou, Henan, PR China Current address: Department of Mathematics and Physics, University of Salento (PO Box 193), 73100 Lecce, Italy
Rights & Permissions [Opens in a new window]

Abstract

By combining the generating function approach with the Lagrange expansion formula, we evaluate, in closed form, two multiple alternating sums of binomial coefficients, which can be regarded as alternating counterparts of the circular sum evaluation discovered by Carlitz [‘The characteristic polynomial of a certain matrix of binomial coefficients’, Fibonacci Quart. 3(2) (1965), 81–89].

Type
Research Article
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

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:

(1.1) $$ \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:

(1.2) $$ \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} $$
(1.3) $$ \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*} $$
(1.4) $$ \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.

References

Benjamin, A. T. and Rouse, J. A., ‘Recounting binomial Fibonacci identities’, in: Applications of Fibonacci Numbers: Volume 9: Proceedings of The Tenth International Research Conference on Fibonacci Numbers and Their Applications (ed. Howard, F. T.) (Springer, Dordrecht, 2004), 2528.Google Scholar
Carlitz, L., ‘The characteristic polynomial of a certain matrix of binomial coefficients’, Fibonacci Quart. 3(2) (1965), 8189.Google Scholar
Chu, W., ‘Derivative inverse series relations and Lagrange expansion formula’, Int J. Number Theory 9(4) (2013), 10011013.CrossRefGoogle Scholar
Chu, W., ‘Bell polynomials and nonlinear inverse relations’, Electron. J. Combin. 28(4) (2021), Article no. P4.24.CrossRefGoogle Scholar
Chu, W., ‘Circular sums of binomial coefficients’, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM 115(2) (2021), Article no. 92.Google Scholar
Comtet, L., Advanced Combinatorics (ed. Reidel, D.) (Springer, Dordrecht, 1974).CrossRefGoogle Scholar
Lagrange, J. L., ‘Nouvelle méthode pour résoudre les équations littérales par le moyen des séries’, Mém. Acad. R. Sci. Belles-Lett. Berl. 24 (1770), 251326.Google Scholar
Mikic, J., ‘A proof of the curious binomial coefficient identity which is connected with the Fibonacci numbers’, Open Access J. Math. Theor. Phys. 1(1) (2017), 17.CrossRefGoogle Scholar
Sloane, N. J. A., The On-Line Encyclopedia of Integer Sequences (OEIS). http://oeis.org/.Google Scholar