[확률과 통계] 계단을 오르는 경우의 수와 피보나치 수열

고등학교 제출용 보고서의 일부임.

[논제] 어떤 사람이 한 걸음에 한 계단 또는 두 계단씩 올라 총 $n$개의 계단을 오르는 경우의 수를 $a_n$이라 하자. 이때, 수열 $a_n$이 아래 명제를 만족시킴을 증명하라. (단, $n$∈$N$)

$a_1 =1$, $a_2 = 2$ 이고, $a_{n+2} = a_{n+1} + a_n$ 이다.

[전제] 한 걸음에 한 계단을 오르는 것을 기호 ‘$1$’, 한 걸음에 두 계단을 오르는 것을 기호 ‘$2$’라고 하자. 편의상 ‘걸음’을 앞으로 ‘시행’이라고 표현한다. 그리고 경우의 표기는 시행의 순서쌍으로 한다. 예를 들어, $5$개의 계단을 오르는 경우 중 $(1, 2, 2)$는 총 세 시행이 있었고 첫 시행은 $1$, 두 번째와 세 번째 시행은 $2$였다는 것을 의미한다.

$n=1$인 경우, 고를 수 있는 경우는 $(1)$ 하나 뿐이므로 $a_1 =1$이다.
$n=2$인 경우, 고를 수 있는 경우는 $(1, 1)$과 $(2)$의 두 개 뿐이므로 $a_2 = 2$이다.

이제 $n≥3$인 경우를 생각해보자. $n≥3$인 경우, 한 시행으로 계단을 모두 오를 수 없다. 다시 말해, 두 번 이상의 시행을 하여 계단을 올라야 한다.

예를 들어, $n=3$의 경우에는 한 시행에 세 계단을 오를 수 없다. 마지막 시행에서 한 계단을 오르는 경우를 (i), 두 계단을 오르는 경우를 (ii)라 하자.
(i) 마지막 시행에서 $1$개의 계단을 올라야 하므로, 이에 앞서 $2$개의 계단을 올라야 한다. $2$개의 계단을 오르는 경우의 수는 $a_2$이다.
(ii) 마지막 시행에서 $2$개의 계단을 올라야 하므로, 이에 앞서 $1$개의 계단을 올라야 한다. $1$개의 계단을 오르는 경우의 수는 $a_2$이다.
이상에 따라, $a_3$은 $3$이고, 동시에 $a_1+a_2$의 결과와 같다.

<일반화>

$n=k+2$($k≥1$인 정수)인 경우 ($a_{k+2}$)
가정에 따라, $(k+2)$개의 계단은 한 시행으로 모두 오를 수 없다. $(k+2)$개의 계단을 오를 때, 마지막 시행으로 한 계단을 오르는 경우를 (a), 두 계단을 오르는 경우를 (b)라 하자.
(a) 마지막 시행에서 $1$개의 계단을 올라야 하므로, 이에 앞서$(k+1)$개의 계단을 올라야한다. $(k+1)$개의 계단을 오르는 경우의 수는 $a_{k+1}$이다.
(b) 마지막 시행에서 $2$개의 계단을 올라야 하므로, 이에 앞서 $k$개의 계단을 올라야 한다. $k$개의 계단을 오르는 경우의 수는 $a_{k}$이다.

이상에 따라, $a_{n+2} = a_{n+1} + a_n$ 이다.

그러므로, 1 이상의 자연수에 대하여 논제의 명제는 참이다.