조합 항등식 증명

자연수 $n$에 대하여 등식 ${}_{n} C _{n} + _{n+1} C _{n} + _{n+2} C _{n} = _{n+3} C _{n+1}$ 이 성립함을 다음과 같이 증명하였다.

<증명> ${}_{n+3} C _{n+1}$은 집합 $A = \{ 1 , 2 , \cdots , n + 3 \}$의 부분집합 중에서 원소의 개수가 $n + 1$인 부분집합의 개수이다. 이것을 다른 방법으로 세어보자. (ⅰ) 집합 $A$의 부분집합 중에서, 가장 큰 원소가 $\square {( \text{가} )}$ 이고 원소의 개수가 $n + 1$인 부분집합의 개수는 ${}_{n} C _{n}$이다. (ⅱ) 집합 $A$의 부분집합 중에서, 가장 큰 원소가 $\square {( \text{나} )}$ 이고 원소의 개수가 $n + 1$인 부분집합의 개수는 ${}_{n+1} C _{n}$이다. (ⅲ) 집합 $A$의 부분집합 중에서, 가장 큰 원소가 $\square {( \text{다} )}$ 이고 원소의 개수가 $n + 1$인 부분집합의 개수는 ${}_{n+2} C _{n}$이다. (ⅰ), (ⅱ), (ⅲ) 중에서 한 가지 경우만 일어날 수 있으므로 합의 법칙에 의하여 ${}_{n} C _{n} + _{n+1} C _{n} + _{n+2} C _{n} = _{n+3} C _{n+1}$이 성립한다.

위의 증명에서 (가), (나), (다)에 알맞은 것을 차례로 나열한 것은? [4점] (가) (나) (다) ①$n - 1$ $n$ $n + 1$②$n$ $n + 1$ $n + 2$③$n + 1$ $n + 2$ $n + 3$④$n + 2$ $n + 1$ $n$⑤$n + 3$ $n + 2$ $n + 1$