Prove that $U_{a+b}=U_aU_b+U_{a-1}U_{b-1}$ for $a\ge1$ and $b\ge1$

Question

I am trying to prove that $U_{a+b}=U_aU_b+U_{a-1}U_{b-1}$ for $a\ge1$ and $b\ge1$, where $U_a$=$\sum_k {a-k\choose k}$.

Therefore $\sum_k {a+b-k\choose k}$=$\sum_k {a-k\choose k}$$\sum_k {b-k\choose k}$ + $\sum_k {a-k-1\choose k}$$\sum_k {b-k-1\choose k}$.

How can I modify the right hand side of the equation to get the left hand side?

Answer 1

We derive a closed formula for a generalisation of $U_m$ which will then be used to prove the identity.

The following is valid for $m\geq 0$ \begin{align*} \sum_{k=0}^{\lfloor m/2\rfloor}\binom{m-k}{k}z^k =\frac{1}{\sqrt{1+4z}}\left(\left(\frac{1+\sqrt{1+4z}}{2}\right)^{m+1} -\left(\frac{1-\sqrt{1+4z}}{2}\right)^{m+1}\right)\tag{1} \end{align*}

It is convenient to use the coefficient of operator $[t^m]$ to denote the coefficient of $t^m$ of a series. We start with the generating function \begin{align*} \frac{1}{1-t-zt^2} \end{align*}

On the one hand it can be shown by partial fraction decomposition \begin{align*} [t^m]\frac{1}{1-t-zt^2} &=[t^m]\frac{1}{\left(1-\frac{1+\sqrt{1+4z}}{2}t\right)\left(1-\frac{1-\sqrt{1+4z}}{2}t\right)}\\ &=\frac{1}{\sqrt{1+4z}}\left(\left(\frac{1+\sqrt{1+4z}}{2}\right)^{m+1}-\left(\frac{1-\sqrt{1+4z}}{2}\right)^{m+1}\right) \end{align*} On the other hand we derive \begin{align*} [t^m]\frac{1}{1-t-zt^2}&=[t^m]\frac{1}{1-t}\cdot\frac{1}{1-\frac{zt^2}{1-t}}\\ &=\frac{1}{1-t}\sum_{j=0}^\infty \frac{z^j t^{2j}}{(1-t)^j}\tag{2}\\ &=\sum_{j=0}^\infty \frac{z^j t^{2j}}{(1-t)^{j+1}}\\ &=\sum_{j=0}^\infty t^{2j}\sum_{l=0}^\infty \binom{-j-1}{l}(-t)^lz^j\tag{3}\\ &=\sum_{j=0}^\infty t^{2j}\sum_{l=0}^\infty \binom{l+j}{l}t^lz^j\tag{4}\\ &=\sum_{j=0}^{\lfloor n/2\rfloor} [t^{n-2j}]\sum_{l=0}^\infty \binom{l+j}{l}t^lz^j\tag{5}\\ &=\sum_{j=0}^{\lfloor n/2\rfloor} \binom{n-j}{n-2j}z^j\tag{6}\\ &=\sum_{j=0}^{\lfloor n/2\rfloor} \binom{n-j}{j}z^j \end{align*} and the claim (1) follows.

Comment:

• In (2) we apply the geometric series expansion.

• In (3) we apply the binomial series expansion.

• In (4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (5) we use the linearity of the coefficient of operator and use the rule $$[t^{p+q}]A(t)=[t^p]t^{-q}A(t)$$ We also restrict the upper limit of the sum since the exponent of $t^{n-2j}$ has to be non-negative.

• In (6) we select the coefficient of $t^{n-2j}$.

We obtain from (1) the following identity by setting $z=1$ \begin{align*} U_m=\sum_{k=0}^{\lfloor m/2\rfloor}\binom{m-k}{k} =\frac{1}{\sqrt{5}\cdot2^{m+1}}\left(\left(1+\sqrt{5}\right)^{m+1}-\left(1-\sqrt{5}\right)^{m+1}\right) \end{align*}

Next we calculate $U_aU_b$ and $U_{a-1}U_{b-1}$.

\begin{align*} U_aU_b&=\frac{1}{5\cdot2^{a+b+2}}\left(\left(1-\sqrt{5}\right)^{a+b+2} -\left(1-\sqrt{5}\right)^{a+1}\left(1+\sqrt{5}\right)^{b+1}\right.\\ &\qquad\qquad\qquad\qquad\left.-\left(1+\sqrt{5}\right)^{a+1}\left(1-\sqrt{5}\right)^{b+1} +\left(1+\sqrt{5}\right)^{a+b+2}\right)\\ &=\frac{1}{5\cdot2^{a+b}}\left( \frac{3-\sqrt{5}}{2}\left(1-\sqrt{5}\right)^{a+b} +\left(1-\sqrt{5}\right)^{a}\left(1+\sqrt{5}\right)^{b}\right.\\ &\qquad\qquad\qquad\qquad\left.+\left(1+\sqrt{5}\right)^{a}\left(1-\sqrt{5}\right)^{b} +\frac{3+\sqrt{5}}{2}\left(1+\sqrt{5}\right)^{a+b}\right)\\ \\ U_{a-1}U_{b-1}&=\frac{1}{5\cdot2^{a+b}}\left(\left(1-\sqrt{5}\right)^{a+b} -\left(1-\sqrt{5}\right)^{a}\left(1+\sqrt{5}\right)^{b}\right.\\ &\qquad\qquad\qquad\qquad\left.-\left(1+\sqrt{5}\right)^{a}\left(1-\sqrt{5}\right)^{b} +\left(1+\sqrt{5}\right)^{a+b}\right)\\ \end{align*}

It follows by collecting equal terms

\begin{align*} U_aU_b+U_{a-1}U_{b-1} &=\frac{1}{5\cdot2^{a+b}}\left( \left(\frac{3-\sqrt{5}}{2}+1\right)\left(1-\sqrt{5}\right)^{a+b}+0\right.\\ &\qquad\qquad\qquad\qquad\left.+0+\left(\frac{3+\sqrt{5}}{2}+1\right)\left(1+\sqrt{5}\right)^{a+b}\right)\\ &=\frac{1}{5\cdot2^{a+b+1}} \left(\left(1+\sqrt{5}\right)^{a+b+1}+\left(1-\sqrt{5}\right)^{a+b+1}\right)\\ &=U_{a+b} \end{align*} and the claim follows.