اعداد کاتالان
اثبات فرمول

چندین راه برای نشان دادن اینکه چرا فرمول  C_{n}={\frac {1}{n+1}}{2n \choose n} مسائل ترکیبیاتی ذکر شده را حل می‌کند وجود دارد. اولین اثبات از تابع مولد استفاده می‌کند. دومین و سومین اثبات مثال‌هایی از اثبات نگاشت‌های دوطرفه هستند.
می بینیم که تعداد زیادی از مسائل ترکیبیاتی فوق از راه بازگشتی حل می‌شوند.
با استفاده از فرمول  C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\mbox{for }}n\geq 0. می‌توانیم با استفاده از تکنیک‌های شناخته شده برای توابع مولد یک فرمول واضح برای اعداد کاتالان به دست بیاوریم.
با تعریف  f(z) که همه اعداد کاتالان را شامل می‌شود شروع می کنیم:
 f(z)=C_{0}+C_{1}z+C_{2}z^{2}+C_{3}z^{3}+...=C_{n+1}=c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}
اگر (f(z را در خودش ضرب کنیم و  [f(z)]^{2} را به دست بیاوریم، نخستین جملات این چنین هستند:
...+ [f(z)]^{2}=C_{0}C_{0}+(C_{1}C_{0}+C_{0}C_{1})z+(C_{2}C_{0}+C_{1}C_{1}+C_{0}C_{2})z^{2}
ضرایب برای توان‌های z همانهایی هستند که از معادله  C_{n}={\frac {1}{n+1}}{2n \choose n} بر می‌آید
...+ [f(z)]^{2}=C_{1}+C_{2}z+C_{3}z^{2}+C_{4}z^{3}
اگر که (f(z رادر z ضرب کنیم و به آن  C_{0} را بیفزاییم به دست می آوریم:
f(z)=C_{0}+z[f(z)]^{2}
معادله فوق یک معادله درجه دو است که می‌توانیم ان را حل کنیم. آن را به صورت  zf^{2}-f-C_{0}=0 می نویسیم. بنابراین به دست می آوریم:
f(z)={\frac {1-{\sqrt {1-4x}}}{2x}}\quad (8)
توجه کنید که ما علامت منفی را برگزیدیم. چون میدانیم که f(0)=C_{0}=1؛ بنابراین اگر علامت مثبت را جایگذاری کنیم وقتی z→0، آنگاه  f(z)\to \infty
برای بسط از فرمول دوجمله‌ای استفاده می‌کنیم؛ اگر که با استفاده از فرمول دوجمله‌ای با نماهای اعشاری آشنا نیستید، نگران نباشید. دقیقاً همانگونه است؛ با این تفاوت که هیچگاه تمام نمی‌شود.
بیایید به فرمول دوجمله‌ای برای یک نمای صحیح نگاهی بیندازیم و همان محاسبات را برای یک عدد اعشاری انجام دهیم. اگر n یک عدد صحیح باشد، فرمول دوجمله‌ای به این قرار است:
... (a+b)^{n}=a^{n}+{\frac {n}{1}}a^{n-1}b^{1}+{\frac {n(n-1)}{2.1}}a^{n-2}b^{2}+{\frac {n(n-1)(n-2)}{3.2.1}}a^{n-3}b^{3}+
اگرn یک عدد صحیح باشد، صورت کسر سرانجام یک عبارت به صورت (n-n)خواهد داشت؛ بنابراین آن جمله و تمام جملات بعد ازآن صفر خواهند بود. اگر nعدد صحیح نباشد و مثلاً برای مثال ما  {\frac {1}{2}} باشد، صورت کسر صفر را خواهد گذراند و ادامه خواهد یافت. در زیر تعدادی از نخستین جملات بسط آمده اند:
(1-4x)^{({\frac {1}{2}})}=1-{\frac {({\frac {1}{2}})}{1}}4z+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})}{2.1}}(4z)^{2}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})}{3.2.1}}(4z)^{3}+{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})}{4.3.2.1}}(4z)^{4}-{\frac {({\frac {1}{2}})(-{\frac {1}{2}})(-{\frac {3}{2}})(-{\frac {5}{2}})(-{\frac {7}{2}})}{5.4.3.2.1}}(4z)^{5}+...
و به دست می آوریم:
(1-4x)^{\frac {1}{2}}=1-{\frac {1}{1!}}2z-{\frac {1}{2!}}4z^{2}-{\frac {3.1}{3!}}8z^{3}-{\frac {5.3.1}{4!}}16z^{4}-{\frac {7.5.3.1}{5!}}32z^{5}-...\quad (9)
از معادله 8 و 9 داریم:
f(z)=1+{\frac {1}{2!}}2z+{\frac {3.1}{3!}}4z^{2}+{\frac {5.3.1}{4!}}8z^{3}+{\frac {7.5.3.1}{5!}}16z^{4}+...\quad (10)
عباراتی نظیر 7.5.3.1 کمی دردسرسازند. این عبارات شبیه فاکتوریل‌ها هستند؛ اما اعداد زوج را در برندارند. اما توجه کنید که  2^{2}.2!=4.2 و  2^{3}.3!=6.4.2 و  2^{4}.4!=8.6.4.2 و مشابه این. بنابراین
 (7.5.3.1).2^{4}4!=8! . بنابراین اگر این ایده را برای معادله 10 به کار ببریم به دست می آوریم:
f(z)=1+{\frac {1}{2}}{\frac {2!}{1!1!}}z+{\frac {1}{3}}{\frac {4!}{2!2!}}z^{2}+{\frac {1}{4}}{\frac {6!}{3!3!}}z^{3}+{\frac {1}{5}}{\frac {8!}{4!4!}}z^{4}+...=\sum _{i=0}^{\infty }{\frac {1}{i+1}}{2i \choose i}z^{i}
از این عبارت می‌توانیم نتیجه بگیریم که n امین عدد کاتالان با این فرمول به دست می‌آید:
C_{i}={\frac {1}{i+1}}{2i \choose i}