수학 에서 피보나치 수 (영어 : 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 ) 일반항 피보나치 수의 일반항 은 다음과 같다.: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}}} 는 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 )이라고 한다.: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}} 다음과 같은 항등식이 성립한다.:20
φ n = F n φ + F n − 1 {\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}} 피보나치 수를 점화식을 통해 음의 정수 에까지 확장할 수 있다. 이 경우, 비네 공식이 여전히 성립하며, 또한 다음이 성립한다.:37, (1.40)
F − n = ( − 1 ) n + 1 F n {\displaystyle F_{-n}=(-1)^{n+1}F_{n}} 급수 공식 처음 몇 피보나치 수의 합,:5, (1.1) 교대합,:6, (1.6) 제곱합,:6, (1.7) 세제곱합: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}}} 처음 몇 피보나치 수의 홀수째,:5, (1.2) 짝수째,:6, (1.3) 3의 배수째: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}}} 피보나치 수의 역수의 합은 수렴하며, 또한 다음 항등식들이 성립한다.: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 종 완전 타원 적분 이다.
생성 함수 피보나치 수의 생성 함수 는 다음과 같다.: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}}}} 피보나치 수의 역수 의 생성 함수 는 다음과 같이 나타낼 수 있다.: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 } 또한, 다음과 같은 부등식 이 성립한다.: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 in memo : return memo [ n ] else : memo [ n ] = fib ( n - 2 ) + fib ( n - 1 ) return memo [ n ] 같이 보기
각주