피보나치 수

수학에서 피보나치 수(영어: 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}$는 다음과 같은 초기값 및 점화식으로 정의되는 수열이다.

$F_{1}=F_{2}=1$

$F_{n}=F_{n-1}+F_{n-2}\qquad (n\in \{3,4,\dots \})$

0번째 항부터 시작할 경우 다음과 같이 정의된다.

$F_{0}=0$

$F_{1}=1$

$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)

일반항

피보나치 수의 일반항은 다음과 같다.^{:19, (1.20)}

$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}}}$

여기서 $\varphi =(1+{\sqrt {5}})/2$는 황금비이며, ${\sqrt {5}}$는 5의 음이 아닌 제곱근이다. 이를 비네 공식(영어: Binet's formula)이라고 한다. 이는 레온하르트 오일러가 1765년 처음 발표했으나 잊혔다가, 1848년 자크 비네에 의해 재발견되었다.

성질

항등식

다음과 같은 항등식이 성립하며, 카시니 항등식(영어: Cassini's identity)이라고 한다.

$F_{n+1}F_{n-1}-{F_{n}}^{2}=(-1)^{n}$

다음과 같은 항등식이 성립하며, 이를 도가뉴 항등식(영어: d'Ocagne's identity)이라고 한다.^{:9, (1.8)}

$F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1}$

다음과 같은 항등식이 성립한다.^:20

$\varphi ^{n}=F_{n}\varphi +F_{n-1}$

피보나치 수를 점화식을 통해 음의 정수에까지 확장할 수 있다. 이 경우, 비네 공식이 여전히 성립하며, 또한 다음이 성립한다.^{:37, (1.40)}

$F_{-n}=(-1)^{n+1}F_{n}$

급수 공식

처음 몇 피보나치 수의 합,^{:5, (1.1)} 교대합,^{:6, (1.6)} 제곱합,^{:6, (1.7)} 세제곱합^:21은 다음과 같다.

$\sum _{k=0}^{n}F_{k}=F_{n+2}-1$

$\sum _{k=0}^{n}(-1)^{k+1}F_{k}=(-1)^{n+1}F_{n-1}+1$

$\sum _{k=0}^{n}F_{k}^{2}=F_{n}F_{n+1}$

$\sum _{k=0}^{n}F_{k}^{3}={\frac {F_{3n+2}+(-1)^{n+1}6F_{n-1}+5}{10}}$

처음 몇 피보나치 수의 홀수째,^{:5, (1.2)} 짝수째,^{:6, (1.3)} 3의 배수째^:21 항의 합은 다음과 같다.

$\sum _{k=1}^{n}F_{2k-1}=F_{2n}$

$\sum _{k=0}^{n}F_{2k}=F_{2n+1}-1$

$\sum _{k=0}^{n}F_{3k}={\frac {F_{3n+2}-1}{2}}$

피보나치 수의 역수의 합은 수렴하며, 또한 다음 항등식들이 성립한다.^{:33, (1.34); 33; 34}

${\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}}$

홀수 위치에서 피보나치 수의 역수의 합은 다음 값을 갖는다:

$\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 종 완전 타원 적분이다.

생성 함수

피보나치 수의 생성 함수는 다음과 같다.^{:28, (1.28)}

$\sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}$

피보나치 수의 역수의 생성 함수는 다음과 같이 나타낼 수 있다.^{:35, (1.36); 35; 36; 36}

${\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\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi$

또한, 다음과 같은 부등식이 성립한다.^:23

${\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]

같이 보기

• 피보나치 수의 일반화
• 엠브리-트레페텐 상수
• 메모이제이션

외부 링크

• “Fibonacci numbers”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Fibonacci number”. 《Wolfram MathWorld》 (영어). Wolfram Research.