The following algebraic identity involving the
Catalan numbers : C_k ={ 1\over{k+1}}{{2k}\choose {k}},\quad k \ge 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 n \geq 0 one has : C_{n+1} = \sum_{k \,\le\, n/2} 2^{n-2k} {n \choose 2k} C_k. \, Using the
generating function : C(t)=\sum_{n \ge 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 : {t \over {1-2t}} C\left({t^2\over (1-2t)^2}\right) = C(t)-1 satisfied by the Catalan generating series C(t). ==References==