피보나치 수열과 토끼 문제 (왜 피보나치 수열이 성립할까?)

 

 

피보나치 수열과 토끼 문제는 피보나치가 1202년에 출간한 책 Liber Abaci 에 나오는 문제입니다. Liber Abaci (리베르 아바치)는 라틴어구요. 영어로는 The book of calculation 입니다. 우리말로는 "계산의 책"입니다. 

피보나치는 1170년생이고, 피사공화국 사람입니다. 

피보나치 수열과 토끼 문제는 '피보나치의 토끼' 라고 불립니다. 문제는 아래와 같습니다. 이해가 쉽도록 각색하였습니다. 

1. 1월1일에 토끼 한쌍이 태어남.
2. 태어난 토끼 한쌍은 두달 뒤부터 매달 한쌍의 토끼를 낳음. 
4. 새로 태어난 토끼쌍들도 2번의 규칙을 따름
3. 토끼는 죽지않음.

1년 뒤 몇쌍의 토끼가 있을까요? 

---

첫 토끼쌍을 $R_{1}$ 이라고 놓겠습니다. 

 

두달이 지나야 새끼를 낳으므로, 다음달에도 토끼 쌍의 수는 그대로입니다.

한달이 지나면 R_{1}이 새끼를 한쌍 낳습니다. 

 

한달이 지나면 $R_{1}$이 새끼를 한쌍 낳습니다. 

 

한달이 지나면 $R_{1}$ 이 새끼 한쌍을 낳고, $R_{11}$ 도 새끼 한쌍을 낳습니다. 

 

한달이 지나면 $R_{1}$ , $R_{11}$, $R_{12}$ 가 새끼 한쌍을 낳습니다.

 

 

지금까지의 결과를 종합해봅시다. 

 

1월 : 1쌍

2월 : 1쌍

3월 : 2쌍

4월 : 3쌍

5월 : 5쌍

6월 : 8쌍

 

1 1 2 3 5 8 은 피보나치 수열입니다. 직접 더 해보지 않아도, 이후에도 계속 성립한다고 할 수 있을까요? 

 

$F_{n}$ 월의 토끼쌍의 수는 $F_{n-1}$ 월의 토끼쌍의 수에, 새로 태어난 토끼쌍의 수를 더한 값입니다. 두달이 지나야 새끼를 낳을 수 있기 때문에 $F_{n}$월에 새끼를 낳을 수 있는 토끼쌍은 두달 전에도 존재한 토끼쌍들입니다. 두달 전에 존재한 토끼쌍의 수가  $F_{n}$ 추가되는 토끼 쌍의 수와 같습니다. 따라서 아래 등식이 성립합니다. 

 

$F_{n}=F_{n-1}+F_{n-2}$

 

피보나치 수열이 성립한다는 것을 알 수 있습니다.