Catalan Numbers

Factorial definition

C_{n} = \frac{( 2 n )!}{( n + 1 )! n !}

$C_{n} = \sum_{i = 1}^{n} C_{i - 1} \cdot C_{n - i}$

If the base case and the induction step (everything up to current case) is true, then $S_{n + 1}$ is true.

eval base case $n = 1$ , get $2 > 1$ , which is true

Assume $2^{k} > k$ . We want to show $2^{k + 1} > k + 1$ .

Multiply both sides by 2 to get $2^{k + 1} > 2 k$ . Since $k > 1$ , $2 k > k + 1$ . Therefore, $2^{k + 1} > k + 1$ .