12
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ is there a difference between $c(n,k)$ and $C(n,k)$? $\endgroup$ Aug 15, 2018 at 17:33
  • $\begingroup$ No, sorry, I have changed the typos. $\endgroup$ Aug 15, 2018 at 17:54

1 Answer 1

12
$\begingroup$

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 $(*)$.

$\endgroup$
2
  • $\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$ Aug 16, 2018 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$ Aug 16, 2018 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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