# A matrix identity related to Catalan numbers

Let $$C_n=\frac{1}{2n+1}\binom{2n+1}{n}$$ be a Catalan number. It is well-known that $$(\sum_{n\ge{0}}C_n x^n)^k=\sum_{n\ge{0}}C(n,k)x^n$$ with $$C(n,k)=\frac{k}{2n+k}\binom{2n+k}{n}.$$ It is also known that the Hankel matrix $\left( {{C(i+j,2)}} \right)_{i,j = 0}^{n - 1}$ can be factored in the form $$\left( {{C(i+j,2)}} \right)_{i,j = 0}^{n - 1}=A_{n} A_{n}^T,$$ where

$$A_{n}=\left(\binom{2i+1}{i-j}\frac{2(j+1)}{i+j+2}\right) _{i,j = 0}^{n - 1}=\left(\binom{2i+1}{i-j}-\binom{2i+1}{i-j-1}\right) _{i,j = 0}^{n - 1}.$$

Computer experiments suggest that for $k\ge{1}$ $$\left( {{C(i+j,k+2)}} \right)_{i,j = 0}^{n - 1}=A_{n}G_{n,k} A_{n}^T$$ with $$G_{n,k}=\left({g(i,j,k)}\right) _{i,j = 0}^{n - 1},$$ where $$g(i,j,k)= \sum_{m={|i-j|-1}}^{i+j}\binom{k-1}{m}.$$ Is there a simple proof of this identity?

• is there a difference between $c(n,k)$ and $C(n,k)$? – Carlo Beenakker Aug 15 '18 at 17:33
• No, sorry, I have changed the typos. – Johann Cigler Aug 15 '18 at 17:54

After unpacking the equation $$\left( {{C(i+j,k+2)}} \right)_{i,j = 0}^{n - 1}=A_{n}G_{n,k} A_{n}^T$$ we see that we want to prove the identity $$C(i+j,k+2)=\frac{k+2}{(2i+2j+k+2)}\binom{2i+2j+k+2}{i+j}$$ $$=\sum_{0\le r\le i,0\le s\le j} \left[\binom{2i+1}{i-r}-\binom{2i+1}{i-r-1}\right]\cdot\left[\sum_{m=|r-s|-1}^{r+s}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s}-\binom{2j+1}{j-s-1}\right] \tag{*}$$ The left hand side is the coefficient of $x^{-1-k}$ in $F(x)=(1-x^2)\left(x+\frac{1}{x}\right)^{2i+2j+k+1}$. We will be done if we can show that the right hand side is the coefficient of $x^{-1-k}$ in $$\left[(1-x^2)\left(x+\frac{1}{x}\right)^{2i+1}\right]\cdot\left[\frac{1}{1-x^2}\left(x+\frac{1}{x}\right)^{k-1}\right]\cdot\left[(1-x^2)\left(x+\frac{1}{x}\right)^{2j+1}\right]$$ which is easily seen to also equal $F(x)$. If we fix $r\le i,s\le j$, the contribution that comes from monomials of the form $x^{-1-2r}x^{2r+2s-k+1}x^{-1-2s}$ is $$\left[\binom{2i+1}{i-r}-\binom{2i+1}{i-r-1}\right]\cdot\left[\sum_{m\le r+s}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s}-\binom{2j+1}{j-s-1}\right]$$ which is nonzero in the case $r\geq 0,s\geq 0$, or $r\geq -s\geq 1$, or $s\geq -r\geq 1$. The second case can be rewritten with $s'=-s-2$ as $$-\left[\binom{2i+1}{i-r}-\binom{2i+1}{i-r-1}\right]\cdot\left[\sum_{m\le r-s'-2}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s'}-\binom{2j+1}{j-s'-1}\right]$$ and the third case can be written with $r'=-r-2$ as $$-\left[\binom{2i+1}{i-r'}-\binom{2i+1}{i-r'-1}\right]\cdot\left[\sum_{m\le s-r'-2}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s}-\binom{2j+1}{j-s-1}\right]$$ Combining everything together we see that for $r\geq s$ the total contribution simplifies to $$\left[\binom{2i+1}{i-r}-\binom{2i+1}{i-r-1}\right]\cdot\left[\sum_{m\le r+s}\binom{k-1}{m}-\sum_{m\le r-s-2}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s}-\binom{2j+1}{j-s-1}\right]$$ $$=\left[\binom{2i+1}{i-r}-\binom{2i+1}{i-r-1}\right]\cdot\left[\sum_{m= r-s-1}^{r+s}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s}-\binom{2j+1}{j-s-1}\right]$$ and similarly for $s\geq r$ we get $$\left[\binom{2i+1}{i-r}-\binom{2i+1}{i-r-1}\right]\cdot\left[\sum_{m\le r+s}\binom{k-1}{m}-\sum_{m\le s-r-2}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s}-\binom{2j+1}{j-s-1}\right]$$ $$=\left[\binom{2i+1}{i-r}-\binom{2i+1}{i-r-1}\right]\cdot\left[\sum_{m= s-r-1}^{r+s}\binom{k-1}{m}\right]\cdot \left[\binom{2j+1}{j-s}-\binom{2j+1}{j-s-1}\right]$$ which is exactly the right hand side in $(*)$.
• @gjergij: This seems to be an ingenious proof. Unfortunately I don*t see how the last two lines imply $m\ge{|r-s|-1}.$. Could you please give some more details? – Johann Cigler Aug 16 '18 at 19:03
• @JohannCigler Suppose $r\geq s$. From the first case we have a contribution $(\cdot)(\sum_{m\le r+s}\cdot)(\cdot)$, and from the second case we have a contribution $-(\cdot)(\sum_{m\le r-s-2}\cdot)(\cdot)$ which in total simplifies to $(\cdot)(\sum_{m= r-s-1}^{r+s}\cdot)(\cdot)$. A similar calculation gets the same result when $r\le s$. – Gjergji Zaimi Aug 16 '18 at 20:33