(1)

\(n+1\)組の括弧()があるとき、1番目は必ず左括弧(であり、その左括弧に対応する右括弧)の間に\(k\)組の括弧（）があるとすると、それ以降は\(n-k\)組の括弧の組み合わせとなる。
このとき、\(k\)は\(0,1,\cdots n\)の値をとるので、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となり
\begin{align*} 1 & =C_{1}\\ & =C_{0}^{2} \end{align*} より、
\[ C_{0}=1 \] とすればカタラン数になる。
従って、題意は成り立つ。

(2)

縦横\(n\)マスとすると格子の線は縦横\(n+1\)個となり、開始点を\(\left(0,0\right)\)、終了点を\(\left(n,n\right)\)とする。
最初に対角線上を通る位置を\(\left(k,k\right)\)とすると、\(\left(0,0\right)\rightarrow\left(1,0\right)\rightarrow\left(k,k-1\right)\rightarrow\left(k,k\right)\)までを進み、\(\left(k,k\right)\)から\(\left(n,n\right)\)までを進む。
このとき\(C_{k-1+1-1}C_{n-k+1-1}=C_{k-1}C_{n-k}\)通りの最短経路がある。
これを\(k\)について1から\(n\)まで総和をとれば、
\begin{align*} C_{n} & =\sum_{k=1}^{n}C_{k-1}C_{n-k}\\ & =\sum_{k=0}^{n-1}C_{k}C_{n-k-1} \end{align*} となり、\(n\rightarrow n+1\)とすれば、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また、\(C_{1}=1\)なので\(C_{0}=1\)とする。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。

(3)

\(n+1\)人でトーナメントを行い、決勝戦の左側に\(k+1\)人、右側に\(n+1-\left(k+1\right)=n-k\)人あるとすると、このとき\(C_{k}C_{n-k-1}\)通りある。
これを\(k\)について0から\(n-1\)まで総和をとれば、
\begin{align*} C_{n} & =\sum_{k=0}^{n-1}C_{k}C_{n-k-1} \end{align*} となり、\(n\rightarrow n+1\)とすれば、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また、\(C_{1}=1\)なので\(C_{0}=1\)とする。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。

(4)

凸\(n+3\)角形の頂点を\(A_{0},A_{1},\cdots,A_{n+1},A_{n+2}\)とする。
この頂点より、3点\(A_{k},A_{n+1},A_{n+2}\)を選び、対角線を引いて3角形\(A_{k}A_{n+1}A_{n+2}\)を作る。
そうすると、\(A_{0},A_{1},\cdots,A_{k-1}\)の凸\(k\)角形と\(A_{k+1},A_{k+2},\cdots,A_{n}\)の凸\(n-k\)角形ができるので、このとき、この2つの凸多角形で\(C_{k}C_{n-k}\)通りの分割ができる。
これを\(k\)について0から\(n\)まで総和をとれば、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となり凸3角形\(\text{で\text{は}}1=C_{1}=C_{0}^{2}\)なので\(C_{0}=1\)とする。
従って\(C_{n}\)はカタラン数となり題意は成り立つ。

(5)

\(n+1\)個の分岐を持つとき1番最初の分岐の左側に\(k\)個の分岐、右側に\(n-k\)個の分岐があるとすると、このとき、\(C_{k}C_{n-k}\)通りある。
これを\(k\)について0から\(n\)まで総和をとればいいので、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また\(1=C_{1}=C_{0}^{2}\)となるので\(C_{0}=1\)とすればいい。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。

(6)

\(2n+2\)個の点を\(a_{0},a_{1},\cdots,a_{2n+1}\)として\(a_{0}\)とペアになる点を\(a_{2k+1}\)とする。
このとき、\(a_{1},a_{2},\cdots,a_{2k}\)と\(a_{2k+1},a_{2k+2},\cdots,a_{2n+1}\)の2個に分割され、\(a_{1},a_{2},\cdots,a_{2k}\)で\(C_{k}\)通り、\(a_{2k+2},a_{2k+2},\cdots,a_{2n+1}\)で\(C_{n-k}\)通りとなるので合わせて\(C_{k}C_{n-k}\)通りとなる。
これを\(k\)について0から\(n\)まで総和をとればいいので、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また\(1=C_{1}=C_{0}^{2}\)となるので\(C_{0}=1\)とすればいい。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。