피보나치 수열 점화식 유도하기

1202년 레오나르도 피보나치가 토끼의 번식을 언급하며 이 수열을 연구했다고 한다.

토끼의 번식에 다음과 같은 규칙이 있다고 하자.

 

처음에 토끼 한 쌍이 있는데 한 쌍의 토끼는 매달 한 쌍의 토끼를 낳는다고 하자.
단, 갓 태어난 토끼는 그 달에는 번식을 못하고 한 달이 지나야 번식을 할 수 있다.

 

이 규칙에 따르면 다음 그림처럼 번식하게 된다.

출처 : https://www.mathscareers.org.uk/the-mathematics-of-rabbit-island/

이제 최초 토끼 쌍이 출현한 이래로 $n$ 개월 후의 토끼는 총 몇 쌍인지 구하고자 한다.

$n$ 개월 지났을 때 총 토끼 쌍을 $f_{n}$ 이라 하자.

 

현재의 토끼는 이번 달 새로 태어난 토끼 + 지난달까지 존재하던 토끼이다.

즉 $n$ 월일 때 새로 태어난 토끼쌍의 수를 $N_{n}$ 이라 하고

$n$ 월일 때 성숙이 완료되어 있는 토끼쌍의 수를 $M_{n}$ 이라 하면

(1) $\textcolor{blue}{f_{n} = N_{n} + M_{n}}$ 가 성립한다.

 

한편 $n$ 월에 새로 태어난 토끼는 $n-1$월까지 성숙이 완료된 토끼가 동일한 수 만큼 낳은 것이다.

따라서 $n$ 월일 때 성숙이 완료되어 있는 토끼쌍의 수를 $M_{n}$ 이라 하면

$\textcolor{orange}{N_{n} = M_{n-1}}$ 가 성립한다.

 

또 $n$ 월에 성숙이 완료된 토끼는

$n-1$ 월까지 성숙이 완료되어 있는 토끼 + $n-1$월 갓 태어나서 이번달 성숙이 완료되는 토끼이므로

$M_{n} = M_{n-1} + N_{n-1}$ 가 성립한다.

이 것을 식 (1)과 결합하면 $\textcolor{orange}{M_{n} = f_{n-1}}$ 을 얻는다.

 

따라서 식 (1)에 대입하면 다음을 얻는다.

$$ \begin{align} f_{n} = &M_{n-1} + f_{n-1} \\ = &f_{n-2} + f_{n-1} \end{align}$$

$n$ 대신에 $n+2$를 대입하여 원하는 꼴을 얻어낸다.

$$\textcolor{red}{f_{n+2} = f_{n+1} + f_{n}} \quad (n \geq 1)$$