Editing Catalan number (section)

== Properties ==
An alternative expression for {{math|''C''<sub>''n''</sub>}} is
:<math>C_n = {2n\choose n} - {2n\choose n+1}</math> for <math>n\ge 0\,,</math>
which is equivalent to the expression given above because <math>\tbinom{2n}{n+1}=\tfrac{n}{n+1}\tbinom{2n}n</math>.  This expression shows that {{math|''C''<sub>''n''</sub>}} is an [[integer]], which is not immediately obvious from the first formula given.  This expression forms the basis for a [[#Second proof|proof of the correctness of the formula]].

Another alternative expression is
:<math>C_n = \frac{1}{2n+1} {2n+1\choose n}\,,</math>
which can be directly interpreted in terms of the [[cycle lemma]]; see below.

The Catalan numbers satisfy the [[recurrence relation]]s
:<math>C_0 = 1 \quad \text{and} \quad C_{n}=\sum_{i=1}^{n}C_{i-1}C_{n-i}\quad\text{for }n > 0</math>
and
:<math>C_0 = 1 \quad \text{and} \quad C_{n} = \frac{2(2n-1)}{n+1}C_{n-1}\quad\text{for }n > 0.</math>

Asymptotically, the Catalan numbers grow as
<math display=block>C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}\,,</math>
in the sense that the quotient of the {{mvar|n}}-th Catalan number and the expression on the right tends towards 1 as {{mvar|n}} approaches infinity.

This can be proved by using the [[central binomial coefficient#Asymptotic growth|asymptotic growth of the central binomial coefficients]], by [[Stirling's approximation]] for <math>n!</math>, or [[Generating function#Asymptotic growth of the Catalan numbers|via generating functions]].

The only Catalan numbers {{math|''C''<sub>''n''</sub>}} that are odd are those for which {{math|1=''n'' = 2<sup>''k''</sup> − 1}}; all others are even.  The only prime Catalan numbers are {{math|1=''C''<sub>2</sub> = 2}} and {{math|1=''C''<sub>3</sub> = 5}}.<ref>{{Cite journal|title = Parity and primality of Catalan numbers |last1 = Koshy|first1 = Thomas |last2 = Salmassi|first2 = Mohammad |journal=The College Mathematics Journal|year=2006|volume=37|issue=1|pages = 52–53|doi = 10.2307/27646275|jstor = 27646275|url=https://www.maa.org/sites/default/files/Koshy-CMJ-2006.pdf}}</ref> More generally, the multiplicity with which a prime {{mvar|p}} divides {{math|''C''{{sub|''n''}}}} can be determined by first expressing {{math|''n'' + 1}} in base {{mvar|p}}. For {{math|1=''p'' = 2}}, the multiplicity is the number of 1 bits, minus 1. For {{mvar|p}} an odd prime, count all digits greater than {{math|(''p'' + 1) / 2}}; also count digits equal to {{math|(''p'' + 1) / 2}} unless final; and count digits equal to {{math|(''p'' − 1) / 2}} if not final and the next digit is counted.<ref>{{Cite OEIS|A000108|Catalan numbers}}</ref> The only known odd Catalan numbers that do not have last digit 5 are {{math|1=''C''<sub>0</sub> = 1}}, {{math|1=''C''<sub>1</sub> = 1}}, {{math|1=''C''<sub>7</sub> = 429}}, {{math|''C''<sub>31</sub>}}, {{math|''C''<sub>127</sub>}} and {{math|''C''<sub>255</sub>}}. The odd Catalan numbers, {{math|''C''<sub>''n''</sub>}} for {{math|1=''n'' = 2<sup>''k''</sup> − 1}}, do not have last digit 5 if {{math|''n'' + 1}} has a base 5 representation containing 0, 1 and 2 only, except in the least significant place, which could also be a 3.<ref>{{cite web | url=https://mathworld.wolfram.com/CatalanNumber.html | title=Catalan Number }}</ref>

The Catalan numbers have the integral representations<ref>{{citation
 | last1 = Choi | first1 = Hayoung
 | last2 = Yeh | first2 = Yeong-Nan
 | last3 = Yoo | first3 = Seonguk
 | arxiv = 1809.07523
 | doi = 10.1016/j.disc.2019.111808
 | issue = 5
 | journal = Discrete Mathematics
 | mr = 4052255
 | pages = 111808, 11
 | title = Catalan-like number sequences and Hausdorff moment sequences
 | volume = 343
 | year = 2020| s2cid = 214165563
 }}, Example 3.1</ref><ref>{{citation
 | last1 = Feng | first1 = Qi
 | last2 = Bai-Ni | first2 = Guo
 | title = Integral Representations of the Catalan Numbers and Their Applications
 | journal = Mathematics
 | date = 2017
 | volume = 5
 | issue = 3
 | page = 40
 | doi = 10.3390/math5030040
 | doi-access = free
 }},Theorem 1</ref>

:<math>C_n=\frac {1}{2\pi}\int_0^4 x^n\sqrt{\frac{4-x}{x}}\,dx\,
=\frac{2}{\pi}4^n\int_{-1}^{1} t^{2n}\sqrt{1-t^2}\,dt.
</math>
which immediately yields <math>\sum_{n=0}^\infty \frac{C_n}{4^n} = 2</math>.

This has a simple probabilistic interpretation. Consider a random walk on the integer line, starting at 0. Let -1 be a "trap" state, such that if the walker arrives at -1, it will remain there. The walker can arrive at the trap state at times 1, 3, 5, 7..., and the number of ways the walker can arrive at the trap state at time <math>2k+1</math> is <math>C_k</math>. Since the 1D random walk is recurrent, the probability that the walker eventually arrives at -1 is <math>\sum_{n=0}^\infty \frac{C_n}{2^{2n+1}} = 1</math>.