피보나치 수를 이용한 사각형 채우기 수학 에서 피보나치 수 (영어 : 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번째 달에 막 태어난 토끼는 아직 새끼를 낳을 수 없기 때문이다.
피보나치 수
F
n
{\displaystyle F_{n}}
점화식 으로 정의되는 수열이다.
F
1
=
F
2
=
1
{\displaystyle F_{1}=F_{2}=1}
F
n
=
F
n
− − -->
1
+
F
n
− − -->
2
(
n
∈ ∈ -->
{
3
,
4
,
… … -->
}
)
{\displaystyle F_{n}=F_{n-1}+F_{n-2}\qquad (n\in \{3,4,\dots \})}
0번째 항부터 시작할 경우 다음과 같이 정의된다.
F
0
=
0
{\displaystyle F_{0}=0}
F
1
=
1
{\displaystyle F_{1}=1}
F
n
=
F
n
− − -->
1
+
F
n
− − -->
2
(
n
∈ ∈ -->
{
2
,
3
,
4
,
… … -->
}
)
{\displaystyle F_{n}=F_{n-1}+F_{n-2}\qquad (n\in \{2,3,4,\dots \})}
피보나치 수의 처음 몇 항은 (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 )
피보나치 수의 일반항 은 다음과 같다.[ 1] :19, (1.20)
F
n
=
(
1
+
5
)
n
− − -->
(
1
− − -->
5
)
n
2
n
5
=
1
5
(
(
1
+
5
2
)
n
− − -->
(
1
− − -->
5
2
)
n
)
=
φ φ -->
n
− − -->
(
1
− − -->
φ φ -->
)
n
5
{\displaystyle F_{n}={\frac {(1+{\sqrt {5}})^{n}-(1-{\sqrt {5}})^{n}}{2^{n}{\sqrt {5}}}}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)={\frac {\varphi ^{n}-(1-\varphi )^{n}}{\sqrt {5}}}}
여기서
φ φ -->
=
(
1
+
5
)
/
2
{\displaystyle \varphi =(1+{\sqrt {5}})/2}
황금비 이며,
5
{\displaystyle {\sqrt {5}}}
제곱근 이다. 이를 비네 공식 (영어 : Binet's formula )이라고 한다. 이는 레온하르트 오일러 가 1765년 처음 발표했으나 잊혔다가, 1848년 자크 비네 에 의해 재발견되었다.
다음과 같은 항등식이 성립하며, 카시니 항등식 (영어 : Cassini's identity )이라고 한다.
F
n
+
1
F
n
− − -->
1
− − -->
F
n
2
=
(
− − -->
1
)
n
{\displaystyle F_{n+1}F_{n-1}-{F_{n}}^{2}=(-1)^{n}}
다음과 같은 항등식이 성립하며, 이를 도가뉴 항등식 (영어 : d'Ocagne's identity )이라고 한다.[ 1] :9, (1.8)
F
m
+
n
=
F
m
− − -->
1
F
n
+
F
m
F
n
+
1
{\displaystyle F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1}}
다음과 같은 항등식이 성립한다.[ 1] :20
φ φ -->
n
=
F
n
φ φ -->
+
F
n
− − -->
1
{\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}}
피보나치 수를 점화식을 통해 음의 정수 에까지 확장할 수 있다. 이 경우, 비네 공식이 여전히 성립하며, 또한 다음이 성립한다.[ 1] :37, (1.40)
F
− − -->
n
=
(
− − -->
1
)
n
+
1
F
n
{\displaystyle F_{-n}=(-1)^{n+1}F_{n}}
처음 몇 피보나치 수의 합,[ 1] :5, (1.1) [ 1] :6, (1.6) [ 1] :6, (1.7) [ 1] :21
∑ ∑ -->
k
=
0
n
F
k
=
F
n
+
2
− − -->
1
{\displaystyle \sum _{k=0}^{n}F_{k}=F_{n+2}-1}
∑ ∑ -->
k
=
0
n
(
− − -->
1
)
k
+
1
F
k
=
(
− − -->
1
)
n
+
1
F
n
− − -->
1
+
1
{\displaystyle \sum _{k=0}^{n}(-1)^{k+1}F_{k}=(-1)^{n+1}F_{n-1}+1}
∑ ∑ -->
k
=
0
n
F
k
2
=
F
n
F
n
+
1
{\displaystyle \sum _{k=0}^{n}F_{k}^{2}=F_{n}F_{n+1}}
∑ ∑ -->
k
=
0
n
F
k
3
=
F
3
n
+
2
+
(
− − -->
1
)
n
+
1
6
F
n
− − -->
1
+
5
10
{\displaystyle \sum _{k=0}^{n}F_{k}^{3}={\frac {F_{3n+2}+(-1)^{n+1}6F_{n-1}+5}{10}}}
처음 몇 피보나치 수의 홀수째,[ 1] :5, (1.2) [ 1] :6, (1.3) [ 1] :21
∑ ∑ -->
k
=
1
n
F
2
k
− − -->
1
=
F
2
n
{\displaystyle \sum _{k=1}^{n}F_{2k-1}=F_{2n}}
∑ ∑ -->
k
=
0
n
F
2
k
=
F
2
n
+
1
− − -->
1
{\displaystyle \sum _{k=0}^{n}F_{2k}=F_{2n+1}-1}
∑ ∑ -->
k
=
0
n
F
3
k
=
F
3
n
+
2
− − -->
1
2
{\displaystyle \sum _{k=0}^{n}F_{3k}={\frac {F_{3n+2}-1}{2}}}
피보나치 수의 역수의 합은 수렴하며, 또한 다음 항등식들이 성립한다.[ 1] :33, (1.34); 33; 34
∑ ∑ -->
n
=
1
∞ ∞ -->
1
F
n
=
3
+
∑ ∑ -->
n
=
1
∞ ∞ -->
(
− − -->
1
)
n
F
n
F
n
+
1
F
n
+
2
=
41
12
− − -->
3
2
∑ ∑ -->
n
=
1
∞ ∞ -->
1
F
n
F
n
+
1
F
n
+
2
F
n
+
3
F
n
+
4
=
11749
5280
− − -->
60
11
∑ ∑ -->
n
=
1
∞ ∞ -->
(
− − -->
1
)
n
F
n
F
n
+
1
F
n
+
2
F
n
+
3
F
n
+
4
F
n
+
5
F
n
+
6
{\displaystyle {\begin{aligned}\sum _{n=1}^{\infty }{\frac {1}{F_{n}}}&=3+\sum _{n=1}^{\infty }{\frac {(-1)^{n}}{F_{n}F_{n+1}F_{n+2}}}\\&={\frac {41}{12}}-{\frac {3}{2}}\sum _{n=1}^{\infty }{\frac {1}{F_{n}F_{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_{n}F_{n+1}F_{n+2}F_{n+3}F_{n+4}F_{n+5}F_{n+6}}}\end{aligned}}}
홀수 위치에서 피보나치 수의 역수의 합은 다음 값을 갖는다:
∑ ∑ -->
n
=
1
∞ ∞ -->
1
F
2
n
− − -->
1
=
5
π π -->
λ λ -->
∗ ∗ -->
[
16
arsinh
-->
(
1
/
2
)
2
/
π π -->
2
]
K
{
λ λ -->
∗ ∗ -->
[
16
arsinh
-->
(
1
/
2
)
2
/
π π -->
2
]
}
{\displaystyle \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}]\}}
λ*은 모듈러 람다 함수 이다.
K는 제 1 종 완전 타원 적분 이다.
피보나치 수의 생성 함수 는 다음과 같다.[ 1] :28, (1.28)
∑ ∑ -->
n
=
0
∞ ∞ -->
F
n
x
n
=
x
1
− − -->
x
− − -->
x
2
{\displaystyle \sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}}
피보나치 수의 역수 의 생성 함수 는 다음과 같이 나타낼 수 있다.[ 1] :35, (1.36); 35; 36; 36
∑ ∑ -->
n
=
1
∞ ∞ -->
1
F
n
x
n
=
∑ ∑ -->
n
=
1
∞ ∞ -->
x
n
5
φ φ -->
n
+
∑ ∑ -->
n
=
1
∞ ∞ -->
(
− − -->
1
)
n
x
n
F
n
φ φ -->
2
n
=
x
5
φ φ -->
− − -->
x
+
∑ ∑ -->
n
=
1
∞ ∞ -->
(
− − -->
1
)
n
x
n
F
n
(
F
2
n
φ φ -->
+
F
2
n
− − -->
1
)
=
x
5
φ φ -->
− − -->
x
− − -->
x
5
φ φ -->
3
+
x
+
∑ ∑ -->
n
=
1
∞ ∞ -->
x
n
F
n
φ φ -->
4
n
=
x
5
φ φ -->
− − -->
x
− − -->
x
5
φ φ -->
3
+
x
+
x
5
φ φ -->
5
− − -->
x
+
∑ ∑ -->
n
=
1
∞ ∞ -->
(
− − -->
1
)
n
x
n
F
n
φ φ -->
6
n
{\displaystyle {\begin{aligned}\sum _{n=1}^{\infty }{\frac {1}{F_{n}}}x^{n}&=\sum _{n=1}^{\infty }{\frac {x^{n}{\sqrt {5}}}{\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{aligned}}}
이웃하는 피보나치 수의 비 이웃하는 피보나치 수의 비 는 황금비 로 수렴한다.
lim
n
→ → -->
∞ ∞ -->
F
n
+
1
F
n
=
φ φ -->
{\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi }
또한, 다음과 같은 부등식 이 성립한다.[ 1] :23
φ φ -->
n
− − -->
1
/
n
5
≤ ≤ -->
F
n
≤ ≤ -->
φ φ -->
n
+
1
/
n
5
{\displaystyle {\frac {\varphi ^{n-1/n}}{\sqrt {5}}}\leq F_{n}\leq {\frac {\varphi ^{n+1/n}}{\sqrt {5}}}}
피보나치 수열은 서로 인접한 항끼리 서로소 이다. 이는 귀납법 으로 간단히 증명할 수 있다.
0번째 항부터 시작할 경우를 파이썬 코드로 구현하면 아래와 같다.
def fib ( n ):
if n == 0 or n == 1 :
return n
return fib ( n - 2 ) + fib ( n - 1 )
위 코드는 메모이제이션을 통해 성능을 개선할 수 있다.
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 ]
![{\displaystyle \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}]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3501f10b4cf5a271b7444dfc12dc8c94a915f37)
