피보나치 수열 (Fibonacci Sequence) $F_{n}$의 기본 정의는 다음과 같습니다.
$$ F_{n} = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n - 1} + F_{n - 2} & n \in \mathbb{Z} \end{cases} $$(초항 두개를 $F_{1} = 1, F_{2} = 1$ 로 정의하는 경우도 있지만, 두 정의는 완전히 동일합니다.)
| 항 번호 | $n$번째 항 |
|---|---|
| $0$ | $0$ |
| $1$ | $1$ |
| $2$ | $1$ |
| $3$ | $2$ |
| $4$ | $3$ |
| $5$ | $5$ |
| $6$ | $8$ |
| $7$ | $13$ |
| $8$ | $21$ |
| $9$ | $34$ |
| $10$ | $55$ |
| $11$ | $89$ |
| $12$ | $144$ |
| $13$ | $233$ |
| $14$ | $377$ |
| $15$ | $610$ |
| $16$ | $987$ |
| $17$ | $1597$ |
| $18$ | $2584$ |
| $19$ | $4181$ |
| $20$ | $6765$ |
| $21$ | $10946$ |
| $22$ | $17711$ |
| $23$ | $28657$ |
| $24$ | $46368$ |
| $25$ | $75025$ |
| $26$ | $121393$ |
| $27$ | $196418$ |
| $28$ | $317811$ |
| $29$ | $514229$ |
| $30$ | $832040$ |
| $31$ | $1346269$ |
| $32$ | $2178309$ |
| $33$ | $3524578$ |
| $34$ | $5702887$ |
| $35$ | $9227465$ |
| $36$ | $14930352$ |
| $37$ | $24157817$ |
| $38$ | $39088169$ |
| $39$ | $63245986$ |
| $40$ | $102334155$ |
| $41$ | $165580141$ |
| $42$ | $267914296$ |
| $43$ | $433494437$ |
| $44$ | $701408733$ |
| $45$ | $1134903170$ |
| $46$ | $1836311903$ |
| $47$ | $2971215073$ |
| $48$ | $4807526976$ |
| $49$ | $7778742049$ |
| $50$ | $12586269025$ |
| $51$ | $20365011074$ |
| $52$ | $32951280099$ |
| $53$ | $53316291173$ |
| $54$ | $86267571272$ |
| $55$ | $139583862445$ |
| $56$ | $225851433717$ |
| $57$ | $365435296162$ |
| $58$ | $591286729879$ |
| $59$ | $956722026041$ |
| $60$ | $1548008755920$ |
| $61$ | $2504730781961$ |
| $62$ | $4052739537881$ |
| $63$ | $6557470319842$ |
| $64$ | $10610209857723$ |
| $65$ | $17167680177565$ |
| $66$ | $27777890035288$ |
| $67$ | $44945570212853$ |
| $68$ | $72723460248141$ |
| $69$ | $117669030460994$ |
| $70$ | $190392490709135$ |
| $71$ | $308061521170129$ |
| $72$ | $498454011879264$ |
| $73$ | $806515533049393$ |
| $74$ | $1304969544928657$ |
| $75$ | $2111485077978050$ |
| $76$ | $3416454622906707$ |
| $77$ | $5527939700884757$ |
| $78$ | $8944394323791464$ |
| $79$ | $14472334024676221$ |
| $80$ | $23416728348467685$ |
| $81$ | $37889062373143906$ |
| $82$ | $61305790721611591$ |
| $83$ | $99194853094755497$ |
| $84$ | $160500643816367088$ |
| $85$ | $259695496911122585$ |
| $86$ | $420196140727489673$ |
| $87$ | $679891637638612258$ |
| $88$ | $1100087778366101931$ |
| $89$ | $1779979416004714189$ |
| $90$ | $2880067194370816120$ |
| $91$ | $4660046610375530309$ |
| $92$ | $7540113804746346429$ |
| $93$ | $12200160415121876738$ |
| $94$ | $19740274219868223167$ |
| $95$ | $31940434634990099905$ |
| $96$ | $51680708854858323072$ |
| $97$ | $83621143489848422977$ |
| $98$ | $135301852344706746049$ |
| $99$ | $218922995834555169026$ |
| $100$ | $ $ $354224848179261915075$ $ $ |
0. 기본 전제 - $F_{n}$은 $n$번째 피보나치 수이고, $\phi$는 황금비 이다. ($\phi = \frac{1 + \sqrt{5}}{2}$)
${\phi}^2 = \phi + 1$인 것은 직접 계산을 해보면서 확인할 수 있고, 양 변을 ${\phi}^{2}$로 나누어서 $1 = \frac{1}{\phi} + \frac{1}{{\phi}^2}$에서 $1 - \frac{1}{\phi} = \frac{1}{{\phi}^2}$임을 알 수 있다.
행렬 $M_{n} = \left[ \begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \\ \end{matrix} \right]$ 에다가 행렬 $Q = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]$을 곱하면, 행렬곱의 정의에 따라서 $$ M_{n} Q = \left[ \begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \\ \end{matrix} \right] \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right] = \left[ \begin{matrix} 1 \times F_{n + 1} + 1 \times F_{n} & 1 \times F_{n} + 1 \times F_{n - 1} \\ 1 \times F_{n + 1} + 0 \times F_{n} & 1 \times F_{n} + 0 \times F_{n - 1} \\ \end{matrix} \right] $$ 이다.
먼저, $2 \times 2$ 크기의 행렬 $A = \left[ \begin{matrix} a & b \\ c & d \\ \end{matrix} \right]$에 대하여 $A$의 행렬식 $\det A$는 $\det A = \det \left[ \begin{matrix} a & b \\ c & d \\ \end{matrix} \right] = ad - bc$ 이다.
$\sum\limits_{k = 1}^{n} F_{2k - 1} = S_{n}$이라 하면, $S_{n + 1} - S_{n} = F_{2n + 1}$ 이다.
$\sum\limits_{k = 0}^{n} F_{2k} = S_{n}$이라 하면, $S_{n + 1} - S_{n} = F_{2n + 2}$ 이다.
1. $F_{n} = \frac{1}{\sqrt{5}} \times \frac{ {\left( 1 + \sqrt{5} \right)}^{n} - {\left( 1 - \sqrt{5} \right)}^{n}}{2^{n}} = \frac{\phi^{n} - {(- \phi)}^{-n}}{\sqrt{5}}$ (비네의 공식)
1번 성질 증명
$\frac{\phi^{n} - {(- \phi)}^{-n}}{\sqrt{5}} = T_{n}$으로 두면, $$ T_{n} = \frac{\phi^{n} - {\left(- \frac{1}{\phi}\right)}^{n}}{\sqrt{5}} $$이다.
$$ T_{n} + T_{n + 1} = \frac{\phi^{n} + \phi^{n + 1} - {\left(- \frac{1}{\phi}\right)}^{n} - {\left(- \frac{1}{\phi}\right)}^{n + 1}}{\sqrt{5}} $$에서, $$ T_{n} + T_{n + 1} = \frac{\phi^{n} (1 + \phi) - {\left(- \frac{1}{\phi}\right)}^{n} \left( 1 - \frac{1}{\phi} \right)}{\sqrt{5}} $$ 이고, $\phi + 1 = {\phi}^2$, $1 - \frac{1}{\phi} = \frac{1}{{\phi}^2} = {\left( -\frac{1}{\phi} \right)}^{2}$에서 $$ \frac{\phi^{n} (1 + \phi) - {\left(- \frac{1}{\phi}\right)}^{n} \left( 1 - \frac{1}{\phi} \right)}{\sqrt{5}} = \frac{\phi^{n} \phi^{2} - {\left(- \frac{1}{\phi}\right)}^{n} {\left( -\frac{1}{\phi} \right)}^{2}}{\sqrt{5}} = \frac{\phi^{n + 2} - {\left(- \frac{1}{\phi}\right)}^{n + 2}}{\sqrt{5}} = T_{n + 2} $$ 이다.
따라서 $T_{n} + T_{n + 1} = T_{n + 2}$이고, $T_{0} = 0$, $T_{1} = 1$, $T_{n} + T_{n + 1} = T_{n + 2}$에서 모든 양의 정수 $n$에 대해 $T_{n} = F_{n}$ 이다.
($T_{0} = 0$, $T_{1} = 1$, 이 둘은 직접 손으로 계산할 수 있다.)
2. 모든 양의 정수 $n$에 대하여 다음을 만족한다. (피보나치 수의 행렬곱표현)
$$
\left[ \begin{matrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1} \\
\end{matrix} \right]
=
\left[ \begin{matrix}
1 & 1 \\ 1 & 0 \\
\end{matrix} \right]^{n}
$$
2번 성질 증명
이때, 피보나치 수열의 정의 $F_{n + 2} = F_{n + 1} + F_{n}$를 이용하면 $$ \left[ \begin{matrix} 1 \times F_{n + 1} + 1 \times F_{n} & 1 \times F_{n} + 1 \times F_{n - 1} \\ 1 \times F_{n + 1} + 0 \times F_{n} & 1 \times F_{n} + 0 \times F_{n - 1} \\ \end{matrix} \right] = \left[ \begin{matrix} F_{n + 2} & F_{n + 1} \\ F_{n + 1} & F_{n} \\ \end{matrix} \right] = M_{n + 1}$$ 이다.
임의의 양의 정수 $n$에 대하여 $M_{n} Q = M_{n + 1}$이므로, 이를 반복 적용해주면 임의의 양의 정수 $k$에 대해 $M_{n} Q^{k - 1} = M_{n + k - 1}$이고, $n = 1$ 대입시 $M_{1} Q^{k - 1} = M_{1 + k - 1} = M_{k}$ 이다.
이때, 행렬 $M_{n}$의 정의 $M_{n} = \left[ \begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \\ \end{matrix} \right]$에서 $M_{1} = \left[ \begin{matrix} F_{2} & F_{1} \\ F_{1} & F_{0} \\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right] = Q$이다.
따라서, $M_{1} Q^{k - 1} = Q Q^{k - 1} = Q^{k}$이고, $$ M_{1} Q^{k - 1} = Q^{k} = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]^{k} = \left[ \begin{matrix} F_{k + 1} & F_{k} \\ F_{k} & F_{k - 1} \\ \end{matrix} \right] = M_{k} $$ 이다.
3. $F_{n + 1} F_{n - 1} - {F_{n}}^{2} = {(-1)}^{n}$ (카시니 항등식)
3번 성질 증명
행렬 $M = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]$에 대하여 행렬식 $\det M = \det \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right] = -1$ 이다.
2번 성질에서 $M^{n} = \left[ \begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \\ \end{matrix} \right]$임을 알았고, 행렬식의 성질을 이용하여 $\det \left[ \begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \\ \end{matrix} \right] = \det M^{n} = {\left( \det M \right)}^{n} = (-1) ^{n}$이다.
$\det \left[ \begin{matrix} F_{n + 1} & F_{n} \\ F_{n} & F_{n - 1} \\ \end{matrix} \right] = F_{n + 1} F_{n - 1} - {F_{n}}^{2}$에서, $F_{n + 1} F_{n - 1} - {F_{n}}^{2} = {(-1)}^{n}$ 임을 알 수 있다.
4. ${F_{n}}^2 - F_{n + r}F_{n - r} = (-1)^{n - r}{F_{n}}^2$ (카시니 항등식의 일반화 / 카탈랑 항등식)
5. $F_{m + n} = F_{m - 1} F_{n} + F_{m} F_{n + 1}$ (도가뉴 항등식)
6. $F_{2n} = {F_{n + 1}}^{2} - {F_{n - 1}}^{2}$ (피보나치 수의 짝수번째 항의 연산)
7. $F_{2n - 1} = {F_{n}}^{2} - {F_{n - 1}}^{2}$ (피보나치 수의 홀수번째 항의 연산)
8. $\sum\limits_{k = 0}^{n} F_{k} = F_{n + 2} - 1$ (피보나치 수의 합)
9. $\sum\limits_{k = 0}^{n} {F_{k}}^2 = F_{n} F_{n + 1}$ (피보나치 수의 제곱의 합)
10. $\sum\limits_{k = 1}^{n} F_{2k - 1} = F_{2n}$ (피보나치 수의 홀수번째 항의 합)
10번 성질 증명
$F_{2n} = T_{n}$이라 하면, $T_{n + 1} = F_{2(n + 1)} = F_{2n + 2}$ 이다.
$T_{n + 1} - T_{n} = \left( F_{2n + 2} \right) - \left( F_{2n} \right) = F_{2n + 2} - F_{2n}$ 이다.
피보나치 수열의 정의 $F_{n + 2} = F_{n + 1} + F_{n}$에서 $F_{2n + 2} = F_{2n + 1} + F_{2n}$ 이므로, $F_{2n + 2} - F_{2n} = F_{2n + 1}$이다.
따라서, $T_{n + 1} - T_{n} = F_{2n + 2} - F_{2n} = F_{2n + 1}$이다.
또, $S_{1} = F_{2 \times 1 - 1} = F_{1} = 1$이고, $T_{1} = F_{2 \times 1} = 1$이므로 $S_{1} = T_{1}$이고, $S_{n + 1} - S_{n} = F_{2n + 1}$, $T_{n + 1} - T_{n} = F_{2n + 1}$이다.
따라서, 모든 양의 정수 $n$에 대하여 $S_{n} = T_{n}$임을 알 수 있고, $$ S_{n} = \sum\limits_{k = 1}^{n} F_{2k - 1} = F_{2n} = T_{n} $$ 이다.
11. $\sum\limits_{k = 0}^{n} F_{2k} = F_{2n + 1} - 1$ (피보나치 수의 짝수번째 항의 합)
11번 성질 증명
$F_{2n + 1} - 1 = T_{n}$이라 하면, $T_{n + 1} = F_{2(n + 1) + 1} - 1 = F_{2n + 3} - 1$ 이다.
$T_{n + 1} - T_{n} = \left( F_{2n + 3} - 1 \right) - \left( F_{2n + 1} - 1 \right) = F_{2n + 3} - F_{2n + 1}$ 이다.
피보나치 수열의 정의 $F_{n + 2} = F_{n + 1} + F_{n}$에서 $F_{2n + 3} = F_{2n + 2} + F_{2n + 1}$ 이므로, $F_{2n + 3} - F_{2n + 1} = F_{2n + 2}$이다.
따라서, $T_{n + 1} - T_{n} = F_{2n + 3} - F_{2n + 1} = F_{2n + 2}$이다.
또, $S_{0} = 0$이고, $T_{0} = F_{1} - 1 = 1 - 1 = 0$이므로 $S_{0} = T_{0}$이고, $S_{n + 1} - S_{n} = F_{2n + 2}$, $T_{n + 1} - T_{n} = F_{2n + 2}$이다.
따라서, 모든 음이 아닌 정수 $n$에 대하여 $S_{n} = T_{n}$임을 알 수 있고, $$ S_{n} = \sum\limits_{k = 0}^{n} F_{2k} = F_{2n + 1} - 1 = T_{n} $$ 이다.
12. $\gcd(F_{m}, F_{n}) = F_{\gcd(m, n)} - 1$ (두 피보나치 수의 최대공약수 )
주요 특징들은 여기까지로 하고, 더 복잡한 특징들은 밑에 따로 모아두도록 하겠습니다.
참고자료 1
이상의 특징들을 이용하여 피보나치수를 빠르게 구하거나 피보나치수에 관한 문제를 풀 수 있습니다.
피보나치 수를 단순 재귀함수 형식으로 구하면 $O\left(2^{n}\right)$ 시간에 구할 수 있고,
메모이제이션 방식으로 구하면 $O(n)$ 시간에 구할 수 있고,
행렬곱과 분할정복 거듭제곱을 사용하면 $O(\log{n})$ 시간에 구할 수 있습니다. (피보나치 수열의 특징으로도 구할 수 있습니다.)
행렬 거듭제곱으로 푸는 방식이야 인터넷에 많으니 피보나치 수열의 특징을 짜내서 피보나치 수열만을 구하기 위한 코드입니다.
위의 "기본 성질"에서 6번, 7번 성질을 이용한, 피보나치 짝수항과 홀수항의 관계를 쥐어 짜낸 코드입니다.
물론, 6번, 7번 성질을 이용할 때에도 재귀를 사용하지 않고 할 수 있습니다.
피사노 주기 를 이용하면 아주 큰 $n$에 대하여 $n$번째 피보나치 수를 $m$으로 나눈 값을 아주 빠르게 얻을 수 있습니다.
피보나치 수열 중에서 특별히 소수 인 것을 피보나치 소수 라 하는데, 무한히 있는지는 알려져있지 않습니다.
피보나치 수열의 일반화로 제 1종 뤼카 수열 이 있습니다.
피보나치 수열 특징 (심화)
피보나치 수열의 $n$제곱의 표현 피보나치 수열의 $n$제곱의 합
참고자료 2 (신빙성을 우려했으나 맞는 듯함)
1. 피보나치 수의 3제곱의 합 $$ \sum\limits_{k = 0}^n {F_{k}}^{3} = \frac{1}{10} \left( F_{3n + 2} - 6 {(-1)}^{n} F_{n - 1} + 5\right) $$
2. 피보나치 수의 4제곱의 합 $$ \sum\limits_{k = 0}^n {F_{k}}^{4} = \frac{1}{25} \left( F_{4n + 2} - 4 {(-1)}^{n} F_{2n + 1} + 6n + 3\right) $$
3. 피보나치 수의 5제곱의 합 $$ \sum\limits_{k = 0}^n {F_{k}}^{5} = \frac{1}{550} \left( 2 F_{5n + 3} + 6 F_{5n + 2} - 55 {(-1)}^{n} F_{3n + 1} + 220 F_{n + 2} - 175\right) $$
4. 피보나치 수의 6제곱의 합 $$ \sum\limits_{k = 0}^n {F_{k}}^{6} = \frac{1}{4} \left( {F_{n}}^{5} F_{n + 3} + F_{2n} \right) $$
5. 피보나치 수의 7제곱의 합 $$ \sum\limits_{k = 0}^n {F_{k}}^{7} = \frac{1}{79750} \left( 88 F_{7n + 3} + 110 F_{7n + 2} - 406 {(-1)}^{n} \left( 2 F_{5n + 2} + 3 F_{5n + 1} + 55 F_{n - 1} \right) + 6699 F_{3n + 2} + 17375 \right) $$
6. 피보나치 수의 8제곱의 합 $$ \sum\limits_{k = 0}^n {F_{k}}^{8} = \frac{1}{1875} \left( F_{8n + 4} - 12 {(-1)}^{n} \left( F_{6n + 3} + 14 F_{2n + 1} \right) + 84 F_{4n + 2} + 210n + 105 \right) $$