피보나치(Fibonacci)수열의 일반항 구하기

수열 가운데 가장 유명한 수열은 피보나치수열이지 않을까? 앞에 있는 두 개의 항을 더해서 다음 항을 만드는 수열이다.

$$0,1,1,2,3,5,8,13,21,\cdots$$

인도 수학자 핀가라(Pingala: BC 300~200?)가 처음 기술하였는데 훗날 피보나치(Fibonacci: 1170~1240)가 1202년 산술을 소개하는 책 Liber Abaci에 소개하면서 유럽에 알려졌기 때문에  피보나치수열로 부르게 되었다. 수학에서 보통 $F_n$으로 표기하는데 첫째 항을 0으로 잡지만 문제에 따라 1로 잡기도 한다. 피보나치수열은 여러 가지 모양으로 표현된다.

피보나치 수열을 소개하는 방법

계단 오르는 방법의 수

문제 계단을 오를 때 한 걸음에 한 칸 또는 두 칸을 오를 수 있다. 칸의 개수가 20인 계단을 오르는 방법의 수를 구해보자.

풀이

칸의 개수가 $n$일 때 오르는 방법의 수를 $a_{n}$이라고 하자.

1칸이면 당연히 한 가지 방법,

2칸인 계단은 $1+1=2$이므로 두 가지 방법,

3칸인 계단은 $1+1+1=1+2=2+1$이므로 세 가지 방법이다.

$a_{1}=1,\;\;a_{2}=2,\;\;a_{3}=3$임을 알 수 있다.

수열 $\{a_{n} \}$을 귀납적으로 정의해 보자.

$n$칸의 계단을 오르는 방법의 수는 처음에 $1$ 칸을 오르는 경우와 $2$ 칸을 오르는 경우로 나누어 볼 수 있다.

$1$ 칸을 오르는 경우는 $a_{n-1}$,   $2$칸을 오르는 경우는 $a_{n-2}$이다.

그러므로 $a_n =a_{n-1} + a_{n-2}$

따라서 $a_{n+2}=a_{n} + a_{n+1}$이다.

$$1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, \cdots$$

계단이 20일 때는 방법의 수가 무려 10946이다. 생각보다 아주 빠르게 증가한다.

타일을 덮는 방법의 수

문제 그림과 같이 $1\times 10$의 직사각형 판을 $1\times 1$ 또는 $1\times 2$ 판으로 덮는 방법은 모두 몇 가지인가?

풀이

일반화를 위해 $1\times n$인 판을 생각하자. 이런 문제는 작은 자연수부터 차근차근 생각하면 된다. $n=1$일 때와 $n=2$일 때는 아래와 같다.

$n=4$일 때는 아래와 같다.

이 그림을 숫자로 표현해 보자.

$$(1,1,1,1),\;\;(1,1,2),\;\;(1,2,1),\;\;(2,1,1),\;\;(2,2)$$

따라서 $a_4 =5$이다.

구하고자 하는 방법의 수를 $a_n$으로 두고 점화식을 찾아보자.

$a_4$를 맨 앞에 $1$이 오는 경우와 $2$가 오는 경우로 나누어 생각하면 $a_4 =a_3 +a_2$임을 알 수 있다.

귀납적으로 생각하면 $a_{n+2}=a_{n+1}+a_n$임을 찾아 피보나치수열임을 알 수 있다.

위에서 찾아 정답은 $a_{10}=89$이다.

번식하는 토끼의 수

가장 널리 알려진 문제는 토끼 문제이다.

토끼 암컷과 수컷 한 쌍이 있다. 태어나 한 달 동안은 자라서 어른이 되고 다시 한 달이 지날 때마다 꼬박꼬박 한 쌍의 남매 토끼를 낳는다. 죽는 토끼가 없다면 12달 후 몇 쌍의 토끼가 있을까?

이제 일반항을 구해보자.

$$\begin{align}a_1 =1, \;\;a_2 =1 \\ a_{n+2} =a_{n+1} +a_n \end{align}$$

와 같이 귀납적으로 정의된다.

일반항 구하기

일반항을 구하기 위하여 점화식을

$a_{n+2} -\alpha a_{n+1} =\beta(a_{n+1} -\alpha a_n )$ 의 모양으로 바꾼다.

$$\begin{align}a_{n+2} -\alpha a_{n+1} &=\beta(a_{n+1} -\alpha a_n )\\&=\beta^2 (a_n -\alpha a_{n-1} )\\&\vdots\\&=\beta^n (a_2 -\alpha a_1 )\\&=\beta^{n+1}\end{align}$$

$$\therefore a_n -\alpha a_{n-1} =\beta^{n-1}\tag{1}$$

$\alpha, \;\;\beta$를 바꾸어 생각해도 마찬가지이다.

$$\therefore a_n -\beta a_{n-1} =\alpha^{n-1}\tag{2}$$

(1), (2)를 연립하여 풀면 $(1)\times \beta -(2)\times \alpha$

$$a_n = \frac{1}{\beta-\alpha} (\beta^n -\alpha^n )$$ 이다.

한편, $\alpha +\beta=1,\;\; \alpha \beta=-1$이므로

$\alpha, \beta$는 2차방정식 $x^2 -x-1=0$의 두 근이다.

$$\beta = \frac{1+\sqrt{5}}{2} , \;\; \alpha = \frac{1-\sqrt{5}}{2}$$라고 한다면

따라서 피보나치수열의 일반항은

$$a_n = \frac{1}{\sqrt5} \Bigg(\bigg( \frac{1+\sqrt5}{2} \bigg)^n -\bigg( \frac{1-\sqrt5}{2} \bigg)^n \Bigg)$$

이다.

Fibonacci.pdf

다운로드

덧붙임

신기하게도 피보나치수열 $F_{n}$의 이웃한 항이 이루는 비율은 황금비($\varphi$)로 수렴한다. 이와 관련된 이야기도 아주 재밌다.

$$\displaystyle{lim_{n \rightarrow \infty} {\frac{F_{n}}{F_{n+1}}}=\varphi}$$

https://suhak.tistory.com/1336

황금비로 나누기

https://phys.org/news/2007-05-scientists-clues-formation-fibonacci-spirals.html

Scientists find clues to the formation of Fibonacci spirals in nature