피보나치 수 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:FibonacciBlocks.png|섬네일|피보나치 수를 이용한 사각형 채우기]]
[[수학]]에서 '''피보나치 수'''({{llang|en|Fibonacci numbers}})는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 [[수열]]이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

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

[[유럽]]에서 피보나치 수를 처음 연구한 것은 [[레오나르도 피보나치]]로 [[토끼]] 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다. ''n'' 번째 달의 토끼 수는
* 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
* 두 달 이상이 된 토끼는 번식 가능하다.
* 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
* 토끼는 죽지 않는다.

따라서 첫 달에는 새로 태어난 토끼 한 쌍이 있고, 두 번째 달에는 그대로 토끼 한 쌍, 세 번째 달부터는 이 토끼 한 쌍이 새끼를 낳게 되어 토끼가 2쌍이 되고, 네 번째 달에는 3쌍, 다섯 번째 달에는 5쌍이 된다.
이때 ''n''번째 달에 ''a'' 쌍의 토끼가 있었고, 다음 ''n''+1번째 달에는 새로 태어난 토끼를 포함해 ''b''쌍이 있었다고 하자. 그러면 그다음 ''n''+2 번째 달에는 ''a''+''b'' 쌍의 토끼가 있게 된다. 이는 ''n''번째 달에 살아있던 토끼는 충분한 나이가 되어 새끼를 낳을 수 있지만, 바로 전 달인 ''n''+1번째 달에 막 태어난 토끼는 아직 새끼를 낳을 수 없기 때문이다.

== 정의 ==
=== 점화식을 통한 정의 ===
'''피보나치 수''' <math>F_n</math>는 다음과 같은 초기값 및 [[점화식]]으로 정의되는 수열이다.
:<math>F_1=F_2=1</math>
:<math>F_n=F_{n-1}+F_{n-2}\qquad(n\in\{3,4,\dots\})</math>
0번째 항부터 시작할 경우 다음과 같이 정의된다.
:<math>F_0=0</math>
:<math>F_1=1</math>
:<math>F_n=F_{n-1}+F_{n-2}\qquad(n\in\{2,3,4,\dots\})</math>
피보나치 수의 처음 몇 항은 (0번째 항부터 시작할 경우) 다음과 같다.
:0, [[1]], 1, [[2]], [[3]], [[5]], [[8]], [[13]], [[21]], [[34]], [[55]], [[89]], [[144]], [[233]], [[377]], [[610]], [[987]], [[1597]], [[2584]], [[4181]], [[6765]], 10946, ... {{OEIS|A000045}}

=== 일반항 ===
피보나치 수의 [[일반항]]은 다음과 같다.<ref name="Vorobiev" />{{rp|19, (1.20)}}
:<math>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}
</math>
여기서 <math>\varphi=(1+\sqrt5)/2</math>는 [[황금비]]이며, <math>\sqrt5</math>는 5의 음이 아닌 [[제곱근]]이다. 이를 '''비네 공식'''({{llang|en|Binet's formula}})이라고 한다. 이는 [[레온하르트 오일러]]가 [[1765년]] 처음 발표했으나 잊혔다가, [[1848년]] [[자크 비네]]에 의해 재발견되었다.

==== 증명 ====
피보나치 수열의 일반항에 대한 증명은 아래와 같다.


a+b=1, ab=-1 인 두 실수 a,b를 가정하자. 그러면 a,b는 이차방정식 <math>x^2-x-1=0</math> 의 두 근이고 이때 판별식 D>0이므로 실수 a,b는 존재함을 알 수 있다.

그러면 피보나치 수열의 점화식 <math>F_{n+2}=F_{n+1}+F_{n}</math> 을 <math>F_{n+2}=(a+b)F_{n+1}- abF_{n}</math> 으로 쓸 수 있고, 

우변의  <math>aF_{n+1}  </math> 을 좌변으로 이항하면 <math>F_{n+2}- aF_{n+1}=b(F_{n+1}- aF_{n})</math> 이 된다. 즉 양변에 동일한 형태를 만들어주었으므로, 이제 <math>(F_{n+1}- aF_{n}) </math> 을 등비수열로 다룰 수 있게 된다. 이때 초항은 <math>F_2- aF_1</math> 이고, 공비는 b가 된다. 

따라서 등비수열의 일반항 공식을 이용해주면 <math>F_{n+1}- aF_{n} = b^{n-1}(F_2 - aF_1)  </math> 이 된다. 그런데 피보나치 수열에서 첫항과 둘째항은 둘 다 1이므로, 다시 써주면 <math>F_{n+1}- aF_{n} = b^n   </math> (<math>\cdots  </math> 식 1)이다(a+b=1에 의해 1-a=b이므로).

그런데 위의 변형된 피보나치 점화식에서 a와 b는 대칭적인 위치에 있으므로, <math>F_{n+2}=(a+b)F_{n+1}- abF_{n}</math> 에서 우변의 <math>bF_{n+1}  </math> 을 좌변으로 이항한 뒤 같은 방식으로 변형해주면 <math>F_{n+1}- bF_{n} = a^n  </math> (<math>\cdots  </math> 식 2)으로 써줄 수 있다. 

이제 식1과 식2를 변변끼리 빼주면, <math>(b-a)F_n = b^{n} - a^{n}  </math>  ,  <math display="block">\therefore F_n = (b^n - a^n)/(b-a) </math>이다. 이때 앞선 이차방정식 <math>x^2-x-1=0</math> 을 통해 a와 b를 직접 구해주면 둘 중 하나가 황금비가 나오는데, a와 b 중 어떤 것을 황금비로 설정하든 결과는 같다. a와 b는 대칭적인 위치에 있기 때문이다. b를 황금비라고 치면, <math>b=\varphi  </math> ,  <math>a=1-\varphi  </math>  이므로 <math>F_n = \frac{\varphi^n-(1-\varphi)^n}{\sqrt5}  </math> 이 된다.

== 성질 ==
=== 항등식 ===
다음과 같은 항등식이 성립하며, '''카시니 항등식'''({{llang|en|Cassini's identity}})이라고 한다.
:<math>F_{n+1}F_{n-1}-{F_n}^2=(-1)^n</math>

다음과 같은 항등식이 성립하며, 이를 '''도가뉴 항등식'''({{llang|en|d'Ocagne's identity}})이라고 한다.<ref name="Vorobiev" />{{rp|9, (1.8)}}
:<math>F_{m+n}=F_{m-1}F_n+F_mF_{n+1}</math>

다음과 같은 항등식이 성립한다.<ref name="Vorobiev" />{{rp|20}}
:<math>\varphi^n=F_n\varphi+F_{n-1}</math>

피보나치 수를 점화식을 통해 [[음의 정수]]에까지 확장할 수 있다. 이 경우, 비네 공식이 여전히 성립하며, 또한 다음이 성립한다.<ref name="Vorobiev" />{{rp|37, (1.40)}}
:<math>F_{-n}=(-1)^{n+1}F_n</math>

=== 급수 공식 ===
처음 몇 피보나치 수의 합,<ref name="Vorobiev">{{서적 인용|성=Vorobiev|이름=Nicolai N.|번역자-성=Martin|번역자-이름=Mircea|제목=Fibonacci Numbers|언어=en|출판사=Springer Basel AG|날짜=2002|원본연도=1992|isbn=978-3-7643-6135-8|doi=10.1007/978-3-0348-8107-4}}</ref>{{rp|5, (1.1)}} 교대합,<ref name="Vorobiev" />{{rp|6, (1.6)}} 제곱합,<ref name="Vorobiev" />{{rp|6, (1.7)}} 세제곱합<ref name="Vorobiev" />{{rp|21}}은 다음과 같다.
:<math>\sum_{k=0}^nF_k=F_{n+2}-1</math>
:<math>\sum_{k=0}^n(-1)^{k+1}F_k=(-1)^{n+1}F_{n-1}+1</math>
:<math>\sum_{k=0}^nF_k^2=F_nF_{n+1}</math>
:<math>\sum_{k=0}^nF_k^3=\frac{F_{3n+2}+(-1)^{n+1}6F_{n-1}+5}{10}</math>

처음 몇 피보나치 수의 홀수째,<ref name="Vorobiev" />{{rp|5, (1.2)}} 짝수째,<ref name="Vorobiev" />{{rp|6, (1.3)}} 3의 배수째<ref name="Vorobiev" />{{rp|21}} 항의 합은 다음과 같다.
:<math>\sum_{k=1}^nF_{2k-1}=F_{2n}</math>
:<math>\sum_{k=0}^nF_{2k}=F_{2n+1}-1</math>
:<math>\sum_{k=0}^nF_{3k}=\frac{F_{3n+2}-1}2</math>

피보나치 수의 역수의 합은 수렴하며, 또한 다음 항등식들이 성립한다.<ref name="Vorobiev" />{{rp|33, (1.34); 33; 34}}
:<math>\begin{align}\sum_{n=1}^\infty\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}</math>
홀수 위치에서 피보나치 수의 역수의 합은 다음 값을 갖는다:
:<math>\sum_{n=1}^{\infty} \frac {1}{F_{2n-1}} = \frac{\sqrt{5}}{\pi}\sqrt{\lambda^*[16\operatorname{arsinh}(1/2)^2/\pi^2]} K\{\lambda^*[16\operatorname{arsinh}(1/2)^2/\pi^2]\}</math>
λ*은 [[모듈러 람다 함수]]이다.

K는 제 1 종 완전 [[타원 적분]]이다.

=== 생성 함수 ===
피보나치 수의 [[생성 함수]]는 다음과 같다.<ref name="Vorobiev" />{{rp|28, (1.28)}}
:<math>\sum_{n=0}^\infty F_nx^n=\frac x{1-x-x^2}</math>

피보나치 수의 [[역수]]의 [[생성 함수]]는 다음과 같이 나타낼 수 있다.<ref name="Vorobiev" />{{rp|35, (1.36); 35; 36; 36}}
:<math>\begin{align}\sum_{n=1}^\infty\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}</math>

=== 점근 공식 ===
[[파일:Fibonacci tiling of the plane and approximation to Golden Ratio.gif|섬네일|이웃하는 피보나치 수의 비]]
이웃하는 피보나치 수의 [[비 (수학)|비]]는 [[황금비]]로 수렴한다.
:<math>\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi</math>

또한, 다음과 같은 [[부등식]]이 성립한다.<ref name="Vorobiev" />{{rp|23}}
:<math>\frac{\varphi^{n-1/n}}{\sqrt5}\le F_n\le\frac{\varphi^{n+1/n}}{\sqrt5}</math>

=== 수론적 성질 ===
피보나치 수열은 서로 인접한 항끼리 [[정수의 서로소|서로소]]이다. 이는 [[귀납법]]으로 간단히 증명할 수 있다.

== 소스 코드 ==

=== [[파이썬]] ===
피보나치 수열은 아래와 같이 함수의 재귀적 용법으로 구현할 수 있다.
<syntaxhighlight lang="python">
def fib(n):
    if n == 0 or n == 1:
        return n
    
    return fib(n-2) + fib(n-1)
</syntaxhighlight>

위 코드는 메모이제이션을 통해 성능을 개선할 수 있다.
<syntaxhighlight lang="python3">
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]
</syntaxhighlight>

== 같이 보기 ==
{{위키공용분류}}
* [[피보나치 수의 일반화]]
* [[엠브리-트레페텐 상수]]
* [[메모이제이션]]

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Fibonacci numbers}}
* {{매스월드|id=FibonacciNumber|title=Fibonacci number}}

{{금속비}}
{{전거 통제}}

[[분류:피보나치 수| ]]
[[분류:정수열]]