학습자료실

수업자료 및 학습에 필요한 강의자료실입니다.

제목

피보나치수열!!!2024-02-27 22:20

작성자

ssolpass

1. 개요[편집]

Fibonacci sequence. 수학에서 다루는 수열이다. 다음과 같은 점화식으로 피보나치 수열을 정의할 수 있다.

�_{0} = 0, �_{1} = 1, �_{� + 2} = �_{� + 1} + �_{�}

일반항으로 표현하자면 다음과 같다.

\begin{aligned} �_{�} & = \frac{1}{\sqrt{5}} [{(\frac{1 + \sqrt{5}}{2})}^{�} - {(\frac{1 - \sqrt{5}}{2})}^{�}] \\ = \frac{{(1 + \sqrt{5})}^{�} - {(1 - \sqrt{5})}^{�}}{2^{�} \sqrt{5}} \\ = \frac{1}{2^{� - 1}} \sum_{� = 0}^{⌊ (� + 1) / 2 ⌋} (\binom{�}{2 � + 1}) 5^{�} \end{aligned}

(

⌊ (� + 1) / 2 ⌋

는

(� + 1) / 2

이하의 최대정수,

(\binom{�}{2 � - 1})

은 조합)
아주 계산이 복잡하다. 다항방정식 형태로 바꿔서 풀면 쉽다.

제0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 1번째 수를 1로, 2번째 수도 1로 놓고, 3번째 수부터는 바로 앞의 두 수를 더한 수로 정의하는 게 좀더 흔하게 알려져 있는 피보나치 수열이다. 이 둘은 시작점이 다르다는 정도를 빼면 사실상 동일하다.

그 중에서 16 번째 항까지만 나열해 보자면 (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
이렇게 간다.

피보나치 수열의 이웃한 두 항이 항상 서로소라는 것은 수학적 귀납법으로 쉽게 증명할 수 있다. 피보나치 소수[1]가 무한히 존재하는지는 유명한 미해결 문제다.[2]

2. 유래[편집]

피사의 레오나르도로 널리 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 인도의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 무리들도 있긴 하나 공식적인 연관성은 불명. 어쨌든 서유럽에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치수열이란 이름은 19세기가 되어서야 붙여졌다.

실제 피보나치수열의 점화식은 인도도 그렇고 유럽도 그렇고 일찌감치 알려져 있었으나 피보나치 수의 생성함수는 완전히 정리되기까지 다소 시간이 필요했다. 1765년 오일러가 최초로 이 생성함수를 정리하여 발표했으나 당시에는 별로 주목을 받지 못해서 그대로 묻혔다. 이후 1848년 비네가 이 생성함수를 재발견하여 발표했고 결국 피보나치 수의 생성함수는 비네의 식이라 이름이 붙었다. 물론 오일러는 다른 방면에서도 어마어마하게 유명하므로 아쉬울 일은 없을 것이다.

수학의 수열 파트에서 잠시 배우는 수준이지만 컴퓨터 계열로 진학할 경우 정말 질리도록 보게 된다. 프로그래밍 언어에서 재귀함수를 배우면서 과제로 반드시 한 번은 하게 된다. 재귀함수로 간단히 구현되지만, 메모이제이션(Memoization) 없이 구현할 경우 실행시간이 안드로메다로 증가하게 된다. 반대로 메모이제이션을 할 경우에는 필요한 메모리가 O(n) 에 비례해지는 단점이 있다. 단순히 직전과 그 전의 값만 저장하는 방식으로 반복문이나 꼬리재귀 최적화가 된 재귀를 할 경우 시간복잡도 O(n)에 공간복잡도 O(1)도 가능하다. 다만, 정말 큰 임의의 n에 대한 피보나치 수를 구해야한다면, 행렬을 이용하여 시간복잡도 O(log n)에 공간복잡도 O(1)로 구현할 수도 있다. 좀더 높은 레벨의 프로그래밍에서는 피보나치 힙(Fibonacci Heap) 같이 자료구조나 알고리즘 최적화에 피보나치 수열의 성질을 우려먹는 경우를 많이 보게 될 것이다.

자연에서 꽃씨의 배열이나 나무가지의 갈라짐 등등으로 빈번하게 등장하고, 피보나치의 문제처럼 실제 생물의 번식을 설명하는 데에도 쓰인다. 이는 황금비의 자기닮음성이나 프랙탈과도 엮인다.[3] 비슷한 맥락으로 주식시장의 변동을 설명하는 엘리어트 파동 이론(Elliott wave theory)에서 출현하기도 한다. 여러 모로 신기한 수열이다.

베리에이션으로 뤼카 수열(Lucas Sequence)이 있다. 초항과 그 다음 항을 0과 1이 아닌 숫자 두 개를 설정하고

�_{� + 2} = �_{�} + �_{� + 1}

대로 따라가면 뤼카 수열이다.

수학 귀신에도 꽤나 나온다. 번식하는 토끼의 수를 나타내거나 아래에 나오는 두 항의 비율이 황금비에 근접하는 사실 등.

3. 일반항의 유도[편집]

피보나치수열의 항의 비율

\frac{�_{�}}{�_{� - 1}}

의 극한값은 소위 황금비가 된다.

위에서 언급한 비네의 식에서 피보나치수열의 일반항을 황금비로 표시할 수 있는데, 황금비를

�

라고 하고

�^{'} = 1 - �

라고 하면 피보나치수열의 일반항은 다음과 같다.

�_{�} = \frac{(�^{�} - �^{'}^{�})}{(� - �^{'})}

� = \frac{1 + \sqrt{5}}{2}

인 무리수인 반면 피보나치수열의 모든 항은 자연수인 걸 감안하면 굉장히 신기한 수열인데, 증명 방법은 대략 다음과 같다.

황금비

�

는 정의에 따라

�^{2} - � - 1 = 0

의 0보다 큰 근이고, 0보다 작은 근은

�^{'}

라고 하자. 그러면 근과 계수와의 관계에서

� + �^{'} = 1, � �^{'} = - 1

이다.

이를 이용해

�_{�} = �_{� - 1} + �_{� - 2}

를 변형하여

(�_{�} - � �_{� - 1}) = �^{'} (�_{� - 1} - � �_{� - 2})

과

(�_{�} - �^{'} �_{� - 1}) = � (�_{� - 1} - �^{'} �_{� - 2})

를 얻는다. 각각에서

�_{� - 1} - � �_{� - 2}

과

�_{� - 1} - �^{'} �_{� - 2}

가 등비수열이고

� = 3

일때 각각

1 - � = �^{'}

와

1 - �^{'} = �

이다. 이를 이용해 일반항을 구하면

� \geq 3

일 때

�_{� - 1} - � �_{� - 2} = {�^{'}}^{� - 2}

이고,

�_{� - 1} - �^{'} �_{� - 2} = �^{� - 2}

. 양변을 빼서 정리하면

� \geq 3

일 때

�_{� - 2} = \frac{�^{� - 2} - {�^{'}}^{� - 2}}{� - �^{'}}

이므로

� \geq 1

일 때로 정리하면 위의 식이 나온다.

일반적으로

� �_{� - 2} + � �_{� - 1} + � �_{�} = 0

의 꼴의 점화식이 주어진다면

� �^{2} + � � + � = 0

의 두 근을

�, �

라고 했을 때,

� �^{�} + � �^{�}

의 형태로 일반항이 나오게 된다.

�, �

은 이제 초항 2개를 연립해서 계수를 맞춰넣어서 계산하는데, 초항과 둘째항이 다른 루카스 수열 역시 점화식이 동일하기 때문에 일반항은 계수

�, �

만 다른 형태로 나오게 되며, 항의 비의 극한값은 여전히 황금비가 나온다.

4. 성질[편집]

$�_{�}$ 과 $�_{� + 1}$ 은 서로소이다.
[증명]

$�_{�}$ $�_{� + 1}$

$� = 1$ $(�_{1}, �_{2})$
$� = �$ $(�_{�}, �_{� + 1})$
$� = � + 1$ $(�_{� + 1}, �_{� + 2})$ $(�_{� + 1}, �_{� + 1} + �_{�})$
$(�_{� + 1}, �_{� + 1} + �_{�})$ $(�_{� + 1}, �_{�})$

피보나치 수열의 합: $\sum_{� = 1}^{�} �_{�} = �_{� + 2} - 1$
[증명]
$�_{� + 2} = �_{� + 1} + �_{�}$ $�_{� + 2} - �_{� + 1} = �_{�}$
$\sum_{� = 1}^{�} �_{�} = \sum_{� = 1}^{�} (�_{� + 2} - �_{� + 1})$
$= (�_{3} - �_{2}) + (�_{4} - �_{3}) + . . . + (�_{� + 1} - �_{�}) + (�_{� + 2} - �_{� + 1})$
$= �_{� + 2} - �_{2} = �_{� + 2} - 1$

피보나치 수열 제곱의 합: $\sum_{� = 1}^{�} �_{�}^{2} = �_{�} �_{� + 1}$
[증명]
$�_{� + 2} = �_{� + 1} + �_{�}$ $�$ $� - 1$ $�_{� + 1} = �_{�} + �_{� - 1}$ $�_{�} = �_{� + 1} - �_{� - 1}$
$\sum_{� = 1}^{�} �_{�}^{2} = �_{1}^{2} + \sum_{� = 2}^{�} �_{�} �_{�} = �_{1}^{2} + \sum_{� = 2}^{�} �_{�} (�_{� + 1} - �_{� - 1}) = �_{1}^{2} + \sum_{� = 2}^{�} (�_{�} �_{� + 1} - �_{�} �_{� - 1})$
$= �_{1}^{2} + (�_{3} �_{2} - �_{2} �_{1}) + (�_{4} �_{3} - �_{3} �_{2}) + . . . + (�_{� + 1} �_{�} - �_{�} �_{� - 1})$
$= �_{� + 1} �_{�} + �_{1}^{2} - �_{2} �_{1} = �_{�} �_{� + 1} + 1 - 1 = �_{�} �_{� + 1}$

피보나치 수열 분수의 합: $\sum_{� = 1}^{�} \frac{�_{�}}{�_{� + 1} �_{� + 2}} = \frac{1}{�_{2}} - \frac{1}{�_{� + 2}}$
[증명]
$\sum_{� = 1}^{�} \frac{�_{�}}{�_{� + 1} �_{� + 2}} = \sum_{� = 1}^{�} \frac{�_{�}}{�_{� + 2} - �_{� + 1}} (\frac{1}{�_{� + 1}} - \frac{1}{�_{� + 2}}) = \sum_{� = 1}^{�} \frac{�_{� + 2} - �_{� + 1}}{�_{� + 2} - �_{� + 1}} (\frac{1}{�_{� + 1}} - \frac{1}{�_{� + 2}})$
$= \sum_{� = 1}^{�} (\frac{1}{�_{� + 1}} - \frac{1}{�_{� + 2}}) = (\frac{1}{�_{2}} - \frac{1}{�_{3}}) + (\frac{1}{�_{3}} - \frac{1}{�_{4}}) + . . . + (\frac{1}{�_{� + 1}} - \frac{1}{�_{� + 2}})$
$= \frac{1}{�_{2}} - \frac{1}{�_{� + 2}}$

다항식 $�^{�}$ 을 $�^{2} - � - 1$ 로 나눈 나머지를 $�_{�} � + �_{�}$ 이라 하면, 수열 ${�_{�}}$ 은 피보나치 수열이다.
[증명]
$�^{�}$ $�^{2} - � - 1$ $� (�)$

$�^{�} = (�^{2} - � - 1) � (�) + �_{�} � + �_{�} \dots ①$

$�^{2} - � - 1 = 0$ $�$ $�$

$�^{2} - � = �^{2} - � = 1 \dots ②$

$� + � = 1, � � = - 1 \dots ③$

$� = �$ $� = �$

$\begin{aligned} �^{�} & = �_{�} � + �_{�} \\ �^{�} & = �_{�} � + �_{�} \\ �^{�} - �^{�} & = �_{�} (� - �) \\ ∴ �_{�} & = \frac{�^{�} - �^{�}}{� - �} \end{aligned}$

$\begin{aligned} �_{1} & = \frac{� - �}{� - �} = 1 \\ �_{2} & = \frac{�^{2} - �^{2}}{� - �} = � + � = 1 \end{aligned}$

$\begin{aligned} �_{�} + �_{� + 1} & = \frac{�^{�} - �^{�}}{� - �} + \frac{�^{� + 1} - �^{� + 1}}{� - �} \\ = \frac{�^{�} (1 + �) - �^{�} (1 + �)}{� - �} \\ = \frac{�^{� + 2} - �^{� + 2}}{� - �} = �_{� + 2} \end{aligned}$

$�_{1} = �_{2} = 1$ $�_{� + 2} = �_{�} + �_{� + 1}$

5. 음의 피보나치 수열[편집]

$�_{0} = 0$
$�_{1} = 1$
$�_{�} = �_{� - 1} + �_{� - 2}$

이 식에서 n의 범위를 정수로 확장하면

�_{- 1}

를 비롯해서 음의 피보나치 수를 구할 수 있다.

$�_{0} = 0$
$�_{- 1} = 1$
$�_{- 2} = - 1$
$�_{- 3} = 2$
$�_{- 4} = - 3$

피보나치 수열에서 2번에 1번씩 번갈아 부호가 음수가 되는 수열이 만들어진다.

(0), 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, 89, -144, 233, -377, 610, -987

즉, 적당한

�, (� > 0)

에 대해서

�_{- �}

는 다음을 만족시킨다.

$�_{- �} = {(- 1)}^{� + 1} �_{�}$

6. 유리수에서[편집]

\frac{1}{1000000 - 1000 - 1} = \frac{1}{998999}

을 소수로 나타내면

0.000 001001002003005008013021034055089144233 377...

로 각 세자리 마다 피보나치 수가 나타난다.

이를 일반화하여 n자리마다 피보나치 수가 나타나는 유리수를 만들 수가 있다.[4]

\frac{1}{1 0^{2 �} - 1 0^{�} - 1} = \sum_{� = 0}^{\infty} \frac{�_{�}}{1 0^{� (� - 1)}}

증명

7. 활용[편집]

7.1. 경우의 수[편집]

피보나치 수는 계단을 오르는 경우의 수로 생각할 수 있다. 계단을 오를 때 한 번에 한 계단 또는 두 계단을 오를 수 있다면, 계단

�

개를 오르는 경우의 수는

�_{� + 1}

이다. 이를 증명하여 보자.

먼저, 계단 1개를 오르는 경우의 수는 당연히 1이고, 계단 2개를 오르는 경우의 수는 한 계단씩 두 번 오르는 경우와 두 계단을 한 번 오르는 경우 이렇게 두 가지이다.

위 그림과 같이, 계단

�

개를 오르는 경우의 수는 마지막에 한 계단을 오르는 경우와 마지막에 두 계단을 오르는 경우로 나누어 구할 수 있다.[5] 전자는 마지막의 한 계단을 제외한 계단

(� - 1)

개를 오르는 경우의 수가 되고, 후자는 마지막의 두 계단을 제외한 계단

(� - 2)

개를 오르는 경우의 수가 된다.

원래 피보나치 수열은

1, 1, 2, 3, 5 \dots

인데, 계단을 오르는 경우의 수는 처음 두 항이 1, 2인 피보나치 수열이 되므로 계단

�

개를 오르는 경우의 수는

�_{� + 1}

이 된다.

#1234

이전	페르마의 마지막 정리	ssolpass	2024-03-04
-	피보나치수열!!!	ssolpass	2024-02-27
다음	2024년도 대학수학능력시험	ssolpass	2023-12-23