Recreation with Catalan

Question

Consider the well-known sequence $C_k=\frac1{k+1}\binom{2k}k$ of Catalan numbers. I came across the below identity while working with certain generating functions. I thought it might be of interest to some folks here. Define the finite sum $$f_n:=\sum_{k\geq0}\binom{2n}{n-3k-2}.$$

QUESTION. Is this true? If so, is there a combinatorial proof to it? $$f_{n+2}-5f_{n+1}+4f_n=C_n.$$

Answer 1

We have $$f_{n+1} = \sum_{k\geq 0}\binom{2n+2}{n-3k-1} = \sum_{k\geq 0}\left(\binom{2n}{n-3k-3}+2\binom{2n}{n-3k-2}+\binom{2n}{n-3k-1}\right)$$ $$f_{n+2} = \sum_{k \geq 0} \binom{2n+4}{n-3k} = \sum_{k \geq 0} \left(\binom{2n}{n-3k-4}+4\binom{2n}{n-3k-3}+6\binom{2n}{n-3k-2} + 4\binom{2n}{n-3k-1} + \binom{2n}{n-3k}\right)$$ So $$f_{n+2} + 4f_n - 5f_{n+1} = \sum_{k \geq 0} \left(\binom{2n}{n-3k-4}- \binom{2n}{n-3k-3} - \binom{2n}{n-3k-1} + \binom{2n}{n-3k}\right)$$ and it can be seen that this sum telescopes to $\binom{2n}{n} - \binom{2n}{n-1} = C_n$.

Answer 2

Here's a sketch of a generating function proof. Recall that \begin{equation*} \sum_{m=0}^\infty \binom{2m+k}{m} x^m =\frac{c(x)^k}{\sqrt{1-4x}}, \end{equation*} where $c(x) = \sum_{n=0}^\infty C_n x^n$. Then \begin{align*} \sum_{n=0}^\infty f_n x^n &= \sum_{n,k\ge0}\binom{2n}{n-3k-2} x^n \\ &=\sum_{m,k\ge0}\binom{2m+6k+4}{m}x^{m+3k+2}\\ &=\sum_{k\ge0}x^{3k+2}\frac{c(x)^{6k+4}}{\sqrt{1-4x}}\\ &=\frac{x^2c(x)^4}{\sqrt{1-4x}(1-x^3 c(x)^6)} \end{align*} Simplifying (with the help of Maple) yields $$\frac{x^2 c(x)}{1-5x+4x^2}$$ from which the recurrence follows.

Update: Here is an explanation and generalization for the mysterious simplification described above. Let $\def\sq{\sqrt{1-4x}}$ \begin{align} p_n(x) &=\frac 1{\sq}\left[\left(\frac{1+\sq}{2}\right)^n\ -\left(\frac{1-\sq}{2}\right)^n\,\right]\tag{1}\\ &= \frac{c(x)^{-n}-(xc(x))^n}{\sq} = c(x)^{-n}\frac{1-x^nc(x)^{2n}}{\sq}.\tag{2} \end{align} By expanding $(1)$ in powers of $\sq$, we see that for $n>0$, $p_n(x)$ is a polynomial in $x$ of degree $\lfloor (n-1)/2\rfloor$. It can be shown that for $n>0$, $$p_n(x) =\sum_{i=0}^{\lfloor(n-1)/2\rfloor}(-1)^i \binom {n-i-1}{i}x^i.$$ We can express $p_n(x)$ for $n>0$ in terms of the Chebyshev polynomial of the second kind $U_n(x)$ by $$ p_n(x) = (-1)^{n-1}x^{(n-1)/2}U_{n-1}\left(-\frac{1}{2\sqrt x}\right). $$ It follows from $(2)$ that $$\frac{1}{p_n(x)} = \sq \frac{c(x)^n}{1-x^nc(x)^{2n}}$$ so \begin{equation} \frac{1}{(1-4x)p_n(x)} = \frac{c(x)^n}{\sq(1-x^nc(x)^{2n})}.\tag{3} \end{equation} Since $p_3(x) = 1-x$ and $(1-4x)p_3(x) = 1-5x+4x^2$, the case $n=3$ of $(3)$ is \begin{equation*} \frac{1}{1-5x+4x^2}=\frac{c(x)^3}{\sq(1-x^3 c(x)^6)}. \end{equation*}