Editing Catalan number (section)

=== First proof ===

We first observe that all of the combinatorial problems listed above satisfy [[Johann Andreas Segner|Segner's]]<ref>A. de Segner, Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula. ''Novi commentarii academiae scientiarum Petropolitanae'' '''7''' (1758/59) 203–209.</ref> [[recurrence relation]]

:<math>C_0 = 1 \quad \text{and} \quad C_{n+1}=\sum_{i=0}^n C_i\,C_{n-i}\quad\text{for }n\ge 0.</math>

For example, every Dyck word {{mvar|w}} of length&nbsp;≥&nbsp;2 can be written in a unique way in the form
:{{math|1=''w'' = X''w''<sub>1</sub>Y''w''<sub>2</sub>}}
with (possibly empty) Dyck words {{math|''w''<sub>1</sub>}} and {{math|''w''<sub>2</sub>}}.

The [[generating function]] for the Catalan numbers is defined by

:<math>c(x)=\sum_{n=0}^\infty C_n x^n.</math>

The recurrence relation given above can then be summarized in generating function form by the relation

:<math>c(x)=1+xc(x)^2;</math>

in other words, this equation follows from the recurrence relation by expanding both sides into [[power series]].  On the one hand, the recurrence relation uniquely determines the Catalan numbers; on the other hand, interpreting {{math|1=''xc''{{sup|2}} − ''c'' + 1 = 0}} as a [[quadratic equation]] of {{mvar|c}} and using the [[quadratic formula]], the generating function relation can be algebraically solved to yield two solution possibilities

:<math>c(x) = \frac{1+\sqrt{1-4x}}{2x}</math> &nbsp;or&nbsp; <math>c(x) = \frac{1-\sqrt{1-4x}}{2x}</math>.

From the two possibilities, the second must be chosen because only the second gives

:<math>C_0 = \lim_{x \to 0} c(x) = 1</math>.

The square root term can be expanded as a power series using the [[binomial series]]

<math display=block>
\begin{align}
1 - \sqrt{1-4x}
& = -\sum_{n=1}^{\infty} \binom{1/2}{n}(-4x)^{n}
= -\sum_{n=1}^{\infty} \frac{(-1)^{n-1}(2n-3)!!}{2^{n}n!}(-4x)^{n} \\
&= -\sum_{n=0}^{\infty} \frac{(-1)^n(2n-1)!!}{2^{n+1}(n+1)!}(-4x)^{n+1}
= \sum_{n=0}^{\infty} \frac{2^{n+1}(2n-1)!!}{(n+1)!}x^{n+1} \\
& = \sum_{n=0}^{\infty} \frac{2(2n)!}{(n+1)!n!}x^{n+1}
= \sum_{n=0}^{\infty} \frac{2}{n+1} \binom{2n}{n}x^{n+1}\,.
\end{align}
</math>
Thus,
<math display=block>
c(x) = \frac{1-\sqrt{1-4x}}{2x} = \sum_{n=0}^{\infty} \frac{1}{n+1} \binom{2n}{n}x^{n}\,.
</math>