We give an elementary proof of the curious binomial coefficient identity, which is connected with the Fibonacci numbers, by using system of auxiliary sums and the induction principle. We discover some interesting relations between main sum and auxiliary sums, where appear the Fibonacci numbers. With help of these relations, we found a second order linear recurrence with main sums only. We easily solve this recurrence by using the Binet formula for the Fibonacci numbers and then prove the desired identity.

Keywords: binomial coefficient, fibonacci number, recurrence equation, auxiliary sum, combinatorial identity

We consider the following sum with binomial coefficients:

$S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^n}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$(1)

Where n is a non negative integer and k is a natural number greater than 1. We call this sum $S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$ a main sum. Let us $F_n$ denote the n -th Fibonacci number. Namely,$F_0\mathrm{<mo>=</mo>0}$, $F_1\mathrm{<mo>=</mo>1}$, and $F_n\mathrm{<mo>=</mo>}{F}_{n-1}+F_{n-2}$; if $n\ge 2$. Our main goal is to prove the following identity:

$S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{F_{k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}}{F_k}$(2)

The Identity (2) can be found¹ as the Identity 142; and it arises as a generalization of the Identity 5 (when $k\mathrm{<mo>=</mo>2}$) from the same book. The same variant of the Identity (2), also, can be found in paper² as the Identity 3 (with small error). The Identity (2) is interesting, mainly, because of its connection with the Fibonacci numbers.

There are no many proofs of the Identity (2). It is known that exists¹ a purely combinatorial proof of the Identity (2). We give an elementary proof of the Identity (2) by using system of auxiliary sums and the induction principle.

Method of auxiliary sums is a new method in proving binomial coefficient identities. This method is introduced by the mathematician Jovan Mikic in papers.^3,4 In this paper, we show how the same method works on harder example; such is the Identity (2). In that sense, this proof of the Identity (2) is interesting, particularly, because of a choice of auxiliary sums.

First, we introduce the auxiliary sum $P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, as follows:

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^n}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1-1\end{array}\right)$(3)

We establish our main theorem:

Theorem 1

Let n be a natural number; and let k be a natural number greater than 1. Then the following relations hold between main and auxiliary sum:

$S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_k\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}^n$(4)

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_k\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(5)

From our main theorem, we derive a second order linear recurrence between main sums only. We have:

Corollary 1

Let n be a non negative integer; and let k be a natural number greater than 1. Then the following relation holds:

$S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}{F}_{k+1}+F_{k-1}\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}+\mathrm{<mo\; stretchy="false">(</mo>}{F}_k^2-F_{k-1}\cdot F_{k+1}\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(6)

With initial conditions:

$S_k\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo><mo>=</mo>1}$(7)

$$S_k\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k+1}+F_{k-1}$$(8)

Recall that the Cassini identity states that $F_k^2-F_{k-1}\cdot F_{k+1}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^{k-1}$. By the Cassini identity, the Relation (6) simplifies to

$S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}{F}_{k+1}+F_{k-1}\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}+{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{k-1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(9)

In order to prove main theorem (1), beside the auxiliary sum $P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, we need to define a whole system of auxiliary sums.

Definition 1

Let n be a natural number; and k be a natural number greater than1. Let l be a natural number such that $l\le k+2$. We define auxiliary sums $S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, as follows:

$S_{k\mathrm{,1}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$(10)

$S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_l\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_{l+1}\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{l-1}\\ i_l\end{array}\right)\left(\begin{array}{c}n-i_l\\ i_{l+1}\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$$\mathrm{1<mo><</mo>}l\le k$ (11)

$S_{k\mathrm{,}k+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(12)

$S_{k\mathrm{,}k+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{P}_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(13)

Then we define the following sum:

Definition 2

Let n be a non negative integer; and k be a natural integer greater than 1. We define the sum $S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, as follows:

$S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}0\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ n\end{array}\right)$(14)

In other words, if we set $i_1\mathrm{<mo>=</mo>}n$ in the main sum $S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, we get the sum $S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. In order to calculate the sum $S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, we need to define one more sum:

Definition 3

Let n be a non negative integer; and k be a natural integer greater than 3. Let j be a non negative integer such that $j\le n$. We define the sum ${\Delta }_{k\mathrm{,}j}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, as follows:

${\Delta }_{k\mathrm{,}j}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)\left(\begin{array}{c}n-i_3\\ i_4\end{array}\right)\cdots \left(\begin{array}{c}n-i_{k-2}\\ i_{k-1}\end{array}\right)$(15)

There is a connection between these two sums from the Definition (2) and Definition (3). Namely, when $k\ge 4$, the following equation holds

$S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\Delta }_{k\mathrm{,0}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(16)

The Equation (16) is true because of the fact that $i_1\mathrm{<mo>=</mo>}n$ implies that both i2 and ik must be equal to zero.

Before we prove main theorem (1), we need to prove several lemmas. Here, we give a list of all lemmas which are important for us.

Lemma 1

Let integers n, k, and l be from the Definition (1); with condition $l\le k$. Then the following equation holds

$S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,}l+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,}l+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(17)

Corollary 2

Let integers n, k, and l be from the Defination (1); with condition $l\le k$. Let m be a non negative integer such that $m\le k+1-l$. Then following equations hold

$S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{m+1}\cdot S_{k\mathrm{,}l+m}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+F_m\cdot S_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(18)

$S_{k\mathrm{,1}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_k\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(19)

$S_{k\mathrm{,2}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_k\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(20)

Lemma 2

Let n be a non negative integer; and k be a natural integer greater than 1. The following relation holds

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,2}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(21)

Lemma 3

Let n, k, and j be from the Defination (3). Then the following equation holds:

${\Delta }_{k\mathrm{,}j}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k-2}^j\cdot F_{k-1}^{n-j}$(22)

Lemma 4

Let n and k be from the Defination (2). Then the following equation holds:

$S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k-1}^n$(23)

Our proof of the Equation (17) relies on the well-known Pascal’s formula for binomial coefficients:

$\left(\begin{array}{c}n\\ k\end{array}\right)\mathrm{<mo>=</mo>}\left(\begin{array}{c}n-1\\ k\end{array}\right)+\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$(24)

Where n is a natural number and k may be an arbitrary integer.

Due to the Definition (1), our proof consists of four parts. All proofs of these four parts are very similar. We prove three cases and give a sketch of a proof for the fourth case.

Proof

1. The first case: $l\mathrm{<mo>=</mo>1}$. Since $i_1\le n-1$, we can apply the Pascal formula on the binomial coefficient

$\left(\begin{array}{c}n-i_1\\ i_2\end{array}\right)$.

We have gradually:

$S_{k\mathrm{,1}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\mathrm{<mo\; stretchy="false">(</mo>}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)+\left(\begin{array}{c}n-1-i_1\\ i_2-1\end{array}\right)\mathrm{<mo\; stretchy="false">)</mo>}\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)+$(25)
${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2-1\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$(26)

Note that the first binomial coefficient in the Equation (25) perishes if $i_2\mathrm{<mo>=</mo>}n$. Therefore, we have

${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{S}_{k\mathrm{,2}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>.}$(27)

The Equation (26) becomes gradually:

${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2-1\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>1}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2-1\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{t_2\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ t_2\end{array}\right)\left(\begin{array}{c}n-1-t_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)\mathrm{<mo\; stretchy="false">(</mo>}{t}_2\mathrm{<mo>=</mo>}{i}_2-\mathrm{1<mo\; stretchy="false">)</mo>}$(28)

If $k\mathrm{<mo>=</mo>2}$, then the above sum in the Equation (28) is $S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$according to the Equation (1). Due to the Equation (12) from the Defination (1), we have that $S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,}k+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,3}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$.

If $k\mathrm{<mo>></mo>2}$, then the above sum in the Equation (28) is, as follows:

${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{t_2\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ t_2\end{array}\right)\left(\begin{array}{c}n-1-t_2\\ i_3\end{array}\right)\left(\begin{array}{c}n-i_3\\ i_4\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$

$\mathrm{<mo>=</mo>}{S}_{k\mathrm{,3}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$According to the Defination (1) and the Equation (11). In both cases, the sum in the Equation (28) is equal to $S_{k\mathrm{,3}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. Now, from the Equation (25), (26), (27), and (28), it follows that $S_{k\mathrm{,1}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,2}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,3}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. This proves the first case.

2. The second case: $l\mathrm{<mo>=</mo>}k$. Since $i_k\le n-1$, we can apply the Pascal formula on the binomial coefficient $\left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$. We have gradually:

$S_{k\mathrm{,}k}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^{n-1}}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ i_k\end{array}\right)\left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^{n-1}}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ i_k\end{array}\right)\left(\begin{array}{c}n-1-i_k\\ i_1\end{array}\right)+$
${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^{n-1}}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ i_k\end{array}\right)\left(\begin{array}{c}n-1-i_k\\ i_1-1\end{array}\right)\text{.}$
$\mathrm{<mo>=</mo>}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(29)

According to the Equation (1) and the Equation (3).

According to the Equation (12) and the Equation (13) from the Defination (1), the Equation (29) becomes $S_{k\mathrm{,}k}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,}k+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,}k+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. This proves the second case.

3. The third case: $l\mathrm{<mo>=</mo>}k-1$. Since $i_{k-1}\le n-1$, we can apply the Pascal formula on the binomial coefficient $\left(\begin{array}{c}n-i_{k-1}\\ i_k\end{array}\right)$. We have gradually:

$S_{k\mathrm{,}k-1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-i_{k-1}\\ i_k\end{array}\right)\left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ i_k\end{array}\right)\left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)+$
${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ i_k-1\end{array}\right)\left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)\text{.}$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^{n-1}}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ i_k\end{array}\right)\left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)+$
${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_k\mathrm{<mo>=</mo>1}}^n}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ i_k-1\end{array}\right)\left(\begin{array}{c}n-i_k\\ i_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{S}_{k\mathrm{,}k}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+$
${\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_{k-1}\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{t_k\mathrm{<mo>=</mo>0}}^{n-1}}\left(\begin{array}{c}n-1-i_1\\ i_2\end{array}\right)\cdots \left(\begin{array}{c}n-1-i_{k-1}\\ t_k\end{array}\right)\left(\begin{array}{c}n-1-t_k\\ i_1\end{array}\right)\text{.}$

In the last equation above, we used substitution $t_k\mathrm{<mo>=</mo>}{i}_k-1$. Therefore, from the last equation above, we obtain that

$S_{k\mathrm{,}k-1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,}k}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$

$\mathrm{<mo>=</mo>}{S}_{k\mathrm{,}k}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,}k+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}\text{;}$(30) (by the Equation (12)). The Equation (30) proves the third case.

4. The fourth case: $\mathrm{1<mo><</mo>}l\mathrm{<mo><</mo>}k-1$. This case exists only if $k\mathrm{<mo>></mo>3}$. We give a short sketch of the proof. The proof of this case is very similar to the proof of the first case. We use the Pascal formula on the binomial coefficient $\left(\begin{array}{c}n-i_l\\ i_{l+1}\end{array}\right)$ and we get $\left(\begin{array}{c}n-i_l\\ i_{l+1}\end{array}\right)\mathrm{<mo>=</mo>}\left(\begin{array}{c}n-1-i_l\\ i_{l+1}\end{array}\right)+\left(\begin{array}{c}n-1-i_l\\ i_{l+1}-1\end{array}\right)$. Then the sum $S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$ splits on two sums. It is easy to see that the first sum is $S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$.

For the second sum, we need to introduce the substitution $t_{l+1}\mathrm{<mo>=</mo>}{i}_{l+1}-1$. Then the second sum becomes$S_{k\mathrm{,}l+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. Therefore, it follows that $S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,}l+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,}l+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. This proves the fourth case.

We need to prove Equations. (18), (19), and (20). All these equations are direct consequences of the Equation (17).

A proof of the equation (18)

Proof: We assume that integers n, k, and l are fixed. We give a proof by using the induction principle on m. If $m\mathrm{<mo>=</mo>0}$, then the Equation (18) is satisfied, because $F_0\mathrm{<mo>=</mo>0}$. Thus, we confirm the base of the induction. Let us suppose that the Equation (18) holds for some m such that $0\le m\mathrm{<mo><</mo>}k+1-l$. In other words, our induction hypothesis is $S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{m+1}\cdot S_{k\mathrm{,}l+m}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+F_m\cdot S_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$. Then $l+m\le k$. By the Lemma (1) and the Equation (17), we know that

$S_{k\mathrm{,}l+m}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,}l+m+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(31)

From our induction hypothesis and the Equation (31), we have that

$$S_{k\mathrm{,}l}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{m+1}\cdot S_{k\mathrm{,}l+m}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+F_m\cdot S_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$$
$$\mathrm{<mo>=</mo>}{F}_{m+1}\cdot \mathrm{<mo\; stretchy="false">(</mo>}{S}_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,}l+m+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}+F_m\cdot S_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$$
$$\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{F}_{m+1}+F_m\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+F_{m+1}\cdot S_{k\mathrm{,}l+m+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$$
$$\mathrm{<mo>=</mo>}{F}_{m+2}\cdot S_{k\mathrm{,}l+m+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+F_{m+1}\cdot S_{k\mathrm{,}l+m+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>.}$$

From the last equation above, it follows that Equation (18) is satisfied for $m+1$; where $\mathrm{0<mo><</mo>}m+1\le k+1-l$. Therefore, the step of induction is proved. By the induction principle, the proof of the Equation (18) is completed.

A proof of the equation (19)

Proof: The proof is straightforward. Just set $l\mathrm{<mo>=</mo>1}$ and $m\mathrm{<mo>=</mo>}k$ in the Equation (18). This is allowed, because $m\le k+1-1$, so $m\le k$. From the Equation (18), we get

$S_{k\mathrm{,1}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k+1}\cdot S_{k\mathrm{,}k+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+F_k\cdot S_{k\mathrm{,}k+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$
$\mathrm{<mo>=</mo>}{F}_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_k\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(32)

According to the Equations (12) and (13) from the Defination (1). The Equation (32) is our desired the Equation (19). This proves the Equation (19)

A proof of the equation (20)

Proof: Again, this proof is straightforward. Just set $l\mathrm{<mo>=</mo>2}$ and $m\mathrm{<mo>=</mo>}k-1$ in the Equation (2). Since,$m\le k+1-l$, this is allowed. From the Equation (18), we get

$S_{k\mathrm{,2}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_k\cdot S_{k\mathrm{,}k+1}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+F_{k-1}\cdot S_{k\mathrm{,}k+2}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$
$\mathrm{<mo>=</mo>}{F}_k\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$(33)

According to the Equations (12) and (13) from the Defination (1). The Equation (33) is our desired the Equation (20). This proves the Equation (20) and completes the proof of the Corollary (2).

Proof

This proof immediately follows from the Equation (3) and the Defination (1). We need to introduce the substitution $t_1\mathrm{<mo>=</mo>}{i}_1-1$. We have:

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>0}}^n}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1-1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_1\mathrm{<mo>=</mo>1}}^n}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-i_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ i_1-1\end{array}\right)$

Now, we introduce the substitution $t_1\mathrm{<mo>=</mo>}{i}_1-1$. Then the last equation above becomes

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{t_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-t_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ t_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{t_1\mathrm{<mo>=</mo>0}}^{n-1}}{\displaystyle \sum _{i_2\mathrm{<mo>=</mo>0}}^{n-1}}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-1-t_1\\ i_2\end{array}\right)\left(\begin{array}{c}n-i_2\\ i_3\end{array}\right)\cdots \left(\begin{array}{c}n-i_k\\ t_1\end{array}\right)$
$\mathrm{<mo>=</mo>}{S}_{k\mathrm{,2}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$(34)

According to the Equation (11) from the Defination (1). The Equation (34) completes the proof of the Lemma (2).

Proof

We give a proof of the Lemma (3) by using the induction principle on k. We start with $k\mathrm{<mo>=</mo>4}$. By the Defination (3), we have

$${\Delta }_{\mathrm{4,}j}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)$$
$$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^{n-j}}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)$$
$${\mathrm{<mo>=</mo>2}}^{n-j}\mathrm{<mo\; stretchy="false">(</mo>}\text{bythebinomialtheorem}\mathrm{<mo\; stretchy="false">)</mo>}$$
$$\mathrm{<mo>=</mo>}{F}_2^j\cdot F_3^{n-j}$$
$$\mathrm{<mo>=</mo>}{F}_{\mathrm{<mo\; stretchy="false">(</mo>4}-\mathrm{2<mo\; stretchy="false">)</mo>}}^j\cdot F_{\mathrm{<mo\; stretchy="false">(</mo>4}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j}\text{.}$$

The last equation above proves the base of induction. Let us suppose that the Equation (22) holds for some $k\ge 4$. This is our induction hypothesis. Let us consider ${\Delta }_{k+\mathrm{1,}j}$.

${\Delta }_{k+\mathrm{1,}j}\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^n}{\displaystyle \sum _{i_4\mathrm{<mo>=</mo>0}}^n}\dots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)\left(\begin{array}{c}n-i_3\\ i_4\end{array}\right)\cdots \left(\begin{array}{c}n-i_{k-1}\\ i_k\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-j\\ i_3\end{array}\right){\displaystyle \sum _{i_4\mathrm{<mo>=</mo>0}}^n}\cdots {\displaystyle \sum _{i_k\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-i_3\\ i_4\end{array}\right)\cdots \left(\begin{array}{c}n-i_{k-1}\\ i_k\end{array}\right)$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)\cdot {\Delta }_{k\mathrm{,}{i}_3}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>.}$(35)

By the induction hypothesis, it follows that

${\Delta }_{k\mathrm{,}{i}_3}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k-2}^{i_3}\cdot F_{k-1}^{n-i_3}$(36)

By the Equation (36), the Equation (35) becomes

${\Delta }_{k+\mathrm{1,}j}\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^n}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)\cdot F_{k-2}^{i_3}\cdot F_{k-1}^{n-i_3}$
$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^{n-j}}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)\cdot F_{k-2}^{i_3}\cdot F_{k-1}^{n-i_3}$
$\mathrm{<mo>=</mo>}{F}_{k-1}^j\cdot {\displaystyle \sum _{i_3\mathrm{<mo>=</mo>0}}^{n-j}}\left(\begin{array}{c}n-j\\ i_3\end{array}\right)\cdot F_{k-2}^{i_3}\cdot F_{k-1}^{n-j-i_3}$
$\mathrm{<mo>=</mo>}{F}_{k-1}^j\cdot {\mathrm{<mo\; stretchy="false">(</mo>}{F}_{k-2}+F_{k-1}\mathrm{<mo\; stretchy="false">)</mo>}}^{n-j}\mathrm{<mo\; stretchy="false">(</mo>}\text{bythebinomialtheorem}\mathrm{<mo\; stretchy="false">)</mo>}$
$\mathrm{<mo>=</mo>}{F}_{k-1}^j\cdot F_k^{n-j}\text{.}$(37)

The Equation (37) proves the step of the induction principle. This completes the proof of the Lemma (3).

It is easily verified, by direct calculation, that

$S_{\mathrm{2,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>1}\text{;}$

$S_{\mathrm{3,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>1.}$

So, we can conclude, from the above equations, that

$S_{\mathrm{2,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_1^n\text{;}$(38)

$S_{\mathrm{3,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_2^n\text{.}$(39)

Therefore, the Equation (22) is true, when $k\mathrm{<mo>=</mo>2}$ and $k\mathrm{<mo>=</mo>3}$.

Now, let us suppose that $k\ge 4$. According to the Equations (16) and (22), we have that

$S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\Delta }_{k\mathrm{,0}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}\text{bytheEquation (16)}\mathrm{<mo\; stretchy="false">)</mo>}$
$\mathrm{<mo>=</mo>}{F}_{k-2}^0\cdot F_{k-1}^{n-0}\mathrm{<mo\; stretchy="false">(</mo>}\text{bytheEquation (16)}\mathrm{<mo\; stretchy="false">)</mo>}$
$\mathrm{<mo>=</mo>}{F}_{k-1}^n\text{.}$(40)

The Equations (38), (39), and (40) prove the Equation (23). This completes the proof of the Lemma (4).

Proof

Let n be a natural number. First, we prove the Equation (4). Due to the Equation (10) from the Defination (1) and the Defination (3), we know that:

$S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_{k\mathrm{,1}}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+S_{k\mathrm{,}{i}_1\mathrm{<mo>=</mo>}n}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>.}$       (41)

By Equations (19) and (23), the Equation (41) becomes $S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}{F}_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_k\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}+F_{k-1}^n$. The last equation above proves the Equation (4). Now, we prove the Equation (5). The proof of the Equation (5) immediately follows from the Equations (20) and (21).

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}\text{bytheEquation (21)}\mathrm{<mo\; stretchy="false">)</mo>}$
$\mathrm{<mo>=</mo>}{F}_k\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}\cdot P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>.<mo\; stretchy="false">(</mo>}\text{bytheEquation (22)}\mathrm{<mo\; stretchy="false">)</mo>}$

The last equation above proves the Equation (5). This completes the proof of the Theorem (1).

Proof

The Corollary (1) directly follows from the Theorem (1) and from its Equations (4) and (5). Let us suppose that n is a natural number. First, we prove the Equation (6). We express sums $P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$ and $P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}$ by main sums with help of the Equation (4). Then we use the Equation (5), in order to get relation between main sums only. First, from the Equation (4), we obtain that:

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}-F_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k-1}^n}{F_k}\text{.}$(42)

If we use the substitution $n-\mathrm{1<mo>=</mo>}t$, the Equation (42) becomes

$P_k\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{S_k\mathrm{<mo\; stretchy="false">(</mo>}t+\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}-F_{k-1}^{t+1}}{F_k}\text{;}$(43)

Where t is a non negative integer. Therefore, when n is a natural number, the Equation (43) implies that

$P_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}-F_{k-1}^{n+1}}{F_k}\text{.}$(44)

Now, we use the Equation (5). By Equations (42) and (44), the Equation (5) becomes gradually:

$$\frac{S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}-F_{k-1}^{n+1}}{F_k}\mathrm{<mo>=</mo>}{F}_k\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}\cdot \frac{S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}-F_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k-1}^n}{F_k}$$

$$S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k+1}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}-F_{k-1}^{n+1}\mathrm{<mo>=</mo>}{F}_k^2{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}\mathrm{<mo\; stretchy="false">(</mo>}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}-F_{k+1}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k-1}^n\mathrm{<mo\; stretchy="false">)</mo>}$$

$$S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}-F_{k+1}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_k^2{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}+F_{k-1}\mathrm{<mo\; stretchy="false">(</mo>}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}-F_{k+1}{S}_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$$

$$S_k\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}{F}_{k+1}+F_{k-1}\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}+\mathrm{<mo\; stretchy="false">(</mo>}{F}_k^2-F_{k-1}\cdot F_{k+1}\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>.}$$

If we use the substitution $n-\mathrm{1<mo>=</mo>}t$, the last equation above becomes

$S_k\mathrm{<mo\; stretchy="false">(</mo>}t+\mathrm{2<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}{F}_{k+1}+F_{k-1}\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}t+\mathrm{1<mo\; stretchy="false">)</mo>}+\mathrm{<mo\; stretchy="false">(</mo>}{F}_k^2-F_{k-1}\cdot F_{k+1}\mathrm{<mo\; stretchy="false">)</mo>}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>}t\mathrm{<mo\; stretchy="false">)</mo>}\text{;}$(45)

Where t is a non negative integer. The Equation (45) is same as the Equation (6). Therefore, the Equation (6) is proved. Now, we prove Equations (7) and (8). The Equation (7) directly follows from the Equation (1). Obviously, from the Equation (3), it follows that

$P_k\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo><mo>=</mo>0}$(46)

Therefore, the Equation (8) follows from Equations. (4), (7), and (46). We set $n\mathrm{<mo>=</mo>1}$ in the Equation (4)

$S_k\mathrm{<mo\; stretchy="false">(</mo>1<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{k+1}\cdot S_k\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}+P_k\mathrm{<mo\; stretchy="false">(</mo>0<mo\; stretchy="false">)</mo>}+F_{k-1}^1$
$\mathrm{<mo>=</mo>}{F}_{k+1}\cdot 1+0+F_{k-1}$
$\mathrm{<mo>=</mo>}{F}_{k+1}+F_{k-1}\text{.}$

The last equation above proves the Equation (8). This proves the Corollary (1).

Finally, we prove our main Identity (2). We use the Corollary (1) and the Binet formula for the Fibonacci numbers. Recall that the Binet formula states that

$F_n\mathrm{<mo>=</mo>}\frac{1}{\sqrt{5}}\cdot \mathrm{<mo\; stretchy="false">[</mo><mo\; stretchy="false">(</mo>}\frac{1+\sqrt{5}}{2}{\mathrm{<mo\; stretchy="false">)</mo>}}^n-{\mathrm{<mo\; stretchy="false">(</mo>}\frac{1-\sqrt{5}}{2}\mathrm{<mo\; stretchy="false">)</mo>}}^n\mathrm{<mo\; stretchy="false">]</mo>}$(47)

Further, we use facts that

${\mathrm{<mo\; stretchy="false">(</mo>}\frac{1+\sqrt{5}}{2}\mathrm{<mo\; stretchy="false">)</mo>}}^k\mathrm{<mo>=</mo>}\frac{F_{k+1}+F_{k-1}+F_k\cdot \sqrt{5}}{2}\text{;}$(48)

${\mathrm{<mo\; stretchy="false">(</mo>}\frac{1-\sqrt{5}}{2}\mathrm{<mo\; stretchy="false">)</mo>}}^k\mathrm{<mo>=</mo>}\frac{F_{k+1}+F_{k-1}-F_k\cdot \sqrt{5}}{2}\text{.}$(49)

Namely, Equations (48) and (49) are consequences of following relations:

${\mathrm{<mo\; stretchy="false">(</mo>}\frac{1+\sqrt{5}}{2}\mathrm{<mo\; stretchy="false">)</mo>}}^k\mathrm{<mo>=</mo>}{F}_k\cdot \mathrm{<mo\; stretchy="false">(</mo>}\frac{1+\sqrt{5}}{2}\mathrm{<mo\; stretchy="false">)</mo>}+F_{k-1}\text{;}$

${\mathrm{<mo\; stretchy="false">(</mo>}\frac{1-\sqrt{5}}{2}\mathrm{<mo\; stretchy="false">)</mo>}}^k\mathrm{<mo>=</mo>}{F}_k\cdot \mathrm{<mo\; stretchy="false">(</mo>}\frac{1-\sqrt{5}}{2}\mathrm{<mo\; stretchy="false">)</mo>}+F_{k-1}\text{;}$