계단 오르기 방법의 수

<풀이1> $n$칸의 계단을 오르는 방법의 수를 수열 $\left\{ a _{n} \right\}$이라 하면 $a _{1} = 1 , a _{2} = 2 , a _{n + 2} = a _{n + 1} + a _{n}$ ∴$a _{9} = 55$ <풀이2> 두 계단을 오르는 횟수가 0번일 때 ${} _{9} C _{0}$가지 1번일 때 ${} _{8} C _{1}$가지 2번일 때 ${} _{7} C _{2}$가지 3번일 때 ${} _{6} C _{3}$가지 4번일 때 ${} _{5} C _{4}$가지 따라서 구하는 방법의 수는 ${} _{9} C _{0} + _{8} C _{1} + _{7} C _{2} + _{6} C _{3} + _{5} C _{4} = 55$