피보나치 수

1. 개요

피보나치 수는 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, ...과 같이 앞의 두 항을 더하여 다음 항을 만들어 나가는 수열이다. 이 수열은 기원전 5세기에 인도 수학자에 의해 처음 언급되었고, 유럽에서는 레오나르도 피보나치가 토끼의 번식을 연구하면서 널리 알려졌다. 피보나치 수는 황금비와 밀접한 관련이 있으며, 자연 현상, 수학, 금융 등 다양한 분야에서 발견된다. 피보나치 수열의 정의를 변형하여 트리보나치 수, 테트라나치 수와 같은 유사 수열을 만들 수 있으며, 뤼카 수와 같은 다른 수열도 피보나치 수열과 유사한 방식으로 정의된다. 파이썬을 사용하여 재귀, 메모이제이션, 반복 등의 방법으로 피보나치 수를 계산하는 코드를 구현할 수 있다.

2. 역사

피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책이다.

유럽에서는 레오나르도 피보나치가 1202년 출판한 『산반서』(Liber Abaci)에서 토끼의 번식 문제를 통해 이 수열을 소개하면서 널리 알려졌다. 피보나치는 다음과 같은 가상 상황을 설정했다:

* 한 쌍의 토끼는 태어난 지 2개월 후부터 매달 한 쌍의 토끼를 낳는다.
* 토끼는 죽지 않는다.
* 이 조건 하에서, 새로 태어난 한 쌍의 토끼는 1년 동안 총 몇 쌍으로 늘어날까?

이 문제의 조건에 따르면, 토끼 쌍의 수는 다음과 같이 증가한다. 첫 달에는 새로 태어난 한 쌍만 존재한다. 두 번째 달에도 번식할 수 없으므로 그대로 한 쌍이다. 세 번째 달에는 첫 달의 토끼 쌍이 번식하여 새로운 한 쌍을 낳으므로 총 두 쌍이 된다. 네 번째 달에는 세 번째 달에 있던 두 쌍 중 원래 있던 한 쌍만 번식 가능하므로 새로운 한 쌍이 태어나 총 세 쌍이 된다. 다섯 번째 달에는 네 번째 달에 있던 세 쌍 중 두 쌍(두 달 이상 된 토끼)이 번식하여 새로운 두 쌍을 낳으므로 총 다섯 쌍이 된다. 이처럼 특정 달의 토끼 쌍의 수는 바로 전 달과 그 전전 달의 토끼 쌍의 수를 합한 것과 같아지는데, 이는 피보나치 수열의 정의와 일치한다.

매달 토끼 쌍의 수는 다음 표와 같이 변하며, 피보나치 수가 나타나는 것을 확인할 수 있다.

피보나치 수라는 명칭은 레오나르도 피보나치의 저서에서 비롯되었지만, 그보다 앞서 인도의 학자 헤마찬드라(Hemachandra)가 운율 연구 과정에서 이 수열을 발견하여 기록했다는 사실도 알려져 있다.

3. 정의

피보나치 수 $F\_n$는 0번째 항을 0, 1번째 항을 1로 두고, 2번째 항부터는 바로 앞의 두 항의 합으로 정의되는 수열이다. 즉, 다음과 같은 점화식으로 정의된다.
:$F\_0=0$
:$F\_1=1$
:$F\_n=F\_\{n-1\}+F\_\{n-2\}\backslash qquad(n\backslash geqq\; 2)$
(때로는 $F\_1=1,\; F\_2=1$로 정의하기도 한다.)

피보나치 수의 처음 몇 항은 다음과 같다.
:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, ...

이 수열은 1202년 레오나르도 피보나치(Leonardo Fibonacci)가 저술한 『산반서』(Liber Abaci)에 소개되면서 '피보나치 수'라는 이름으로 널리 알려졌다. 하지만 그보다 앞서 인도의 학자 헤마찬드라(Hemachandra)가 운율 연구 과정에서 이 수열을 발견하여 기록한 바 있다.

레오나르도 피보나치는 『산반서』에서 다음과 같은 문제를 통해 이 수열을 설명했다.
* 한 쌍의 토끼는 태어난 지 2개월 후부터 매달 암수 한 쌍의 토끼를 낳는다.
* 토끼는 죽지 않는다고 가정한다.
* 이 조건에서 갓 태어난 한 쌍의 토끼는 1년 후에 총 몇 쌍으로 불어나는가?

시간에 따른 토끼 쌍의 수는 다음 표와 같이 증가하며, 매달 총 토끼 쌍의 수가 바로 피보나치 수가 됨을 알 수 있다.

3.1. 일반항

피보나치 수의 일반항은 다음과 같다.
:$F\_n$
=\frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}
=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right)
=\frac{\varphi^n-(1-\varphi)^n}{\sqrt5}

여기서 $\backslash varphi=\backslash frac\{1+\backslash sqrt5\}\{2\}\; \backslash approx\; 1.6180339887\backslash dots$는 황금비이며, $1-\backslash varphi\; =\; \backslash frac\{1-\backslash sqrt5\}\{2\}\; \backslash approx\; -0.6180339887\backslash dots$ 이다. 또한 $\backslash sqrt5$는 5의 음이 아닌 제곱근이다.

이 식은 비네 공식(Binet's formula^영어)이라고 불린다. 이 공식은 1730년 아브라함 드 무아브르가 처음 발견했고, 1765년 레온하르트 오일러가 발표했으나 잊혔다가, 1843년 자크 비네에 의해 다시 발표되었다. 비네가 최초 발견자는 아니다.

황금비 $\backslash varphi$는 이차 방정식 $x^2\; -\; x\; -\; 1\; =\; 0$의 두 해 중 큰 값이다. 다른 해를 $\backslash psi\; =\; 1-\backslash varphi\; =\; \backslash frac\{1-\backslash sqrt5\}\{2\}$라고 하면, 일반항은 다음과 같이 나타낼 수도 있다.
:$F\_n=\backslash frac\{\backslash varphi^n-\backslash psi^n\}\{\backslash varphi-\backslash psi\}=\backslash frac\{\backslash varphi^n-\backslash psi^n\}\{\backslash sqrt5\}$

이므로, $n$이 커짐에 따라 $|\backslash psi^n|$ 항은 0에 가까워진다. 따라서 $n$이 충분히 크면 피보나치 수 $F\_n$은 $\backslash frac\{\backslash varphi^n\}\{\backslash sqrt5\}$에 매우 가까워진다. 즉, 다음 근사식이 성립한다.
:$F\_n\; \backslash approx\; \backslash frac\{\backslash varphi^n\}\{\backslash sqrt5\}$
실제로 $n\; \backslash ge\; 0$에 대해 이므로, $F\_n$은 $\backslash frac\{\backslash varphi^n\}\{\backslash sqrt5\}$에 가장 가까운 정수이다. 따라서 바닥 함수(내림 함수)를 이용하여 $F\_n$의 정확한 값을 다음과 같이 표현할 수 있다.
:$F\_n\; =\; \backslash left\backslash lfloor\; \backslash frac\{\backslash varphi^n\}\{\backslash sqrt\{5\}\}\; +\; \backslash frac\{1\}\{2\}\; \backslash right\backslash rfloor\; \backslash quad\; (n\; \backslash ge\; 0)$

피보나치 수열은 점화식 $F\_n\; =\; F\_\{n-1\}\; +\; F\_\{n-2\}$를 이용하여 음의 정수 $n$에 대해서도 확장할 수 있다. 이 경우 $F\_\{-n\}\; =\; (-1)^\{n+1\}F\_n$ 관계가 성립한다. 예를 들어 $F\_\{-1\}\; =\; (-1)^2\; F\_1\; =\; 1$, $F\_\{-2\}\; =\; (-1)^3\; F\_2\; =\; -1$, $F\_\{-3\}\; =\; (-1)^4\; F\_3\; =\; 2$ 이다. 음수 항에 대해서도 비네 공식은 성립한다.

3.2. 행렬 표현

피보나치 수열의 점화식은 다음과 같이 행렬로 표현할 수 있다.
:$\backslash begin\{bmatrix\}\; F\_\{n+1\}\; \backslash \backslash F\_\{n\}\; \backslash end\{bmatrix\}\; =\; \backslash begin\{bmatrix\}$
1 & 1 \\
1 & 0
\end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix},\;\;\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}
이 관계를 반복 적용하면 다음과 같이 행렬의 거듭제곱으로 나타낼 수 있다.
:$\backslash begin\{align\}$
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix} &= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}\begin{bmatrix}
F_{n} & F_{n-1} \\
F_{n-1} & F_{n-2}
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^2\begin{bmatrix}
F_{n-1} & F_{n-2} \\
F_{n-2} & F_{n-3}
\end{bmatrix} \\
&= \cdots \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n\begin{bmatrix}
F_{1} & F_{0} \\
F_{0} & F_{-1}
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix} \quad (\because F_1=1, F_0=0, F_{-1}=1)
\end{align}
따라서 다음의 중요한 행렬 표현을 얻는다.
:$\backslash begin\{align\}$
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\end{align}
여기서 $F\_\{-1\}=1$은 점화식 $F\_n\; =\; F\_\{n-1\}\; +\; F\_\{n-2\}$에 $n=1$을 대입하여 $F\_1\; =\; F\_0\; +\; F\_\{-1\}$로부터 얻을 수 있다(자세한 내용은 음수 번호로의 확장 참조).

이 행렬 표현식의 양변에 $n$ 대신 $2n$을 대입하고 행렬의 거듭제곱 성질을 이용하면 다음과 같은 관계식을 유도할 수 있다.
:$\backslash begin\{align\}$
\begin{bmatrix}
F_{2n+1} & F_{2n} \\
F_{2n} & F_{2n-1}
\end{bmatrix} &= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n} = \left ( \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n \right )^2 = \begin{bmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{bmatrix}^2 \\
&= \begin{bmatrix}
{F_{n+1}}^2 + {F_n}^2 & F_{n+1}F_n + F_n F_{n-1} \\
F_n F_{n+1} + F_{n-1}F_n & {F_n}^2 + {F_{n-1}}^2
\end{bmatrix} \\
&= \begin{bmatrix}
{F_{n+1}}^2 + {F_n}^2 & (F_{n+1} + F_{n-1}) F_n \\
(F_{n+1} + F_{n-1}) F_n & {F_n}^2 + {F_{n-1}}^2
\end{bmatrix}
\end{align}

두 행렬이 같다는 조건으로부터 각 성분을 비교하면 다음 항등식들을 얻는다.
:$\backslash begin\{align\}$
F_{2n+1} &= F_{n+1}^2 + F_n^2 \\
F_{2n} &= (F_{n+1} + F_{n-1}) F_n = (F_n + F_{n-1} + F_{n-1}) F_n = L_n F_n \\
F_{2n-1} &= F_n^2 + F_{n-1}^2
\end{align}

여기서 $L\_n\; =\; F\_\{n+1\}\; +\; F\_\{n-1\}$은 뤼카 수이다. $F\_\{2n\}$에 대한 식은 $F\_\{n+1\}\; =\; F\_n\; +\; F\_\{n-1\}$ 또는 $F\_\{n-1\}\; =\; F\_\{n+1\}\; -\; F\_n$을 이용하여 다음과 같이 변형할 수도 있다.
:$F\_\{2n\}\; =\; (F\_n\; +\; 2F\_\{n-1\})F\_n$
:$F\_\{2n\}\; =\; (2F\_\{n+1\}\; -\; F\_n)F\_n$

또한, 위 행렬 표현식에서 $n$ 대신 $n-1$을 대입하면 다음과 같다.
:$\backslash begin\{bmatrix\}$
F_n & F_{n-1} \\
F_{n-1} & F_{n-2}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{n-1}
따라서 $F\_n$은 행렬 의 (1, 1) 성분(좌상단 성분)과 같다. 이 성질은 행렬의 거듭제곱을 이용하여 피보나치 수를 효율적으로 계산하는 데 사용될 수 있다.

4. 성질

피보나치 수는 여러 흥미로운 항등식을 만족한다. 대표적인 것으로 카시니 항등식(Cassini's identity^영어)이 있다.
:$F\_\{n+1\}F\_\{n-1\}-\{F\_n\}^2=(-1)^n$

또한, 도가뉴 항등식(d'Ocagne's identity^영어)도 성립한다.
:$F\_\{m+n\}=F\_\{m-1\}F\_n+F\_mF\_\{n+1\}$

황금비 $\backslash varphi$와 관련된 다음과 같은 항등식도 성립한다.
:$\backslash varphi^n=F\_n\backslash varphi+F\_\{n-1\}$

피보나치 수는 점화식을 이용해 음의 정수 항으로 확장할 수 있다. 이 경우, 다음과 같은 관계가 성립한다.
:$F\_\{-n\}=(-1)^\{n+1\}F\_n$

피보나치 수열에서 이웃하는 두 항의 비는 $n$이 커짐에 따라 황금비 $\backslash varphi\; =\; \backslash frac\{1+\backslash sqrt\{5\}\}\{2\}\; \backslash approx\; 1.618...$ 로 수렴한다.
:$\backslash lim\_\{n\backslash to\backslash infty\}\backslash frac\{F\_\{n+1\}\}\{F\_n\}=\backslash varphi$
이 성질은 피보나치 수열의 정의 $F\_n\; =\; F\_\{n-1\}\; +\; F\_\{n-2\}$ 로부터 유도할 수 있다. 극한값 $x$가 존재한다고 가정하면, $x\; =\; 1\; +\; \backslash frac\{1\}\{x\}$ 라는 식을 얻고, 이 이차방정식 $x^2\; -\; x\; -\; 1\; =\; 0$ 의 양수 해가 바로 황금비 $\backslash varphi$이다.

또한, 피보나치 수는 황금비를 이용하여 다음과 같은 부등식으로 그 크기를 어림할 수 있다.
:$\backslash frac\{\backslash varphi^\{n-1/n\}\}\{\backslash sqrt5\}\backslash le\; F\_n\backslash le\backslash frac\{\backslash varphi^\{n+1/n\}\}\{\backslash sqrt5\}$

피보나치 수열의 일반항은 비네 공식으로 알려져 있으며, 황금비 $\backslash varphi$를 사용하여 나타낼 수 있다.
:$F\_n\; =\; \backslash frac\{\backslash varphi^n\; -\; (1-\backslash varphi)^n\}\{\backslash sqrt\{5\}\}\; =\; \backslash frac\{\backslash varphi^n\; -\; (-\backslash varphi)^\{-n\}\}\{\backslash sqrt\{5\}\}$
이 공식은 1843년 자크 필리프 마리 비네가 발표했지만, 그보다 앞서 아브라함 드무아브르 (1730년)와 레온하르트 오일러 (1765년)에 의해 알려져 있었다. $n$이 커질수록 $|(-\backslash varphi)^\{-n\}|/\backslash sqrt\{5\}$ 항은 0에 가까워지므로, $F\_n$은 $\backslash frac\{\backslash varphi^n\}\{\backslash sqrt\{5\}\}$에 매우 가까운 값이 된다. 구체적으로, $F\_n$은 $\backslash frac\{\backslash varphi^n\}\{\backslash sqrt\{5\}\}$를 반올림한 정수 값과 같다.
:$F\_n\; =\; \backslash left\backslash lfloor\; \backslash frac\{\backslash varphi^n\}\{\backslash sqrt\{5\}\}\; +\; \backslash frac\{1\}\{2\}\; \backslash right\backslash rfloor$
여기서 $\backslash lfloor\; x\; \backslash rfloor$는 $x$보다 작거나 같은 가장 큰 정수를 나타내는 바닥 함수이다.

피보나치 수열의 점화식은 행렬을 이용하여 다음과 같이 표현할 수 있다.
:
이를 반복 적용하면 다음 관계를 얻는다.
:
이 행렬 표현의 행렬식을 계산하면 이 되어 카시니 항등식을 얻을 수 있다. 또한 이 행렬 표현을 이용하여 다른 여러 항등식을 유도할 수 있다. 예를 들어, $n$을 $2n$으로 바꾸고 행렬의 곱셈을 이용하면 다음과 같은 관계식을 얻는다.
:$F\_\{2n+1\}\; =\; F\_n^2\; +\; F\_\{n+1\}^2$
:$F\_\{2n\}\; =\; F\_n\; (F\_\{n-1\}\; +\; F\_\{n+1\})\; =\; F\_n\; (2\; F\_\{n+1\}\; -\; F\_n)$
:$F\_\{2n-1\}\; =\; F\_\{n-1\}^2\; +\; F\_n^2$

4.1. 급수 공식

처음 몇 피보나치 수의 합, 교대합, 제곱합, 세제곱합은 다음과 같다.
:$\backslash sum\_\{k=0\}^nF\_k=F\_\{n+2\}-1$
:$\backslash sum\_\{k=0\}^n(-1)^\{k+1\}F\_k=(-1)^\{n+1\}F\_\{n-1\}+1$
:$\backslash sum\_\{k=0\}^nF\_k^2=F\_nF\_\{n+1\}$
:$\backslash sum\_\{k=0\}^nF\_k^3=\backslash frac\{F\_\{3n+2\}+(-1)^\{n+1\}6F\_\{n-1\}+5\}\{10\}$

처음 몇 피보나치 수의 홀수째, 짝수째, 3의 배수째 항의 합은 다음과 같다.
:$\backslash sum\_\{k=1\}^nF\_\{2k-1\}=F\_\{2n\}$
:$\backslash sum\_\{k=0\}^nF\_\{2k\}=F\_\{2n+1\}-1$
:$\backslash sum\_\{k=0\}^nF\_\{3k\}=\backslash frac\{F\_\{3n+2\}-1\}2$

피보나치 수의 역수의 합은 수렴하며, 또한 다음 항등식들이 성립한다.
:$\backslash begin\{align\}\backslash sum\_\{n=1\}^\backslash infty\backslash frac1\{F\_n\}$
&=3+\sum_{n=1}^\infty\frac{(-1)^n}{F_nF_{n+1}F_{n+2}}\\
&=\frac{41}{12}-\frac32\sum_{n=1}^\infty\frac1{F_nF_{n+1}F_{n+2}F_{n+3}F_{n+4}}\\
&=\frac{11749}{5280}-\frac{60}{11}\sum_{n=1}^\infty\frac{(-1)^n}{F_nF_{n+1}F_{n+2}F_{n+3}F_{n+4}F_{n+5}F_{n+6}}
\end{align}
홀수 위치에서 피보나치 수의 역수의 합은 다음 값을 갖는다:
:$\backslash sum\_\{n=1\}^\{\backslash infty\}\; \backslash frac\; \{1\}\{F\_\{2n-1\}\}\; =\; \backslash frac\{\backslash sqrt\{5\}\}\{\backslash pi\}\backslash sqrt\{\backslash lambda^*[16\backslash operatorname\{arsinh\}(1/2)^2/\backslash pi^2]\}\; K\backslash \{\backslash lambda^*[16\backslash operatorname\{arsinh\}(1/2)^2/\backslash pi^2]\backslash \}$
여기서 λ*은 모듈러 람다 함수이고, K는 제 1 종 완전 타원 적분이다.

4.2. 생성 함수

피보나치 수의 생성 함수는 다음과 같다.
:$\backslash sum\_\{n=0\}^\backslash infty\; F\_nx^n=\backslash frac\; x\{1-x-x^2\}$

피보나치 수의 역수의 생성 함수는 다음과 같이 나타낼 수 있다.
:$\backslash begin\{align\}\backslash sum\_\{n=1\}^\backslash infty\backslash frac1\{F\_n\}x^n$
&=\sum_{n=1}^\infty\frac{x^n\sqrt5}{\varphi^n}+\sum_{n=1}^\infty(-1)^n\frac{x^n}{F_n\varphi^{2n}}\\
&=\frac{x\sqrt 5}{\varphi-x}+\sum_{n=1}^\infty(-1)^n\frac{x^n}{F_n(F_{2n}\varphi+F_{2n-1})}\\
&=\frac{x\sqrt 5}{\varphi-x}-\frac{x\sqrt 5}{\varphi^3+x}
+\sum_{n=1}^\infty\frac{x^n}{F_n\varphi^{4n}}\\
&=\frac{x\sqrt 5}{\varphi-x}-\frac{x\sqrt 5}{\varphi^3+x}+\frac{x\sqrt 5}{\varphi^5-x}
+\sum_{n=1}^\infty(-1)^n\frac{x^n}{F_n\varphi^{6n}}
\end{align}

4.3. 수론적 성질

피보나치 수열에서 서로 인접한 항은 서로소이다.

또한, 자연수 p, q의 최대공약수를 r이라고 하면, F_p와 F_q의 최대공약수는 F_r이다. 이 성질로부터 다음과 같은 사실들을 유도할 수 있다.
* m이 n으로 나누어 떨어지면, F_m은 F_n으로 나누어 떨어진다.
* F_m이 짝수가 되는 것은 m이 3의 배수일 때와 동치이다.
* F_m이 5의 배수가 되는 것은 m이 5의 배수일 때와 동치이다.
* p가 2도 5도 아닌 소수일 때, m = p − (5/p)라고 하면 p는 F_m을 나눈다. 여기서 ( / )는 르장드르 기호이다.

피보나치 수 중 특정 형태의 수에 대한 성질은 다음과 같다.
* 제곱수인 피보나치 수는 F₁ = F₂ = 1, F₁₂ = 144 뿐이다 (Cohn 1964).
* 세제곱수인 피보나치 수는 F₁ = F₂ = 1, F₆ = 8 뿐이다 (London and Finkelstein 1969).
* 거듭제곱수인 피보나치 수는 위의 제곱수와 세제곱수 외에는 존재하지 않는다 (Bugeaud, Mignotte, Siksek 2006). (OEIS A227875)
* 소수인 피보나치 수는 2, 3, 5, 13, 89, 233, 1597, 28657, … 등이 있으며 (OEIS A005478), 이들을 피보나치 소수라고 부른다.
* 삼각수인 피보나치 수는 1, 3, 21, 55 (OEIS A039595) 뿐이다. 이는 Vern Hoggatt에 의해 추측되었고, 나중에 Luo Ming에 의해 증명되었다.
* 하샤드 수인 피보나치 수는 1, 2, 3, 5, 8, 21, 144, 2584, … 등이 있다 (OEIS A117774).
* 피보나치 수는 완전수가 될 수 없다. 더 나아가, 피보나치 수는 배적 완전수도 될 수 없으며, 두 피보나치 수의 비 또한 완전수가 될 수 없다.

임의의 양의 정수는 하나 이상의 연속하지 않은 서로 다른 피보나치 수의 합으로 유일하게 표현할 수 있는데, 이를 제켄도르프 정리라고 한다.

5. 여러 가지 예시

피보나치 수열의 점화식은 다음과 같이 행렬로 표현할 수 있다.
:$\backslash begin\{bmatrix\}\; F\_\{n+1\}\; \backslash \backslash F\_\{n\}\; \backslash end\{bmatrix\}\; =\; \backslash begin\{bmatrix\}$
1 & 1 \\
1 & 0
\end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix},\;\;\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix}
이를 반복하여 적용하면 다음과 같은 행렬 관계식을 얻는다.
:$\backslash begin\{align\}$
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix} &= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}\begin{bmatrix}
F_{n} & F_{n-1} \\
F_{n-1} & F_{n-2}
\end{bmatrix} \\
&= \cdots \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n\begin{bmatrix}
F_{1} & F_{0} \\
F_{0} & F_{-1}
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}
\end{align}
여기서 $F\_1=1,\; F\_0=0$이며, $F\_\{-1\}=1$은 점화식 $F\_n\; =\; F\_\{n-1\}\; +\; F\_\{n-2\}$에 $n=1$을 대입하여 얻을 수 있다(자세한 내용은 음수 번호로의 확장 참조). 따라서 다음이 성립한다.
:$\backslash therefore$
\begin{align}
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\end{align}

또한, 위 행렬 관계식에서 $n$을 $2n$으로 치환하면,
:$\backslash begin\{align\}$
\begin{bmatrix}
F_{2n+1} & F_{2n} \\
F_{2n} & F_{2n-1}
\end{bmatrix} &= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n} = \left ( \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n \right )^2 = \begin{bmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{bmatrix}^2 \\
&= \begin{bmatrix}
F_{n+1}^2 + F_n^2 & F_n(F_{n+1} + F_{n-1}) \\
F_n(F_{n+1} + F_{n-1}) & F_n^2 + F_{n-1}^2
\end{bmatrix}
\end{align}

따라서, 다음과 같은 항등식을 얻는다.
:$\backslash begin\{align\}$
F_{2n+1} &= F_{n+1}^2 + F_n^2 \\
F_{2n} &= F_n(F_{n+1} + F_{n-1}) = F_n(F_n + 2F_{n-1}) \\
F_{2n-1} &= F_n^2 + F_{n-1}^2
\end{align}


피보나치 수열의 모 생성 함수는 다음과 같다.
:$g(x)\; =\; \backslash sum\backslash limits\_\{n=0\}^\{\backslash infty\}\; F\_n\; x^n\; =\; \backslash dfrac\{x\}\{1-x-x^2\}$

또한, 행렬 표현을 기반으로 다음과 같은 점화식을 생각할 수도 있다.
:$\backslash begin\{cases\}$
F_0 = 0 & \, \\
F_1 = 1 & \, \\
F_n = F_q^2+\{ 1+(-1)^n \}F_{q-1}F_q+\dfrac{1-(-1)^n}{2}F_{q+1}^2 &\left( n\geqq 2,\;q=\left\lfloor \dfrac{n}{2} \right\rfloor \right)
\end{cases}


피보나치 수열은 재귀 처리의 예시로 자주 소개된다. 다음은 파이썬에서의 예시이다.

(단, 아래 구현 예시 중 음수 번째 항으로의 확장에 대응하는 것은 예시 5, 예시 6뿐이다.)

5.1. 자연 속의 피보나치 수열

(원본 소스에 해당 섹션 내용이 존재하지 않아, 내용을 작성할 수 없습니다.)

5.2. 금융 분야

환율 등의 기술적 분석에서, 피보나치 되돌림이라는 기법이 자주 사용된다.

6. 유사 수열

피보나치 수열은 그 정의, 즉 초기값이나 점화식을 약간 변경하여 다양한 유사 수열을 만들 수 있다. 예를 들어, 각 항이 바로 앞 두 항의 합으로 결정되는 규칙 대신, 더 많은 이전 항들의 합으로 새로운 항을 정의하는 방식으로 일반화할 수 있다. 또한, 수열의 시작 값인 처음 몇 개의 항을 다르게 설정하여 또 다른 종류의 유사 수열을 만들 수도 있다. 이러한 방식으로 생성된 수열들은 피보나치 수열과 유사한 성질을 가지면서도 독특한 특징을 나타낸다.

6.1. 항 수 변경

피보나치 수열은 각 항이 바로 앞 두 항의 합으로 이루어지지만, 이를 "바로 앞 k 항의 합"으로 바꾸어 일반화할 수 있다.
:$F\_\{n+k\}^\{(k)\}\; :=\; F\_\{n+k-1\}^\{(k)\}\; +\; F\_\{n+k-2\}^\{(k)\}\; +\; \backslash dotsb\; +\; F\_n^\{(k)\}\backslash quad\; (n\backslash ge\; 0)$
이러한 일반화된 피보나치 수열을 정의할 때는 초기값을 설정하는 방식이 필요하다. 주로 두 가지 방식이 사용된다.
* 1-fil형: 처음 k-1개 항을 모두 1로 설정한다.
:$F\_0^\{(k)\}\; =\; F\_1^\{(k)\}=\backslash dotsb=F\_\{k-1\}^\{(k)\}=1$
* 0-fil형: 마지막 항인 (k-1)번째 항만 1로 설정하고, 그 앞의 항들은 모두 0으로 설정한다.
:$F\_0^\{(k)\}\; =\; F\_1^\{(k)\}=\backslash dotsb=F\_\{k-2\}^\{(k)\}=0,\backslash quad\; F\_\{k-1\}^\{(k)\}=1$

이처럼 일반화된 피보나치 수열들은 항 수 k에 해당하는 라틴어 또는 그리스어 배수 접두사와 '피보나치'를 조합하여 이름을 붙인다. 예를 들어, k=3일 때는 트리보나치 수열, k=4일 때는 테트라나치 수열이라고 부른다.

특히 k=3인 경우, 즉 바로 앞 세 항의 합으로 각 항이 정해지는 트리보나치 수열(Tribonacci sequence)은 피보나치 수열 다음으로 많이 연구된다. 0-fil형으로 0번째 항부터 시작하는 트리보나치 수열($T\_n$)은 다음과 같이 정의된다.
:$T\_0\; =\; 0,\; T\_1\; =\; 0,\; T\_2\; =\; 1$
:$T\_\{n+3\}\; =\; T\_n\; +\; T\_\{n+1\}\; +\; T\_\{n+2\}\; \backslash quad\; (n\; \backslash ge\; 0)$
이 수열의 처음 몇 항은 다음과 같다.
:0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, … (OEIS A000073)

트리보나치 수열의 일반항은 3차 방정식 $x^3\; -\; x^2\; -\; x\; -\; 1\; =\; 0$의 세 해 $\backslash alpha,\; \backslash beta,\; \backslash gamma$를 이용하여 다음과 같이 나타낼 수 있다.
:$T\_n\; =\; \backslash frac\{\backslash alpha^n\}\{(\backslash alpha\; -\; \backslash beta)(\backslash alpha\; -\; \backslash gamma)\}+\; \backslash frac\{\backslash beta^n\}\{(\backslash beta\; -\; \backslash gamma)(\backslash beta\; -\; \backslash alpha)\}+\; \backslash frac\{\backslash gamma^n\}\{(\backslash gamma\; -\; \backslash alpha)(\backslash gamma\; -\; \backslash beta)\}$
여기서 세 해는 다음과 같다.
:$\backslash begin\{align\}$
\alpha &= \frac{1}{3} \left(1 + \sqrt[3]{19-3\sqrt{33}} + \sqrt[3]{19+3\sqrt{33}}\right) \\
\beta &= \frac{1}{3} \left(1 + \omega \sqrt[3]{19-3\sqrt{33}} + \bar{\omega} \sqrt[3]{19+3\sqrt{33}}\right) \\
\gamma &= \frac{1}{3} \left(1 + \bar{\omega} \sqrt[3]{19-3\sqrt{33}} + \omega \sqrt[3]{19+3\sqrt{33}}\right)
\end{align}
(단, $\backslash omega\; =\; \backslash frac\{-1\; +\; \backslash sqrt\{3\}\; i\}\{2\}$는 1의 허수 세제곱근이다.)

이때 실수 해 $\backslash alpha\; \backslash approx\; 1.839286755214161\backslash cdots$를 트리보나치 상수라고 부른다. 이는 피보나치 수열의 황금비에 해당하는 상수로, 트리보나치 수열에서 인접한 두 항의 비는 n이 커짐에 따라 트리보나치 상수로 수렴한다.
:$\backslash lim\_\{n\; \backslash to\; \backslash infty\}\; \backslash frac\{T\_n\}\{T\_\{n-1\}\}\; =\; \backslash alpha$

k=4인 경우, 즉 바로 앞 네 항의 합으로 정해지는 테트라나치 수열(Tetranacci sequence)도 알려져 있다. 0-fil형으로 0번째 항부터 시작하는 테트라나치 수열($T\_n$)은 다음과 같이 정의된다.
:$T\_0\; =\; 0,\; T\_1\; =\; 0,\; T\_2\; =\; 0,\; T\_3\; =\; 1$
:$T\_\{n+4\}\; =\; T\_n\; +\; T\_\{n+1\}\; +\; T\_\{n+2\}\; +\; T\_\{n+3\}\; \backslash quad\; (n\; \backslash ge\; 0)$
이 수열의 처음 몇 항은 다음과 같다.
: 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, … (OEIS A000078)

테트라나치 수열의 일반항은 사차 방정식 $x^4\; -\; x^3\; -\; x^2\; -\; x\; -\; 1\; =\; 0$의 네 해 $\backslash alpha,\; \backslash beta,\; \backslash gamma,\; \backslash delta$를 이용하여 다음과 같이 나타낼 수 있다.
:$T\_n\; =\; \backslash frac\{\backslash alpha^n\}\{(\backslash alpha-\; \backslash beta)(\backslash alpha\; -\; \backslash gamma)(\backslash alpha\; -\; \backslash delta)\}+\; \backslash frac\{\backslash beta^n\}\{(\backslash beta\; -\; \backslash gamma)(\backslash beta\; -\; \backslash delta)(\backslash beta\; -\; \backslash alpha)\}+\; \backslash frac\{\backslash gamma^n\}\{(\backslash gamma\; -\; \backslash delta)(\backslash gamma\; -\; \backslash alpha)(\backslash gamma\; -\; \backslash beta)\}+\; \backslash frac\{\backslash delta^n\}\{(\backslash delta\; -\; \backslash alpha)(\backslash delta\; -\; \backslash beta)(\backslash delta\; -\; \backslash gamma)\}$

6.2. 초기값 변경

피보나치 수열의 처음 두 항을 2, 1로 바꾼 수열의 항을 뤼카 수라고 한다.
: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, … (OEIS A000032)
이 수열의 일반항은
:$L\_n\; =\; \backslash left(\; \backslash frac\{1+\backslash sqrt\{5\}\}\{2\}\; \backslash right)^n\; +\; \backslash left(\; \backslash frac\{1-\backslash sqrt\{5\}\}\{2\}\; \backslash right)^n=\; \backslash varphi^n\; +\; (1-\backslash varphi)^n\; =\; \{\backslash varphi^n\; +\; (-\backslash varphi)^\{-n\}\}$
로 나타낸다.

피보나치 수열이나 뤼카 수의 열을 일반화한 것이 뤼카 수열이며, 1878년에 에두아르 뤼카가 체계적인 연구를 수행했고, 1913년에 Robert Daniel Carmichael^영어이 그 결과를 정리, 확장했다. 이러한 연구가 현대의 피보나치 수 이론의 기초가 되었다.

7. 프로그래밍 구현 (파이썬)

피보나치 수는 재귀 처리의 예시로 자주 소개된다. 다음은 파이썬을 이용한 다양한 구현 예시이다.

=== 재귀적 구현 ===
가장 기본적인 방법은 피보나치 수의 정의를 그대로 코드로 옮긴 재귀 함수를 사용하는 것이다. 0번째 항부터 시작하는 경우, 코드는 다음과 같다.

def fib(n):
if n == 0 or n == 1:
return n
return fib(n-2) + fib(n-1)

또는 타입 힌트를 사용하여 다음과 같이 작성할 수도 있다.

def fib(n: int) -> int:
if n < 2:
return n
else:
return fib(n=n-1) + fib(n=n-2)

그러나 이 방식은 n이 주어졌을 때 F_n을 구하기까지 F_n ∝ φⁿ (여기서 φ는 황금비) 번의 함수 호출이 발생하여 지수 시간 복잡도를 가진다. 즉, n이 조금만 커져도 계산 시간이 매우 길어져 실용적이지 않다.

=== 메모이제이션을 이용한 재귀적 구현 ===
재귀적 구현의 비효율성을 개선하기 위해 메모이제이션 기법을 사용할 수 있다. 이미 계산된 피보나치 수 값을 저장해두고, 필요할 때 다시 계산하는 대신 저장된 값을 사용하는 방식이다.

memo = {}

def fib(n):
if n == 0 or n == 1:
return n
if n not in memo:
memo[n] = fib(n-2) + fib(n-1)
return memo[n]

파이썬의 `functools` 모듈에 있는 `cache` 데코레이터를 사용하면 더 간편하게 메모이제이션을 구현할 수 있다.

from functools import cache

@cache
def fib(n: int) -> int:
if n < 2:
return n
else:
return fib(n=n-1) + fib(n=n-2)

메모이제이션을 사용하면 각 피보나치 수는 한 번만 계산되므로 선형 시간 복잡도로 계산할 수 있다.

=== 반복적 구현 ===
반복문을 사용하여 피보나치 수를 계산할 수도 있다. 이 방법은 재귀 호출의 오버헤드가 없고 메모리 사용량도 적어 효율적이다.

def fib(n: int) -> int:
a, b = 1, 0 # F_1, F_0 에 해당하는 값으로 시작 (n=0일 때 b=0 반환)
for _ in range(n):
a, b = b, a+b # 다음 항 계산 (b가 F_k, a+b가 F_{k+1}이 됨)
return b # n번 반복 후 b는 F_n이 됨

이 구현 역시 선형 시간 복잡도를 가진다.

=== 꼬리 재귀 형태의 구현 ===
일부 언어에서는 꼬리 재귀 최적화를 지원하지만, 표준 파이썬 인터프리터는 이를 지원하지 않는다. 그러나 꼬리 재귀와 유사한 형태로 함수를 작성하여 반복적인 계산 과정을 표현할 수 있다. 이 방식은 추가적인 인자를 사용하여 상태를 전달한다.

def fib(n: int, a: int = 1, b: int = 0) -> int:
# a는 F_{k+1}, b는 F_k 에 해당하는 값을 가짐
if n == 0:
return b # n번 반복 후 b는 F_n
else:
# 다음 단계로 상태 업데이트 (a -> b, b -> a+b)
return fib(n=n-1, a=b, b=a+b)

이 함수는 n이 1 이상일 때, 호출 횟수를 n 회로 제한하여 선형 시간으로 처리할 수 있다.

=== 행렬 표현을 이용한 구현 ===
피보나치 수열의 점화식은 다음과 같이 행렬로 표현할 수 있다.
:
이를 반복 적용하면 다음 관계식을 얻는다.
:
여기서 n을 n - 1로 치환하면,
:
따라서 F_n은 행렬 의 좌상단 성분과 같다. 행렬의 거듭제곱은 분할 정복 알고리즘을 이용하여 로그 시간에 계산할 수 있으므로, 이를 이용하면 피보나치 수를 매우 빠르게 계산할 수 있다. SymPy 라이브러리를 사용한 예시는 다음과 같다.

from sympy import Matrix

def fib(n: int) -> int:
if n == 0: # 행렬 거듭제곱은 n-1을 사용하므로 n=0 예외 처리
return 0
# (n-1) 거듭제곱 계산 후 좌상단 성분 반환
return (Matrix(1, 1], [1, 0) (n - 1))[0, 0]


또한, 행렬 표현에서 유도된 다음 점화식을 사용하여 재귀적으로 구현할 수도 있다. 이 방식은 재귀 호출 횟수를 줄여 대수 시간(로그 시간) 복잡도를 가진다.
:
이를 코드로 구현하면 다음과 같다. 단, 프로그램 상에서는 0을 곱하는 경우에도 해당 값의 계산이 생략되지 않으므로(단락 평가되지 않음), 조건식을 사용하여 분기한다. 실제 효율적인 사용을 위해서는 메모이제이션이 필수적이다.

# 이 구현은 앞서 정의된 fib 함수에 의존하며, 메모이제이션과 함께 사용해야 효율적이다.
# 여기서는 설명을 위해 독립적인 함수 형태로 제시하며, 실제 사용 시에는 메모이제이션 적용 필요.
memo_fast = {}
def fib_fast(n: int) -> int:
if n in memo_fast:
return memo_fast[n]
if n < 2:
return n

q = n // 2
fq = fib_fast(n=q)
fq_minus_1 = fib_fast(n=q-1) # F_{q-1}

if n % 2 == 0: # n이 짝수일 때 F_n = F_q^2 + 2 * F_{q-1} * F_q
result = fq 2 + 2 * fq_minus_1 * fq
else: # n이 홀수일 때 F_n = F_q^2 + F_{q+1}^2
# F_{q+1} = F_q + F_{q-1} 이므로 다시 계산할 필요 없이 사용 가능
fq_plus_1 = fq + fq_minus_1
result = fq 2 + fq_plus_1 2

memo_fast[n] = result
return result

# 초기 호출 예시 (메모이제이션 딕셔너리 초기화 필요)
# memo_fast = {}
# print(fib_fast(10))

주의: 위 `fib_fast` 코드는 설명을 위한 것이며, 실제 효율적인 사용을 위해서는 `fib_fast` 함수 내에서 재귀 호출 시에도 `fib_fast`를 호출하고, 전역 또는 클래스 멤버 등으로 `memo_fast` 딕셔너리를 관리하여 메모이제이션을 올바르게 적용해야 한다.

=== 일반항을 이용한 구현 ===
비네 공식으로 알려진 피보나치 수의 일반항을 이용하여 계산할 수도 있다.
:$F\_n\; =\; \backslash frac\{\backslash varphi^n\; -\; \backslash psi^n\}\{\backslash sqrt\{5\}\}\; =\; \backslash frac\{\backslash left(\backslash frac\{1+\backslash sqrt\{5\}\}\{2\}\backslash right)^n\; -\; \backslash left(\backslash frac\{1-\backslash sqrt\{5\}\}\{2\}\backslash right)^n\}\{\backslash sqrt\{5\}\}$
여기서 $\backslash varphi\; =\; \backslash frac\{1+\backslash sqrt\{5\}\}\{2\}$는 황금비이고, $\backslash psi\; =\; \backslash frac\{1-\backslash sqrt\{5\}\}\{2\}\; =\; 1\; -\; \backslash varphi\; =\; -\backslash frac\{1\}\{\backslash varphi\}$이다.

부동소수점 연산을 사용하면 계산 오차가 발생할 수 있으므로, 정확한 계산을 위해 파이썬의 `decimal` 모듈을 사용할 수 있다.

from decimal import Decimal, getcontext

# 필요에 따라 정밀도 설정 (예: getcontext().prec = 50)

SQRT5 = Decimal(5).sqrt()
PHI = (1 + SQRT5) / 2 # 황금비

def fib(n: int) -> int:
if n == 0: return 0
# |PSI^n / sqrt(5)|는 n이 커짐에 따라 0에 수렴하며, n >= 1에 대해 0.5보다 작다.
# 따라서 F_n은 PHI^n / sqrt(5) 에 가장 가까운 정수이다.
# F_n = round(PHIn / SQRT5)
# PSI = -1/PHI 관계를 이용하여 계산할 수도 있다.
return int(round((PHI n - (-PHI) -n) / SQRT5))

또한, 피보나치 수의 일반항은 n의 부호에 따라 두 항 중 하나의 절댓값이 0.5 미만이 되므로, 부호 함수와 바닥 함수를 사용하여 다음과 같이 나타낼 수도 있다.
:$F\_n\; =\; (\backslash operatorname\{sgn\}\; n)\backslash left\backslash lfloor\; \backslash frac\{\backslash \{\; (\backslash operatorname\{sgn\}\; n)\backslash varphi\; \backslash \}^$