|
=== 일반항 ===
피보나치 수의 [[일반항]]은 다음과 같다.<ref name="Vorobiev">{{서적 인용|제목=Fibonacci Numbers|성=Vorobiev|이름=Nicolai N.|날짜=2002|출판사=Springer Basel AG|언어=en|원본연도=1992|doi=10.1007/978-3-0348-8107-4|isbn=978-3-7643-6135-8|번역자-성=Martin|번역자-이름=Mircea}}</ref>{{rp|19, (1.20)}}
:<math>F_n
=\frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}
== 성질 ==
=== 항등식 ===
<syntaxhighlight lang="python3">
다음과 같은 항등식이 성립하며, '''카시니 항등식'''({{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>
=== 수론적 성질 ===
피보나치 수열은 서로 인접한 항끼리 [[정수의 서로소|서로소]]이다. 이는 [[귀납법]]으로 간단히 증명할 수 있다.
== 소스 코드 ==
=== [[파이썬]] ===
0번째 항부터 시작할 경우를 파이썬 코드로 구현하면 아래와 같다.<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 = {}
| 