피보나치 수열 심화과정1 - n번째 피보나치 수를 바로 계산할 수 있을까? (피보나치 수열의 일반항과 황금비)-

1. 피보나치 수열

 

$F_{1} = F_{2} = 1$이고 3이상의 자연수 n에 대하여,

 

$F_{n} = F_{n-1} + F_{n-2}$를 만족하는 수열 $F_{n}$을 피보나치 수열이라고 부른다.

 

 

2. 피보나치 수열을 만드는 방법

 

어떤 자연수 n이 주어졌을때, $F_{n}$을 O(1)에 바로 계산할 수 있는가?

 

1,1,2,3,5,...로 더해나가 n번째 피보나치 수열의 항을 구하는 것이 아니라

 

n만 알면 n번째 피보나치 수를 바로 구할 수 있는지?

 

 

3. 선형점화식의 특성방정식(characteristic equation)

 

선형점화식 $$f(n) = a_{n+k} + c_{1}a_{n+k-1} + c_{2}a_{n+k-2} + ... + c_{k}a_{n}$$에 대하여, 

 

모든 i = 0, 1, 2, ..., k에 대해 $a_{n+k-i} = x^{k-i}$라고 정의하자. 

 

그러면 선형점화식은 x에 대한 방정식 $$x^{k} + c_{1}x^{k-1} + c_{2}x^{k-2} + ... + c_{k} = 0$$으로 바뀐다.

 

이를 선형점화식 f(n)의 특성방정식이라고 부른다.

 

특성방정식의 가장 중요한 성질은 일반항과 관련되어 있는데, 이 방정식의 근이 $\alpha_{1}, \alpha_{2}, ... , \alpha_{k}$라고 하면, 

 

수열의 일반항 $a_{n}$은 $\alpha_{1}^{n}, \alpha_{2}^{n}, ... , \alpha_{k}^{n}$의 선형결합이다.

 

즉 적절한 상수 $A_{1}, A_{2}, ... ,A_{k}$에 대하여 가능한 모든 일반항은..

 

$$a_{n} = A_{1}\alpha_{1}^{n} + A_{2}\alpha_{2}^{n} + ... + A_{k}\alpha_{k}^{n}$$

 

여기서 특성방정식의 근이 모두 달라야한다. 중근을 갖는다면 성립하지 않는다고 한다

 

적절한 상수 $A_{i}$는 초기조건 $a_{1}, a_{2}, ..$에 따라 정해진다.

 

https://namu.wiki/w/%EC%A0%90%ED%99%94%EC%8B%9D

점화식 - 나무위키

 

https://milkclouds.work/%EB%AF%B8%EB%B6%84%EB%B0%A9%EC%A0%95%EC%8B%9D%EA%B3%BC-%EC%A0%90%ED%99%94%EC%8B%9D%EC%9D%98-%ED%8A%B9%EC%84%B1%EB%B0%A9%EC%A0%95%EC%8B%9D%EC%97%90-%EB%8C%80%ED%95%B4/

수학 조각글 - 미분방정식과 점화식의 특성방정식에 대해

 

왜 맞는지, 직관적으로 설명해주신분이 있어서 첨부해본다

 

선형점화식이라 가능한가보다.

 

특성방정식의 어떠한 해 $\alpha_{1}^{n}, \alpha_{2}^{n}$이 특성방정식을 만족시킨다면,

 

선형결합 $a\alpha_{1}^{n} + b\alpha_{2}^{n}$도 그 방정식을 만족시킨다.

 

따라서 점화식을 구성하는 해공간의 두 원소의 선형결합으로 점화식의 무수히 많은 해공간을 반드시 구성할 수 있다.

 

이렇게 무한히 많은 해 중에서 초기조건 $F_{1} = F_{2} = 1$을 만족하는 해를 찾는 것이 사람이 찾고자 하는 특정한 일반항이다.

 

 

4. 피보나치 수열의 일반항

 

피보나치 수열의 점화식 $F_{n} = F_{n-1} + F_{n-2}$를 특성방정식으로 변형하면 $$x^{2} - x - 1 = 0$$이다.

 

이 방정식의 두 근을 $\alpha, \beta$라 하고 근의 공식을 이용해 구할 수 있다.

 

$$\alpha = \frac{1 + \sqrt{5}}{2}$$

 

$$\beta = \frac{1 - \sqrt{5}}{2}$$

 

따라서 피보나치 수열의 일반항은 $$F_{n} = A(\frac{1+\sqrt{5}}{2})^{n} + B(\frac{1-\sqrt{5}}{2})^{n}$$

 

초기조건 $F_{1} = F_{2} = 1$을 이용하면 두 상수 $A, B$를 구할 수 있다.

 

$1 = A(\frac{1+\sqrt{5}}{2}) + B(\frac{1-\sqrt{5}}{2})$

 

$1 = A(\frac{3+\sqrt{5}}{2}) + B(\frac{3-\sqrt{5}}{2})$

 

식을 변형하면,

 

$-6 = -3A -3A\sqrt{5} -3B +3B\sqrt{5}$

 

$2 = 3A + A\sqrt{5} + 3B - B\sqrt{5}$

 

그러면, 

 

$A + B = 0$이므로, $1 = A(\frac{1 + \sqrt{5}}{2}) + B(\frac{1 - \sqrt{5}}{2})$에 대입하면, 

 

$2 = 2A\sqrt{5}$이고, 그러므로 $$A = \frac{1}{\sqrt{5}}$$

 

$A+B = 0$이므로, $$B = \frac{-1}{\sqrt{5}}$$

 

따라서 $F_{1} = F_{2} = 1$인 피보나치 수열 $F_{n}$의 일반항은...

 

$$F_{n} = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n})$$

 

피보나치 수열의 모든 항이 자연수임에도 불구하고 일반항에 무리수가 들어간다는 점이 상당히 놀랍다.

 

특히 피보나치 수열의 일반항 $F_{n}$을 Binet의 공식이라고 부른다.

 

만약 자연수 n이 주어지면 일반항 $F_{n}$만으로 O(1)에 n번째 피보나치 수를 바로 구할 수 있다...

 

 

https://mathpeak.tistory.com/447

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

 

 

이론상 O(1)이긴 한데 사실 이 공식은 수학적으로 의미있지 프로그래밍적으로는 아무 의미없는게

 

floating point error때문에 n = 71부터 실제 값과 오차가 난다고 함

 

 

5. 황금비(golden ratio)

 

임의의 한 선분의 길이를 두 부분 A,B로 나누었을때, A > B라고 한다면, A+B: A = A : B가 되도록 분할할때,

 

$\frac{A}{B}$ 또는 $\frac{A+B}{A}$를 황금비라고 부른다(golden ratio)

 

비례식 A+B : A = A: B로부터 $A^{2} = AB + B^{2}$이 만들어지고, $\frac{A}{B} = \varphi$라고 하자.

 

그러면 방정식은 $(\varphi)^{2}  - \varphi - 1 = 0$

 

이 방정식의 근을 근의 공식을 이용해 구한다면, 비율은 양수이므로 $\varphi = \frac{1+\sqrt{5}}{2}$

 

이를 황금비라고 부르고 보통 $\varphi = 1.6180339887....$로 나타낸다.

 

참고로 인터넷 검색을 해보면 황금비는 수학적으로만 의미 있을뿐,

 

일반적으로 알려진 "미학적으로 아름답다" 등등은 모두 근거 없다고 함

 

https://namu.wiki/w/%ED%99%A9%EA%B8%88%EB%B9%84

황금비 - 나무위키

 

 

6. 피보나치 수열과 황금비

 

$\frac{1+\sqrt{5}}{2}$는 어디서 본것 같은 값인데, 피보나치 수열의 일반항에도 나오는 값이다.

 

피보나치 수열의 일반항 $F_{n}$에 대하여, 

 

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

 

인접한 두 항의 비가 n이 커질수록 황금비에 수렴한다

 

이건 좀 놀랍네

 

$1 - \varphi = \frac{1-\sqrt{5}}{2} = (\varphi)^{'}$라고 나타내면,  피보나치 수열의 일반항은..

 

$F_{n+1} = \frac{(\varphi)^{n+1} - ((\varphi)^{'})^{n+1}}{\sqrt{5}}$

 

$F_{n} = \frac{(\varphi)^{n} - ((\varphi)^{'})^{n}}{\sqrt{5}}$

 

두 식을 나누면, $$\frac{F_{n+1}}{F_{n}} = \frac{(\varphi)^{n+1} - ((\varphi)^{'})^{n+1}}{(\varphi)^{n} - ((\varphi)^{'})^{n}}$$

 

여기서, $-1 < (\varphi)^{'} < 1$이므로, $((\varphi)^{'})^{n}$의 n에 대한 극한값은 0이다.

 

https://j1w2k3.tistory.com/761

[미적분01 03탄] 등비수열의 극한

 

따라서, $\displaystyle \lim_{n \to \infty} \frac{F_{n+1}}{F_{n}}$의 값은...

 

$$\displaystyle \lim_{n \to \infty} \frac{F_{n+1}}{F_{n}} = \frac{(\varphi)^{n+1}}{(\varphi)^{n}} = \varphi$$

 

비슷한 방식으로 다음을 알 수 있다.

 

$$\displaystyle \lim_{n \to \infty} \frac{F_{n}}{F_{n-1}} = -(1-\varphi)$$

 

$$\displaystyle \lim_{n \to \infty} \frac{F_{n+m}}{F_{n}} = (\varphi)^{m}$$

 

-----------------------------------------------------------------------------------------------------------------------------------------------

 

알고리즘과는 상관없지만

 

오직 수학적 유희를 위해..

 

다음편부터는 알고리즘적으로 중요하니 계속

 

https://www.youtube.com/watch?v=RgjLmjDQQww