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?

  • $\begingroup$ is there a difference between $c(n,k)$ and $C(n,k)$? $\endgroup$ – Carlo Beenakker Aug 15 '18 at 17:33
  • $\begingroup$ No, sorry, I have changed the typos. $\endgroup$ – 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 $(*)$.

  • $\begingroup$ @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? $\endgroup$ – Johann Cigler Aug 16 '18 at 19:03
  • $\begingroup$ @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$. $\endgroup$ – Gjergji Zaimi Aug 16 '18 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.