3
$\begingroup$

I need the result that for all $t$,

$$\sum_{i=0}^{\lfloor t/2 \rfloor} (-1)^{i+1} \binom{t-i}{i} C_{t-i-1} = 0,$$

where $C_{t-i-1}$ is the $(t-i-1)$-th Catalan number. I've checked for $t$ up to 1000 using Python and the result holds, but I don't really have an intuition for why it would be true. The terms of this sequence are on OEIS (A068763) but they're simply called a "generalized Catalan sequence".

Does anyone have a name for this sequence or a citation for this result?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The formula (which holds for $t>1$ but not for $t=1$), is equivalent to $$\sum_{t=1}^\infty C_{t-1}\bigl(x(1-x)\bigr)^t = x,$$ which follows directly from the generating function $$\sum_{t=1}^\infty C_{t-1}x^t = \frac{1-\sqrt{1-4x}}{2}.$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah, thank you! My colleague had a very nice combinatorial argument, but this is much more straightforward. $\endgroup$
    – Aaron Li
    Commented Jan 19, 2023 at 19:22
  • $\begingroup$ Denoting the second sum as $xC$, where $C=C(x)=1+xC^2$, another way to put it is that $(xC)\circ(x-x^2)=x$ because $(x-x^2)\circ(xC)=xC-x^2C^2=x$. $\endgroup$
    – Alexander Burstein
    Commented Jan 22, 2023 at 17:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .