Jacques Touchard

The following algebraic identity involving the Catalan numbers

${\displaystyle C_{k}={1 \over {k+1}}{{2k} \choose {k}},\quad k\geq 0}$

is apparently due to Touchard (according to Richard P. Stanley, who mentions it in his panorama article "Exercises on Catalan and Related Numbers" giving an overwhelming plenitude of different definitions for the Catalan numbers). For ${\displaystyle n\geq 0}$ one has

${\displaystyle C_{n+1}=\sum _{k\,\leq \,n/2}2^{n-2k}{n \choose 2k}C_{k}.\,}$

Using the generating function

${\displaystyle C(t)=\sum _{n\geq 0}C_{n}t^{n}={{1-{\sqrt {1-4t}}} \over {2t}}}$

it can be proved by algebraic manipulations of generating series that Touchard's identity is equivalent to the functional equation

${\displaystyle {t \over {1-2t}}C\left({t^{2} \over (1-2t)^{2}}\right)=C(t)-1}$

satisfied by the Catalan generating series ${\displaystyle C(t)}$.