피보나치 수열

수학에서 피보나치 수열(Fibonacci sequence)은 각각의 수가 앞의 두 수를 합한 수열입니다.Fibonacci 수열의 일부인 숫자는 일반적으로 F로 표시되는_n Fibonacci 수열로 알려져 있습니다. 이 수열은 일반적으로 0과 1부터 시작하지만, 일부 저자들은 1과 1부터 시작하거나 때로는 (Fibonacci와 마찬가지로) 1과 2부터 시작합니다.0과 1부터 시작하는 시퀀스의 첫 몇 가지 값은 ^[1]다음과 같습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

피보나치 수는 기원전 200년경 핑갈라가 두 길이의 음절로 형성된 산스크리트 시의 가능한 패턴을 열거하는 작업에서 인도 ^[2][3][4]수학에서 처음 기술되었습니다.피보나치라고도 알려진 피사의 이탈리아 수학자 레오나르도의 이름을 따서 지어졌습니다. 피보나치는 그의 1202년 저서 Liber Abaci에서 ^[5]서유럽 수학에 순서를 소개했습니다.

피보나치 수는 수학에서 예상치 못하게 자주 등장하기 때문에 그들의 연구에 전념하는 전체 저널인 피보나치 분기가 있습니다.피보나치 번호의 응용에는 피보나치 검색 기술과 피보나치 힙 데이터 구조와 같은 컴퓨터 알고리즘과 병렬 시스템과 분산 시스템을 상호 연결하는 데 사용되는 피보나치 큐브라고 불리는 그래프가 포함됩니다.나무의 가지치기, 줄기의 잎 배열, 파인애플의 열매 싹, 아티초크의 개화, 솔방울의 꽃차례와 같은 생물학적 환경에서도 나타나지만, 모든 종에서 발생하는 것은 아닙니다.

피보나치 수는 황금 비율과도 밀접한 관련이 있습니다.비네의 공식은 n번째 피보나치 수를 n과 황금 비율로 표현하며, n이 증가함에 따라 연속된 두 개의 피보나치 수의 비율이 황금 비율로 경향이 있음을 암시합니다.피보나치 수는 동일한 재발 관계에 따르고 피보나치 수와 상보적인 루카스 수열 쌍을 형성하는 루카스 수와도 밀접한 관련이 있습니다.

정의.

피보나치 수는 재발^[6] 관계에 의해 정의될 수 있습니다.

그리고.n > 1의 경우

일부 이전 정의에서는 ${\displaystyle F_{}}$ 0 = ${\displaystyle 0}${\$displaystyle$ F_${0$}=$0}$ $값$이 생략되므로 시퀀스가 F ${\displaystyle 1_{}}$ = ${\displaystyle F_{}}$ 2 = ${\displaystyle 1,}${\$displaystyle F_{1$}=$F_{2$}=$1,}$로 시작하고 반복 F ${\displaystyle n_{}}$ = ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$- ${\displaystyle 1_{}{}_{}}$+ ${\displaystyle F_{}}$ n${\displaystyle {}_{}}$- ${\displaystyle 2_{}}${\$displaystyle$ F_${n$}=$F_{n-1}+F_{n-2}$ 값이 n > 2에 유효합니다.

첫 20 피보나치 수는_n 다음과 같습니다.^[1]

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

역사

인디아

피보나치 수열은 산스크리트어 운율과 관련하여 ^[3][9][10]인도 수학에 등장합니다.산스크리트어의 시적 전통에서는, 1 단위 길이의 짧은 (S) 음절과 병치되어 2 단위 길이의 긴 (L) 음절의 모든 패턴을 열거하는 것에 관심이 있었습니다.주어진 총 지속 시간으로 연속적인 L과 S의 다른 패턴을 세는 것은 피보나치 수가 됩니다: 지속 시간 단위의 패턴 수는 ^[4]F입니다_m+1.

피보나치 수열에 대한 지식은 일찍이 핑갈라(c.기원전 450년–기원전 200년)로 표현되었습니다.싱은 핑갈라의 암호 공식 미스라우차("둘은 혼합되어 있다")와 이를 맥락적으로 해석하는 학자들을 인용하여, 패턴의 ^[11]수는_m+1 F_m 사례에 하나 [S]를_m−1 더하고 F 사례에 하나 [L]을 추가함으로써 얻을 수 있다고 말합니다.바라타 무니는 또한 Natya Shastra (c. 100 BC–c. 350 AD)^[12][2]에서 순서에 대한 지식을 표현합니다.그러나 순서에 대한 가장 명확한 설명은 자신의 작품이 소실된 Virahanka(서기 700년경)의 작품에서 일어나지만, Gopala(서기 1135년경)^[10]의 인용문에서 확인할 수 있습니다.

두 개의 초기 미터의 변화[변동]...예를 들어, [1미터 길이] 4의 경우, 2미터와 3미터가 혼합된 경우, 5미터가 발생합니다.[예 8, 13, 21]...이러한 방식으로 모든 matrā-vṛtas [prosodic combines]에서 프로세스를 따라야 합니다.

헤마찬드라 (c. 1150)는 "마지막과 마지막 앞의 숫자의 합은 다음 마트라-베타의 ^[14][15]숫자이다"라고 쓰면서,^[2] 서열에 대한 지식도 인정받고 있습니다.

유럽

피보나치 수열은 피보나치의^[16][17] 저서 Liber Abaci(계산의 책, 1202)에 처음 등장하며, 여기서 토끼 ^[18][19]개체군의 성장을 계산하는 데 사용됩니다.피보나치는 이상화된(생물학적으로 비현실적인) 토끼 개체수의 증가를 고려합니다. 새로 태어난 번식용 토끼 한 쌍이 들판에 놓여지고, 각각의 번식용 토끼는 한 달의 나이에 짝짓기를 하고, 두 번째 달이 끝날 때마다 항상 다른 토끼 한 쌍을 낳습니다. 그리고 토끼는 절대 죽지 않습니다.하지만 영원히 번식을 계속합니다.피보나치는 퍼즐을 맞추었습니다: 1년에 몇 쌍이 있을까요?

• 첫 달 말에는 짝짓기를 하지만 아직 한 쌍밖에 없습니다.
• 두 번째 달 말에는 새 쌍이 생성되므로 필드에는 두 쌍이 있습니다.
• 세 번째 달 말에 원래 짝은 두 번째 짝을 낳지만, 두 번째 짝은 한 달 동안만 짝짓기를 하기 때문에 모두 세 쌍이 됩니다.
• 네 번째 달 말, 원래의 한 쌍은 또 다른 새로운 한 쌍을 만들어 냈고, 두 달 전에 태어난 한 쌍도 다섯 쌍을 만들어 첫 번째 한 쌍을 만들어냈습니다.

n달 말에 토끼의 쌍 수는 지난달(n~1달)에 살아있는 쌍의 수를 더한 성숙한 쌍(즉, n~2달의 쌍 수)과 같습니다.n번째 달의 숫자는 n번째 피보나치 ^[20]숫자입니다.

"피보나치 수열"이라는 이름은 19세기 숫자 이론가 에두아르 루카스(^[21]Edouard Lucas)에 의해 처음 사용되었습니다.

황금비율과의 관계

닫힌형태식

상수 계수를 갖는 선형 반복에 의해 정의되는 모든 시퀀스와 마찬가지로, 피보나치 수는 닫힌 형태의 표현식을 갖습니다.프랑스 수학자 자크 필리프 마리 비네의 이름을 딴 비네의 공식으로 알려지게 되었지만, 아브라함 드 모이브르와 다니엘 ^[22]베르누이에 의해 이미 알려져 있었습니다.

어디에

는 황금 비율이고, π는 그 ^[23]켤레입니다.

ψ =$$-${\displaystyle }$φ${\displaystyle {}^{}}$- 1 ${\displaystyle \display$=-\$varphi ^{-1$이므로, 이 공식은 다음과 같이 쓸 수도 있습니다.

수열과 이 상수들 사이의 관계를 보려면, φ와 ψ는 둘 다 $방정식$ x $2^{}$ =$x$ + $1$ ${\textstyle$ x$^{2$}= $x+1}$의 해이므로,$$φ와$$ψ의 거듭제곱이 피보나치 재귀를 만족합니다.즉,

임의의 값 a 및 b에 대하여 다음과 같이 정의되는 수열이 있습니다.

동일한 재발을 만족시킬 수 있습니다

U = 0이고 U = 1이 되도록 a와 b를 선택한 경우 결과 시퀀스 U가 Fibonacci 시퀀스여야 합니다.이는 a와 b가 방정식 체계를 만족시켜야 하는 것과 같습니다.

해결책이 있는.

필요한 공식을 생성합니다.

시작 값₀ U와₁ U를 임의 상수로 하면 보다 일반적인 해는 다음과 같습니다.

어디에

반올림에 의한 연산

ψ $n$ <1 ${\textstyle \left {\frac {\psi ^{n}}{\sqrt {5}}\right <{\frac {1}{2}}}$이므로 숫자 F는 φ n ${\displaystyle \frac{{}^{}}{}}$ ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5$에 가장 가까운 정수입니다.따라서 가장 가까운 정수 함수를 사용하여 반올림하면 알 수 있습니다.

실제로 반올림 오차는 n≥4인 경우 0.1보다 작으며 n≥8인 경우 0.01보다 작습니다.이 공식은 피보나치 수 F의 지수를 찾기 위해 쉽게 반전됩니다.

대신 floor 함수를 사용하면 F보다 크지 않은 Fibonacci 숫자의 가장 큰 인덱스를 얻을 수 있습니다.

${\displaystyle {\mathrm{여기}}_{}}$서 log φ (${\displaystyle x}$) = ln ⁡ (${\displaystyle }$x${\displaystyle }$) / ${\displaystyle \ln }$ ⁡ (${\displaystyle }$φ ) = ${\displaystyle {\log }_{}}$ 10 ⁡ (${\displaystyle x}$) / ${\displaystyle {\log }_{}}$ 10 ⁡ (${\displaystyle }$φ )$${\$displaystyle \log$ _${\varphi }(x$) =\$ln(x)/\ln(\varphi$ ) =\$log _{$10$}(x$)/\${\displaystyle \log }$$_${10}(\varphi$$)}, ${\displaystyle \ln }$⁡ (φ ) = 0.${\displaystyle 481211}$… ${\displaystyle \ln$(\$varphi$ ) = 0.$481211\$ldots$$}, ${\displaystyle {\log }_{}}$ 10${\displaystyle }$⁡${\displaystyle }$(φ ) = 0.179987$$… ${\displaystyle$ \$log _${10}(\$varphi$ ) =$$0.179987$\ldots$ $\}$

매그니튜드

F는 φ${\displaystyle {}^{}}$n / ${\displaystyle 5}${\$displaystyle \varphi ^{n}/{\sqrt {5$로 점근하므로, F의 자릿수는 ${\displaystyle n_{}}$ ${\displaystyle {\log }_{}}$ 10 ⁡ ≈ φ 0${\displaystyle \mathrm{.}2090}$n {\$displaystyle$n\$log _{10$}\$varphi \approx 0$.2090$\,n$로 점근합니다. 결과적으로, 모든 정수 d > 1에 대하여 d개의 십진수를 가진 4개 또는 5개의 피보나치 수가 있습니다.

더 일반적으로, 기본 b 표현에서 F의 ${\displaystyle {\mathrm{자릿수}}_{}}$는 ${\displaystyle n_{}}$ log b${\displaystyle {}_{}}$φ ⁡ φ ⁡ n log ⁡ log φ ${\displaystyle \frac{\log }{}}$ . $b$로 점근적입니다$.$ {\$displaystyle$n\$log _{$b}\$varphi$=${\frac {n\log$ \varphi$}{\log$ b$}}$

연속계수한계

요하네스 케플러는 연속적인 피보나치 수들의 비율이 수렴하는 것을 관찰했습니다.그는 "5가 8 대 8이므로 실질적으로 8 대 13이고, 8이 13이므로 13 대 21은 거의 마찬가지"라고 썼고, 이 비율들이 $황금$ 비율${\displaystyle }$φ에 가깝다고 결론지었습니다:$${\$displaystyle \varphi \colon }$

${\displaystyle U_{}}$ 1 = - ${\displaystyle U_{}}$${\displaystyle 0_{}}$ /$$φ {\$displaystyle$ U_${0}}/$ U $1$ ${\displaystyle U_{1$}}이$($가) 아니면 $시작$ 값 U ${\displaystyle 0_{}}${\displaystyle U_${1$} = $-U_{0}/\varphi$ $\}$에 관계없이 수렴이 유지됩니다. 이는 Binet 공식을 사용하여 확인할 수 있습니다.예를 들어, 초기값 3과 2는 수열 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ...를 생성합니다. 이 수열의 연속된 항들의 비율은 황금 비율을 향한 동일한 수렴을 보여줍니다.

${\displaystyle \underset{}{일반적}}$으로 ${\displaystyle \underset{}{lim}}$ → ∞ ${\displaystyle \frac{{Fn}_{}}{}}$ ${\displaystyle \frac{{+}_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{{Fn}_{}}{}}$ = φ m$${\$display$style \$lim$ _${n\to \infty}{\frac {F_{n+m}}{$$F_{n}}}=\varphi$^{$m$ 연속된 Fibonacci 숫자 $사이$의 비율이$$$φ$${\displaystyle$ \varphi$\}$에 가깝기 때문입니다.

권력분립

황금비율은 다음 식을 만족하기 때문에

이 표현식은 하위 파워의 선형 함수로서 상위 파워 ∈$$ ${\$$displaystyle$ \$varphi$^{$n$$}$을(를) 분해하는 데 사용할 수 있으며, 이는 $∈$ {\$displaystyle$ \varphi $}$ 및$$ 1의 선형 조합으로 분해될 수 있습니다.결과적인 재발 관계는 선형 계수로서 피보나치 수를 산출합니다.

이 방정식은 n ≥ 1에 대한 귀납법으로 증명할 수 있습니다.ψ =${\displaystyle {}^{}}$- ${\displaystyle 1}$ /${\displaystyle }$φ ${\displaystyle$\displaystyle \display=-$1/\varphi$}에$$대하여 ψ $2$ = ψ${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle$\display$^{2$}=\display $+1}$인 경우도 있고,

이러한 표현식은 ${\displaystyle {Fn}_{}}$= Fn${\displaystyle {}_{}}$+ ${\displaystyle 2_{}}$- ${\displaystyle {Fn}_{}}$ ${\displaystyle {+}_{}}$ $.$ {\displaystyle $F_{n$}=$F_{n+2}-F_{n+1}$을(를) 사용하여 Fibonacci 시퀀스 F를 음의 정수로 확장하는 경우 n < 1에도 해당됩니다.

신분증

비네의 공식은 5 ${\displaystyle {x\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$+ ${\displaystyle 4}${\$displaystyle 5x^{2}+4}$ 또는$$ ${\displaystyle {}^{}}$ x ${\displaystyle {2\mathrm{}}^{}}$ -${\displaystyle {}^{}4}${\$displaystyle 5x^{2}-4}$ 중$$ 적어도 $하나$가 완벽한 ^[29]정사각형인 경우에만 양의 정수 x가 피보나치 수임을 증명합니다.F ${\displaystyle n_{}}$ = ( φ${\displaystyle {}^{}}$n${\displaystyle }$-${\displaystyle }$( - 1${\displaystyle {}^{}}$) ${\displaystyle n^{}{}^{}}$φ -${\displaystyle {}^{}}$n${\displaystyle }$) / ${\displaystyle 5}${\$displaystyle F_{n$}=(\$varphi ^{n}-(-1)^{n})\varphi ^{-n})/{\sqrt${$5$$\}\},$ 5 φ n ${\displaystyle${\$sqrt {5}},\varphi ^{n$}}를 곱하면 2차 공식을 ${\displaystyle {통해}^{}}$φ n${\displaystyle$ \varphi$^{n$}에서 2차 방정식으로 풀 수 있기 때문입니다.

이를 φ n = ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$φ + ${\displaystyle {\mathrm{n}}_{}}$ - 1 = ( ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ 5${\displaystyle }$+ ${\displaystyle n_{}}$ + ${\displaystyle 2}$ ${\displaystyle F_{}}$n -${\displaystyle 1_{}}$) / ${\displaystyle 2}${\$displaystyle \varphi ^{n$} =$F_{n}\varphi +F_{n-1$} = ($F_{n}$ {\$sqrt {5}}+F_{n}+2F_{n-1$와 비교하면 다음과 같습니다.

$${\displaystyle 5{F_{n}}^{2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2}\.}$$

특히 왼쪽은 완벽한 사각형입니다.

매트릭스 형태

피보나치 수열을 설명하는 2차원 선형 차분 방정식 체계는

대체적으로 표시되는

F → ${\displaystyle n_{}}$ = ${\displaystyle {}^{}}$ F → ${\displaystyle 0_{}}${\$displaystyle${\$vec {F}_{n}$=$\mathbf {A}^{n}{\vec {F}_{0$가 됩니다.행렬 A의 고유값은 각각의 고유벡터에 해당하는 φ = ${\displaystyle 1}$ ${\displaystyle \frac{2}{}}$(${\displaystyle 1}$+ ${\displaystyle 5)}${\$displaystyle \varphi$ = {\$frac {1}{2}}(1+{\sqrt {5})},$ ψ = -${\displaystyle {}^{}}$φ - ${\displaystyle 1^{}}$ = ${\displaystyle 1}$ ${\displaystyle \frac{2}{}}$(${\displaystyle 1}$- ${\displaystyle 5)}${\$displaystyle$\displaystyle \display=-\$varphi ^{-1$}= {\$frac {1}{2}}(1-{\sqrt {5}})}$입니다.

그리고.초기값 그대로n번째 항은 다음과 같습니다.이로부터, 피보나치 급수의 n번째 원소는 닫힌 형태의 식으로 직접 읽어낼 수 있습니다.

동등하게, 동일한 계산은 A의 고유한 분해를 사용하여 대각화함으로써 수행될 수 있습니다.

여기서 λ = ( φ φ - ){\$displaystyle \Lambda$ = {\display${pmatrix}\varphi &0\0&-\varphi$^{-$1}\end{pmatrix}}$와 = ( φ-φ - ).${\displaystyle$ S = {\$begin{pmatrix}\varphi &-\varphi ^{-1}\1&1\end{pmatrix}}.$$}$따라서 피보나치 급수의 n번째 원소에 대한 닫힌 형태식은 다음과 같이 주어집니다.

다시 한 번 양보할 것입니다.

행렬 A는 -1의 행렬식을 가지므로 2×2 단위 행렬입니다.

이 속성은 황금 비율에 대한 연속 분수 표현의 관점에서 이해할 수 있습니다.

피보나치 수는 π에 대한 연속 분수의 연속적인 수렴의 비율로 발생하며, 연속 분수의 연속적인 수렴으로부터 형성된 행렬은 +1 또는 -1의 행렬식을 갖습니다.행렬 표현은 피보나치 수에 대해 다음과 같은 닫힌 형태 표현을 제공합니다.

주어진 n에 대해 이 행렬은 제곱법에 의한 지수화를 사용하여 O(log(n)) 산술 연산으로 계산할 수 있습니다.

이 방정식의 양변의 행렬식을 취하면 카시니의 동일성이 얻어집니다.

또한, 임의의 정방행렬 A에 대하여 AA = A이므로, 다음과 같은 항등식을 유도할 수 있습니다(이들은 행렬 곱의 서로 다른 두 계수로부터 얻어지며, n을 n+1로 바꾸면 첫 번째 계수로부터 두 번째 계수를 쉽게 추론할 수 있습니다).

특히, m = n일 때,

이 마지막 두 개의 항등식은 O(log(n)) 산술 연산에서 피보나치 수를 재귀적으로 계산하는 방법을 제공하며 시간 O(M(n) log(n))에서 여기서 M(n)은 n자리 수의 두 수의 곱에 대한 시간입니다.이것은 폐쇄형 행렬 공식에서 n번째 피보나치 수를 계산하는 시간과 일치하지만, 이미 계산된 피보나치 수를 다시 계산하는 것을 피하면 중복 단계가 더 적습니다(^[30]메모화를 사용한 재귀).

조합 항등식

합법적 증명

${\displaystyle {Fn}_{}}${\$displaystyle$ F_${n}}$을 $합$이${\displaystyle }$n - ${\displaystyle \mathrm{1인}}$ 1과 2의 (공백) 수열의 수(합이 n - 1인$)$ {\$displaystyle n-1$로 해석할 수 있다는 $사실$을 이용하여 피보나치 수와 관련된 대부분의 항등식은 합론을 사용하여 증명할 수 있습니다. 이는 ${\displaystyle {F0}_{}}$ = ${\displaystyle 0}${\$dis$}인 ${\displaystyle {Fn}_{}}${\$displaystyle$ F_${n}$의 정의로 사용할 수 있습니다.$합$이 -1인 그러한 시퀀스가 존재하지 $않음$을 의미하는 playstyle $F_{0}=$0$\}$이고, ${\displaystyle {F1}_{}}$ $=$ ${\displaystyle 1}${\$displaystyle$ F_${1$}$=$$1$이며, 빈 시퀀스가 0으로 "최대"됨을 의미합니다.다음에서${\displaystyle \{...\}}$ $displaystyle {...$$} }$은(는) 집합의 카디널리티입니다.

${\displaystyle F_{0}=0= \{\}}$

${\displaystyle F_{1}=1= \{\}\}}$

${\displaystyle F_{2}=1= \{1\}\}}$

${\displaystyle F_{3}=2= \{\{1,1\},\{2\}\}}$

${\displaystyle F_{4}=3= \{\{1,1,1\},\{1,2\},\{2,1\}\}}$

${\displaystyle F_{5}=5= \{\{1,1,1,1\},\{1,1,2\},\{1,2,1\},\{2,1,1\},\{2,2\}\{2,2}\}}$

이런 식으로 재발 관계.

${\displaystyle {Fn}_{}}$ ${\$ F_${n$$}}$ $시퀀스$를 중복되지 않는 두 세트로 나누어 이해할 수 있습니다. 여기서 모든 시퀀스는 1 또는 2로 시작합니다.첫 번째 요소를 제외한 각 시퀀스의 나머지 $항$은 ${\displaystyle \mathrm{n}}$- 2$${\$displaystyle n-2}$ $또는$ n - 3$${\$displaystyle n-3}$이며, 각 집합의 $카디널리티$는 ${\displaystyle {Fn}_{}}$ ${\displaystyle {-}_{}}$ ${\displaystyle 1_{}{}_{}}${\$displaystyle$ F_${n-1}$ $또는$ ${\displaystyle {Fn}_{}}$- ${\displaystyle 2_{}}$${\$$displaystyle$ F_${n-2}$이며, $이$는 ${\displaystyle {Fn}_{}}$ {\$displaystyle$ $F_{n-1}+F_{n-2}$$개$ 시퀀스와 동일함을 보여줍니다$.$$yle$ F_${n$

비슷한 방법으로 n번째까지의 첫번째 피보나치 수의 합은 (n + 2)번째 피보나치 수에서 1을 ^[31]뺀 것과 같다는 것을 알 수 있습니다.기호:

이는 처음 2의 위치를 기준으로${\displaystyle }$모든 수열을 n + 1 {\$displaystyle$ n$+1}$로 나누면 알 수 있습니다.특히 각 집합은 {${\displaystyle 2},{\displaystyle }$ ${\displaystyle ...\},}${${\displaystyle 1,}$ ${\displaystyle 2,}$ ...}, ${\displaystyle ...,}$ ${\displaystyle \{2,$ ...로 시작하는 시퀀스로 구성됩니다.마지막$$ 두${\displaystyle }$집합${\displaystyle }${{${\displaystyle 1,}$ $1$${\displaystyle ,}$ 1${\displaystyle ,}$ 1, ${\displaystyle 2}$}$$${\displaystyle \},}$ ${\displaystyle \{\{}$$1$, 1${\displaystyle ,}$ 1, ${\displaystyle 2\}}$ }, {{${\displaystyle 1,}$ ${\displaystyle 1,}$1${\displaystyle ,}$ ${\displaystyle 2}$} $},$ {\$displaystyle \{1, 1,$ 1, $2\}\},\{1$, 1, 2\}\},\{$1, 1, 2\}\},$ 각각 카디널리티가$$ 1입니다$.$

이전과 같은 논리에 따라 각 집합의 카디널리티를 합하면 다음을 알 수 있습니다.

${\displaystyle F_{n+2}=F_{n}+F_{n-1}+...+ \{\{1,1,...,1,2\}\} + \{\{1,1,...,1\}\} }$

... 여기서 마지막 두 항은 ${\displaystyle F_{}}$ 1 = ${\displaystyle 1}${\$displaystyle$ F_${1$}=1$\}$의 값을 갖습니다. ${\displaystyle \underset{}{\overset{}{이}}}$로부터$$∑ i = ${\displaystyle 1_{}}$ ${\displaystyle \underset{}{\overset{}{}}}$ F ${\displaystyle {}_{}}$ =${\displaystyle {\mathrm{F}}_{}}$ ${\displaystyle \mathrm{n}{}_{}}$+ 2$$- 1${\displaystyle$ \$sum$ _{$i$=$1}^{n}F_${i$}$=$F_{n+2}-1$이(가) 뒤따릅니다.

비슷한 주장으로, 합을 처음 2개가 아닌 처음 1개의 위치로 묶는 것은 다음 두 가지 항등식을 더 제공합니다.

그리고.즉, 홀수 지수가 ${\displaystyle {\mathrm{F2}}_{}}$n - ${\displaystyle 1_{}}$ ${\$ F_${2n-1}}$인 첫 번째 피보나치 수의 합은 (2n)번째 피보나치 수이며, 지수가 ${\displaystyle {\mathrm{F2}}_{}}$ n ${\$인 첫 번째 피보나치 수의 합은 (2n + 1)번째 피보나치 수에서 ^[32]1을 뺀 값입니다.

다른 속임수를 사용하여 그 사실을 증명할 수도 있습니다.

즉, ${\displaystyle {Fn}_{}}$ ${\$ F_${n}}$까지의 첫 번째 피보나치 수의 제곱의 합은 n번째와 (n + 1)번째 피보나치 수의 곱입니다.이를 보려면 $크기{\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}}$× ${\displaystyle {Fn}_{}}$+ ${\displaystyle 1_{}}${\$displaystyle$ F_${n}\times$ F_${n+1}}$의 Fibonacci 직사각형으로 시작하여 ${\displaystyle {크기}_{}{Fn,}_{}}$ ${\displaystyle {\mathrm{Fn}}_{}}$-${\displaystyle {}_{},}$ ...,$F1$ {\$displaystyle F_{n}, F_${n-1$},$ ..., F_$\{$$1$}; 에서 영역을 비교하여 ID를 따릅니다.

기호법

수열$$(${\displaystyle {Fn}_{}{}_{}}$ n ∈ ${\displaystyle N_{}}$ ${\displaystyle (F_{n})_{n\in \mathbb {N}}}$도 기호 방법을 사용하여 고려합니다.더 정확하게 말하면, 이 수열은 특정한 조합 클래스에 해당합니다.이 수열의 규격은 ${\displaystyle \mathrm{Seq}}$ ⁡ (${\displaystyle \mathcal{}{}^{}}$ +${\displaystyle Z^{}}$ ${\displaystyle 2}$) ${\displaystyle \operatorname$ {$Seq} ({\mathcal {Z+Z^{$2$\}\})\}$입니다. 실제로 위에서 언급한 바와 같이$n$ {\$displaystyle$n} - fibonacci 수는 항 1과 2를 사용하는 n${\displaystyle }$-$$ {\$displaystyle n-1}$의 조합 구성(순서된 파티션)의 수와 같습니다.

이는 피보나치 수열의 통상적인 생성 ${\displaystyle \underset{}{\overset{}{함수}}}$인$$∑ i = ${\displaystyle \underset{}{\overset{}{}}}$∞ ${\displaystyle {Fiz}^{}}$ i${\displaystyle \sum$_{i=$0$}^{\$infty}F_{$i}$z$i}}, 는 ${\displaystyle \frac{유리함수}{}}$ z${\displaystyle \frac{}{}}$1${\displaystyle \frac{}{}}$- ${\displaystyle \frac{{}^{}}{}}$ -${\displaystyle \frac{{}^{}}{}}$z ${\displaystyle \frac{2^{}}{}}$ 입니다$.$ {\$displaystyle${\$frac {z}{1-z-z^{2}}}}$

귀납법

피보나치 상동성은 종종 수학적 귀납법을 사용하여 쉽게 증명될 수 있습니다.

예를 들어, 다시 생각해 보십시오.

양쪽에 ${\displaystyle {Fn}_{}}$+ ${\displaystyle 1_{}}${\$displaystyle$ F_${n+1}}$을 $더하면{\displaystyle {}_{}}$ 효과가 있습니다.

${\displaystyle \sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1}$

따라서 n${\displaystyle }$+ ${\displaystyle 1}${\$displaystyle$ n$+1}$에 $대한{\displaystyle }$ 공식이 있습니다.

마찬가지로, ${\displaystyle {{\mathrm{Fn}}_{}}^{}}$+ ${\displaystyle {{}_{}}^{\mathrm{}}}$2 ${\displaystyle {F_{n$+1$}}^{2$$}$를 양 옆에 $추가$합니다.

주다

바이네 공식 증명

비네 공식은

이것은 피보나치의 정체성을 증명하는 데 사용될 수 있습니다.

예를 들어, ∑ $\underset{}{\overset{}{i}}$ = $\underset{}{\overset{}{1}}$ $\underset{}{\overset{}{}}$ $\underset{}{\overset{}{}}$ $i_{}$ = $n_{}$ + $2_{}$- $1${\$textstyle \sum$ _${i$=$1}^{n}F_{i$}=$F_{n+2}-1}$을$($를) 증명하려면 $왼쪽$에 5 ${\displaystyle${\sqrt {$5}}$을 곱하면 다음과 같습니다.

필요에 따라 φ ψ φ = - $1${\$textstyle \varphi$\lot = $-1}$ 및$$ψ - psi = 5$${\$textstyle \varphi -$\lot = {\$sqrt {5}}$를 사용하여 방정식을 단순화합니다.

기타아이덴티티

다양한 방법을 사용하여 수많은 다른 아이덴티티를 도출할 수 있습니다.그 중 몇 ^[34]가지는 다음과 같습니다.

카시니와 카탈루냐의 정체성

카시니의 신원에 의하면

카탈루냐어의 정체성은 일반화입니다.

도카뉴의 정체

여기서_n L은 n번째 루카스 번호입니다.마지막은 n을 곱하기 위한 아이덴티티입니다. 이 유형의 다른 아이덴티티는카시니의 신원으로 볼 때

이것들은 격자 감소를 사용하여 실험적으로 발견될 수 있으며, 피보나치 수를 인수분해하기 위해 특수한 수 필드 체를 설정하는 데 유용합니다.

좀 더 일반적으로.^[34]

아니면 다른 방법으로

이 공식에 k = 2를 넣으면 위의 절 끝 행렬 형식의 공식을 다시 얻습니다.

함수생성

피보나치 수열의 발생 함수는 멱급수입니다.

이 급수는z < /φ,{\$displaystyle$z < 1$/\varphi,}$를 하는 임의의 $복소수$ z$${\$displaystyle$ z$}$에 대하여 수렴하며, 그 합은 단순한 닫힌 형태를 갖습니다.

이는 ($1$ $-z$ - ${z\mathrm{}}^{}$ 2${}^{}$)$${\$textstyle (1-z-z^{2$을$$곱하여 증명할 수 있습니다.

여기서${\displaystyle \mathrm{정의}}$된 Fibonacci 반복 관계 때문에 k$≥$2 ${\$$displaystyle$k\$geq$ 2$}$에 대해 zk {\$displaystyle$ z^{k$}$를 $포함$하는 모든 항이 취소됩니다.

부분 분율 분해는 다음과 같이 주어집니다.

여기서 φ = $1$ $\frac{2}{}$($1$ $+$ $5$)$${\$textstyle \varphi$ = {\$tfrac {1}{2}}\left(1+{\sqrt {5}}\$right)}는 황금 비율이고 ψ$$= ${\displaystyle \frac{1}{}2}$(${\displaystyle 1}$ -${\displaystyle }$5$)$ {\$displaystyle$ \lot = ${\tfrac {1}{2}}\left(1$ - {\$sqrt {5}\right)}$는 그 켤레입니다.

관련 $함수$ z ↦ -$s$( - $1$/$z$ )$${\$textstyle$ z$\mapsto -s\left( -1/z\right)}$는 네가피보나치 수에 대한 생성 함수이며${\displaystyle ,}$ ${\displaystyle s}$ ( z${\displaystyle )}${\$displaystyle$ s$(z)}$는 함수 방정식을 만족합니다.

z$${\$displaystyle$ z}을(를) 0.01, 0.001, 0$.$0001 등과 $동일$하게 사용하면 s${\displaystyle }$( ) {\$displaystyle$ s$z))$의 십진수 확장에 첫 번째 Fibonacci 숫자가 레이아웃 됩니다. 예를 들어${\displaystyle }s$ (${\displaystyle 0.001)}$ = ${\displaystyle \mathrm{0.001002003008013021..}}$${\displaystyles(0.001)=0.001001002003005008013021....}$

역합

역수 피보나치 수에 대한 무한합은 때때로 세타 함수의 관점에서 평가될 수 있습니다.예를 들어, 모든 홀수 지수 역수 피보나치 수의 합은 다음과 같이 쓸 수 있습니다.

그리고 역수 피보나치 수의 제곱합은 다음과 같습니다.

첫 합에서 각 피보나치 수에 1을 더하면 닫힌 형태도 있습니다.

황금 비율의 역수를 제공하는 제곱 피보나치 수의 중첩 합이 있습니다.

모든 짝수 지수 역수 피보나치 수의^[36] 합은

Lambert $$ 시리즈${\displaystyle }$L (${\displaystyle q}$ ) :${\displaystyle }$= ∑ ${\displaystyle \underset{}{\overset{}{k}}}$ = ${\displaystyle \underset{}{\overset{}{1}}}$ ∞ ${\displaystyle \frac{q^{}}{}}$ ${\displaystyle \frac{{}^{}}{}}$1 - ${\displaystyle \frac{q^{}}{}}$k ,$${\$displaystyle \textstyle$ L$(q)):$$=\sum$ _${k=$${\displaystyle 1}$$}^{\infty}{\frac {q^{k}}{\$frac {q^{k}}{$^{$$k}}},$ 1 ${\displaystyle \frac{{\mathrm{F2}}_{}}{}}$ K${\displaystyle \frac{{}_{}}{}}$$=$${\displaystyle }$5 ($ψ$ ${\displaystyle \frac{2^{}}{}}$ k${\displaystyle \frac{}{{}^{}}}$ - $ψ$ ${\displaystyle \frac{2^{}}{}}$ k${\displaystyle \frac{{}^{}}{}}$- $ψ$$$4 k${\displaystyle \frac{}{{}^{}}}$ - $ψ$ 4${\displaystyle \frac{{}^{}}{}}$k ${\displaystyle ).}$ ${\displaystyle$ \textstyle {\$frac {1}{F_{2k$}}$=${\$sqrt$ {$5}}\left\frac${\$sqrt ^{2k}}{1-\sqrt ^{2k}}{{1-}\right).$

그래서 역수 피보나치 상수는^[37]

게다가, 이 숫자는 Richard André-Jeannin에 ^[38]의해 불합리하다는 것이 증명되었습니다.

밀린의 시리즈는 아이덴티티를^[39] 제공합니다.

N이 무한대로 갈수록 부분합에 대해 닫힌 형태에서 다음과 같이 나옵니다.

소수와 나눗셈

가감속성

시퀀스의 세 번째 개수는 짝수입니다(${\displaystyle F_{}}$ 3 = ${\displaystyle 2}${\$displaystyle$ F_${3$}=$2$의 $배수$). 일반적으로 시퀀스의 모든 k번째 개수는 F의 배수입니다.따라서 피보나치 수열은 분할 가능 수열의 한 예입니다.사실, 피보나치 수열은 더 강한 가분성^[40][41] 특성을 만족합니다.

여기서 gcd는 가장 큰 공약수 함수입니다.

특히, F ${\displaystyle 1_{}}$ = ${\displaystyle 1}${\$displaystyle$ F_${1$}=$1}$과 ${\displaystyle F_{}}$ 2 = ${\displaystyle 1}${\$displaystyle F_{2$}=$1$이므로, 연속된 임의의 피보나치 수는 쌍방향 공분입니다. 즉,

${\displaystyle \gcd(F_{n},F_{n+1})=\gcd(F_{n},F_{n+2})=\gcd(F_{n+1},F_{n+2})=1}$

모든 n에 대하여

모든 소수 p는 모듈로 5의 값에 의해 결정될 수 있는 피보나치 수를 나눕니다.p가 1 또는 4 modulo 5에 해당하면, p는 F를_p−1 나누고, p가 2 또는 3 modulo 5에 해당하면, p는 F를 나눕니다_p+1.나머지 경우는 p = 5이고, 이 경우 p는 F를 나눕니다.

이러한 경우는 Legendre ^[42]기호를 사용하여 하나의 비조각 공식으로 결합할 수 있습니다.

원시성 검정

위 공식은 다음과 같은 의미에서 프라이머리리티 테스트로 사용될 수 있습니다.

레전드르 기호가 자코비 기호로 대체된 경우, 이는 n이 소수라는 증거이며, 만약 그것이 성립하지 않는다면 n은 확실히 소수가 아닙니다.만약 n이 합성이고 공식을 만족한다면, n은 피보나치 의사 소수입니다.m이 크면(예를 들어 500비트 수) 행렬 형태를 사용하여 F(modn)를 효율적으로 계산할_m 수 있습니다.따라서

여기서 행렬 A는^{m [43]}행렬에 적용할 수 있는 모듈러 지수화를 사용하여 계산됩니다.

피보나치 소수

피보나치 소수는 피보나치 소수입니다.처음 몇 가지는 다음과 같습니다.^[44]

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ...

수천 자리 수의 피보나치 소수점이 발견됐지만 무한히 많은 ^[45]수인지는 알 수 없습니다.

F는 F로 나뉠 수 있으므로 F = 3을 제외한 모든 Fibonacci 소수는 소수의 지수를 가져야 합니다.합성수의 임의의 긴 런이 존재하므로 합성 피보나치 수의 임의의 긴 런도 존재합니다.

F = 8보다 큰 피보나치 수는 소수보다 하나 크거나 하나 적은 수가 없습니다.

자명하지 않은 피보나치 수는 ^[47]144입니다.아틸라 페테(Attila Pethő)는 2001년에 피보나치 수가 유한하다는 것을 증명했습니다.2006년에는 Y. Buggeaud, M. Mignotte, S.식섹은 8과 144가 그런 사소하지 않은 완벽한 ^[49]거듭제곱들이라는 것을 증명했습니다.

베른 호갓이 추측하고 뤄밍이 ^[50]증명한 삼각형 피보나치 수는 1, 3, 21, 55가 유일합니다.

어떤 피보나치 수도 완벽한 ^[51]수가 될 수 없습니다.더 일반적으로, 1 이외의 어떤 피보나치 수도 곱셈 ^[52]완벽할 수 없고, 두 피보나치 수의 어떤 비율도 ^[53]완벽할 수 없습니다.

소수점

1, 8, 144(F = F, F, F)를 제외하고 모든 피보나치 수는 더 작은 피보나치 수(카마이클 정리)의 인자가 아닌 소수를 갖습니다.결과적으로 8과 144(F와₆₁₂ F)는 다른 피보나치 ^[55]수의 곱인 유일한 피보나치 수이다.

소수 p에 의한 피보나치 수의 구분은 다음과 같이 평가되는 레전드르$기호$(${\displaystyle \frac{\mathrm{p}}{}}$ 5${\displaystyle )}${\$displaystyle$\left$({\tfrac {p}{5}}\right)}$와 관련이 있습니다.

만약 p가 소수라면,

^[56][57]

예를들면,

다음과 같은 소수 p가 존재하는지는 알 수 없습니다.

그러한 소수점들이 있다면 월-태양-태양 소수점이라고 부를 것입니다.

또한 p ≥ 5가 홀수 소수일 경우:^[58]

예제 1. p = 7, 이 경우 p ≥ 3 (mod 4)이며 다음과 같습니다.

예제 2. p = 11, 이 경우 p ≥ 3 (mod 4)이며 다음과 같습니다.

예제 3. p = 13, 이 경우 p ≥ 1 (mod 4)이며, 다음과 같습니다.

예제 4. p = 29, 이 경우 p ≥ 1 (mod 4)이며, 다음과 같습니다.

홀수 n의 경우, F의 모든_n 홀수 소수는 1 모듈로 4와 일치하며, 이는_n (홀수 소수의 곱으로) F의 모든 홀수 소수가 1 ^[59]모듈로 4와 일치함을 의미합니다.

예를들면,

모든 i < 50000에 대한 Fibonacci 숫자 F(i)의 알려진 모든 인자는 관련 ^[60][61]저장소에서 수집됩니다.

주기성모듈

피보나치 수열의 구성원이 modn을 취하면 결과적인 수열은 최대 6n ^[62]주기로 주기적입니다.다양한 n에 대한 주기의 길이는 소위 피사노 ^[63]주기를 형성합니다.피사노 기간의 일반적인 공식을 결정하는 것은 하위 문제로 모듈 정수의 곱셈 순서 또는 유한장의 원소를 찾는 문제의 특별한 예를 포함하는 미해결 문제입니다.그러나 특정 n에 대해서는 Pisano 주기가 주기 감지의 한 예로 발견될 수 있습니다.

일반화

피보나치 수열은 재발 관계, 특히 선형 차분 방정식에 의해 정의되는 가장 단순하고 초기에 알려진 수열 중 하나입니다.이 모든 시퀀스는 피보나치 시퀀스의 일반화로 볼 수 있습니다.특히, Binet의 공식은 일정한 계수를 갖는 균일한 선형 차분 방정식의 해인 임의의 수열로 일반화될 수 있습니다.

어떤 의미에서 피보나치 수열에 가까운 몇 가지 구체적인 예는 다음과 같습니다.

• 네가피보나치 수를 생성하기 위해 지수를 음의 정수로 일반화하는 것.
• Binet ^[34]공식의 수정을 사용하여 인덱스를 실수로 일반화하는 것.
• 다른 정수부터 시작합니다.루카스 수는 L = 1, L = 3, L = L + L을 갖습니다. 프라임프리 수열은 모든 수가 합성되는 수열을 생성하기 위해 다른 시작점과의 피보나치 재귀를 사용합니다.
• 숫자를 앞의 두 숫자의 (합 이외의) 선형 함수라고 합니다.Pell 수는 P = 2P + P입니다. 앞의 값의 계수에 변수 값 x가 할당되면 결과는 Fibonacci 다항식의 수열입니다.
• 바로 앞에 있는 숫자를 더하지 않습니다.Padovan 수열과 Perrin 수는 P(n) = P(n - 2) + P(n - 3)입니다.
• 3개의 숫자(트리보나치 수), 4개의 숫자(테트라나치 수) 또는 그 이상을 더해 다음 숫자를 생성하는 것.결과적인 시퀀스는 n-Step Fibonacci ^[64]번호로 알려져 있습니다.

적용들

수학

피보나치 수는 파스칼 [65]삼각형의 얕은 대각선에 있는 이항 계수의 합으로 나타납니다.

이는 생성 기능을 확장하면 증명할 수 있습니다.x ${\displaystyle n^{}}$ ${\$ x$^{n$의 용어처럼 수집합니다.

공식이 어떻게 사용되는지 보기 위해, 우리는 존재하는 항의 개수로 합을 배열할 수 있습니다.

5	= 1+1+1+1+1
	= 2+1+1+1	= 1+2+1+1	= 1+1+2+1	= 1+1+1+2
	= 2+2+1	= 2+1+2	= 1+2+2

$({\displaystyle \genfrac{}{}{0ex}{}{50}{}}$) +${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{41}{})}$+ (${\displaystyle \genfrac{}{}{0ex}{}{32}{})}${\$displaystyle${\$binom {5}{0}}+{\binom {4}{1}}+{\binom {3}{2$로서 n-k-1 항에서 k개의 위치를 선택합니다.

이 숫자들은 특정한 열거 ^[66]문제들에 대한 해결책을 제공하며, 그 중 가장 일반적인 것은 주어진 숫자 n을 1과 2의 순서 합(구성이라고 함)으로 쓰는 방법의 수를 세는 것입니다. 이것을 하는 방법에는 F가지가 있습니다_n+1. (동등하게는${\displaystyle }2{\displaystyle \mathrm{}}$ ×$$ {\$displaystyle 2\times$n$$} 직사각형의 도미노 타일링의 수이기도 합니다.)예를 들어, F = F = 한 번에 한 두 계단씩 5계단씩 올라갈 수 있는 8가지 방법이 있습니다.

5	= 1+1+1+1+1	= 2+1+1+1	= 1+2+1+1	= 1+1+2+1	= 2+2+1
	= 1+1+1+2	= 2+1+2	= 1+2+2

그림에 따르면 8개는 5개(4계단을 오르는 방법의 수, 그 다음에 1단계)와 3개(3계단을 오르는 방법의 수, 그 다음에 2단계)로 분해할 수 있습니다.동일한 추론은 한 단계까지 재귀적으로 적용되며, 그 중 한 단계만 올라갈 수 있습니다.

피보나치 수는 이진 문자열 집합 중에서 다른 방법으로 찾을 수 있고, 주어진 집합의 부분 집합 중에서 동등하게 찾을 수 있습니다.

• 연속된 1이 없는 길이 n의 이진 문자열의 수는 피보나치 수 F입니다_n+2.예를 들어 길이 4의 16개 이진 문자열 중에서 연속적인 1이 없는 F = 8이 있습니다. 즉, 0000, 0001, 0010, 0100, 0101, 1000, 1001 및 1010입니다.이러한 문자열은 Fibinary 숫자의 이진법 표현입니다.이와 동등하게, F는 연속 정수가 없는 {1, ..., n}의 부분 집합 S의 수, 즉 모든 i에 대해 {i, i + 1} ⊈ S인 S입니다.합이 n+1인 사영은 1을 0으로 바꾸고 2를 10으로 바꾼 후 마지막 0을 떨어뜨리는 것입니다.
• 연속된 1의 홀수가 없는 길이 n의 이진 문자열의 수는 피보나치 수 F입니다_n+1.예를 들어, 길이 4의 16개의 이진 문자열 중에서 연속되는 1의 홀수가 없는 F = 5가 있는데, 이는 0000, 0011, 0110, 1100, 1111입니다.이와 동일하게, 홀수의 연속 정수가 없는 {1, ..., n}의 부분 집합 S의 수는 F입니다_n+1.합계가 n인 사영은 1을 0으로, 2를 11로 치환하는 것입니다.
• 연속되는 0 또는 1의 짝수 개수가 없는 길이 n의 이진 문자열의 개수는_n 2F입니다.예를 들어, 길이 4의 16개 이진 문자열 중 연속되는 0 또는 1의 짝수가 없는 2F = 6이 있으며, 이는 0001, 0111, 0101, 1000, 1010, 1110입니다.부분 집합에 대한 동등한 문이 있습니다.
• 유리 마티야세비치는 피보나치 수가 디오판토스 방정식에 의해 정의될 수 있다는 것을 보여줄 수 있었고, 이것은 그가 힐베르트의 ^[67]열 번째 문제를 푸는 것으로 이끌었습니다.
• 피보나치 수 역시 완전한 수열의 한 예입니다.이것은 모든 양의 정수가 피보나치 수의 합으로 쓰여질 수 있다는 것을 의미하며, 여기서 어떤 숫자라도 기껏해야 한 번씩 사용됩니다.
• 또한 모든 양의 정수는 합이 연속적인 2개의 피보나치 수를 포함하지 않는 방식으로 하나 이상의 구별된 피보나치 수의 합으로 고유한 방식으로 기록될 수 있습니다.이를 제켄도르프의 정리라고 하며, 이 조건을 만족시키는 피보나치 수의 합을 제켄도르프 표현이라고 합니다.숫자의 제켄도르프 표현은 피보나치 부호화를 유도하는 데 사용될 수 있습니다.
• 5로 시작하는 매 초 피보나치 수는 다음 공식에서 구한 피타고라스 삼중의 정수변을 가진 직각 삼각형의 빗변의 길이, 즉 피타고라스 삼중의 가장 큰 수
  $${\displaystyle(F_{n}F_{n+3})^{2}+(2F_{n+1}F_{n+2})^{2}={F_{2n+3}}^{2}}.$$

  
  이 공식으로부터 얻어진 피타고라스 삼각형의 수열은 길이 (3,4,5), (5,12,13), (16,30,34), (39,80,89), ...의 변을 갖습니다. 이 각 삼각형의 가운데 변은 앞의 ^[68]삼각형의 세 변의 합입니다.
• 피보나치 큐브는 병렬 컴퓨팅을 위한 네트워크 토폴로지로 제안된 피보나치 수의 노드를 가진 무방향 그래프입니다.
• 피보나치 수는 ^[69]원 패킹 정리와 등각 지도 사이의 연결을 증명하는 데 사용되는 고리 보조정리에 나타납니다.

컴퓨터과학

• 피보나치 수는 두 정수의 최대 공약수를 결정하기 위한 유클리드 알고리즘의 계산 런타임 분석에서 중요합니다. 이 알고리즘에 대한 최악의 경우 입력은 연속적인 피보나치 ^[70]수 쌍입니다.
• 피보나치 수는 정렬되지 않은 목록이 순차적인 피보나치 수에 해당하는 두 개의 목록으로 분할되는 병합 정렬 알고리즘의 다상 버전에서 사용되며, 두 부분의 길이가 대략적인 비율 θ로 되도록 목록을 분할합니다.다상 병합 정렬의 테이프 드라이브 구현은 <컴퓨터 프로그래밍 기술>에 설명되어 있습니다.
• Fibonacci 트리는 하위 트리(재귀적으로)의 높이가 정확히 1만큼 다른 이진 트리입니다.따라서 이는 AVL 트리이며, 주어진 높이에 대해 가장 적은 노드를 가진 것입니다. 즉 "가장 얇은" AVL 트리입니다.이 트리들에는 피보나치 수에서 1을 뺀 여러 정점이 있는데, 이는 AVL ^[71]트리 분석에서 중요한 사실입니다.
• 피보나치 수는 일부 의사 난수 생성기에서 사용됩니다.
• 피보나치 수는 피보나치 힙 데이터 구조의 분석에서 발생합니다.
• 피보나치 탐색 기법이라 불리는 1차원 최적화 방법은 피보나치 ^[72]수를 사용합니다.
• Fibonacci 번호 시리즈는 Amiga 컴퓨터에서 사용되는 IFF 8SVX 오디오 파일 형식의 옵션 손실 압축에 사용됩니다.숫자 시리즈는 μ-law와 ^[73][74]같은 로그 방식과 유사한 원본 오디오 파형을 컴파일합니다.
• 일부 애자일 팀은 포커를 기획할 때 "수정된 피보나치 시리즈"라고 불리는 수정된 시리즈를 추정 도구로 사용합니다.Planning Poker는 Scale Agile ^[75]Framework의 공식적인 부분입니다.
• 피보나치 부호화
• 네가피보나치 부호화

자연.

피보나치 수열은 나무의 가지치기, 줄기의 잎 배열, ^[77]파인애플의 열매, 아티초크의 개화, ^[78]솔방울의 배열, ^[79][80]꿀벌의 가계도와 같은 생물학적 ^[76]환경에서 나타납니다.케플러는 일부 ^[81]꽃들의 (황금 비율과 관련된) 오각형 형태를 설명하기 위해 피보나치 수열이 자연에 존재한다는 것을 지적했습니다.밭 데이지는 대개 피보나치 ^[82]수만큼 꽃잎을 가지고 있습니다.1830년 K. F.스킴퍼와 A.브라운은 식물의 파라스티시(spiral phyllotaxis)가 종종 피보나치 ^[83]수를 포함하는 분수로 표현된다는 것을 발견했습니다.

프셰미스와프 프루신키에비치는 실제 사례가 부분적으로 자유군, 특히 린덴메이어 ^[84]문법에 대한 특정 대수적 제약의 표현으로 이해될 수 있다는 생각을 발전시켰습니다.

1979년 ^[85]헬무트 보겔(Helmut Vogel [de])은 해바라기 머리에 꽃무늬의 모형을 제안했습니다.이것은 형식을 갖습니다.

여기서 n은 플로렛의 인덱스 수이고 c는 일정한 스케일링 인자입니다. 따라서 플로렛은 페르마의 나선형 위에 놓여 있습니다.발산각은 약 137.51°로 황금 비율로 원을 나누는 황금각입니다.이 비율이 비합리적이기 때문에 중심에서 정확히 같은 각도에 인접한 플로트는 없으므로 플로트가 효율적으로 포장됩니다.황금 비율에 대한 합리적 근사치는 F(j)의 형태를 취하기 때문입니다.F( j + 1), 꽃수 n의 가장 가까운 이웃은 중심으로부터의 거리인 r에 의존하는 일부 지수 j에 대한 n ± F(j)에 있는 이웃입니다.해바라기와 유사한 꽃들은 가장 일반적으로 인접한 피보나치 ^[86]수의 양에 따라 시계 방향과 반시계 방향으로 나선형의 꽃을 갖는데,^[87] 일반적으로 가장 바깥쪽 반경으로 계산됩니다.

피보나치 수는 다음 규칙에 따라 이상화된 꿀벌의 혈통에도 나타납니다.

• 만약 알이 짝짓기를 하지 않은 암컷에 의해 낳으면, 수컷이나 드론 벌을 부화시킵니다.
• 하지만, 만약 알이 수컷에 의해 수정된다면, 암컷을 부화시키는 것입니다.

따라서 수컷 벌은 항상 부모가 한 명이고 암컷 벌은 두 명입니다.만약 어떤 수컷 벌(1벌)의 혈통을 추적한다면, 그는 부모 1명(1벌), 조부모 2명, 증조부모 3명, 증조부모 5명 등이 있습니다.부모의 수열은 피보나치 수열입니다.각 등급의 조상의 수 F는_n 여성 조상의 수 F에_n−1 남성 조상의 수 ^[88]F를_n−2 더한 수이다.이것은 각 단계의 조상들이 그렇지 않으면 관련이 없다는 비현실적인 가정 하에 있습니다.

주어진 조상 세대에서 인간 X 염색체 유전 라인의 가능한 조상의 수는 또한 피보나치 ^[89]수열을 따른다는 것이 주목되었습니다.남성은 어머니로부터 받은 X염색체와 아버지로부터 받은 Y염색체를 가지고 있습니다.남성은 자신의 X염색체의 "염색체"(${\displaystyle {F1}_{}}$ = ${\displaystyle 1}${\$displaystyle$ F_${1$}=$1})$로 간주하고, 부모 세대에서 그의 X염색체는 한 부모로부터 왔습니다(${\displaystyle {F2}_{}}$ = ${\displaystyle 1}${\$displaystyle F_{2$}=$1$남자의 어머니는 어머니(아들의 외할머니)로부터 1개의 X염색체를, 아버지(아들의 외할아버지)로부터 1개의 X염색체를 받았으므로, 2명의 조부모가 남자 후손의 X염색체에 기여하였습니다(${\displaystyle {F3}_{}}$ = ${\displaystyle 2}${\$displaystyle$ F_${3$} =$2$외할아버지는 어머니로부터 X염색체를, 외할아버지는 양친으로부터 X염색체를 받았으므로 증조부모 3명이 남자 후손의 X염색체에 기여하였습니다(${\displaystyle {F4}_{}}$ = ${\displaystyle 3}${\$displaystyle$ F_${4$} =$3$5명의 증조부모가 남자 후손의 X염색체(${\displaystyle {F5}_{}}$ = ${\displaystyle 5}${\$displaystyle$ F_${5$} =$5$ 등에 기여했습니다(이는 주어진 후손의 조상이 모두 독립적이라고 가정하지만, 어느 족보라도 충분히 과거로 거슬러 올라가면, 조상들은 족보의 여러 줄에 나타나기 시작하고,최종적으로 인구 창시자가 족보의 모든 선에 나타날 때까지.)

다른.

• 광학에서, 한 줄기의 빛이 굴절률이 다른 서로 다른 물질로 쌓여 있는 두 개의 투명한 판을 통해 일정 각도로 빛날 때, 두 판의 상면, 중간면, 그리고 바닥면의 세 면을 반사할 수 있습니다.k > 1의 k 반사를 갖는 다양한 빔 경로의 수는 k ${\displaystyle$ k$}$ 피보나치 수이다.(단, k = 1일 때, 반사 경로는 3개의 표면 각각에 대해 1개씩 2개가 아니라 3개가 있습니다.)
• 피보나치 추적 수준은 금융 시장 거래를 위한 기술 분석에 널리 사용됩니다.
• 수 마일에서 수 킬로미터까지의 변환 계수 1.609344가 황금 비율에 가깝기 때문에, 수 마일의 거리를 피보나치 수의 합으로 분해하는 것은 피보나치 수가 그 계승자로 대체되었을 때 거의 수 킬로미터의 합이 됩니다.이 방법은 황금 비율 베이스 δ의 라디칼 2 숫자 레지스터가 이동되는 것에 해당합니다.킬로미터에서 마일로 변환하려면 레지스터를 Fibonacci 시퀀스 아래로 이동합니다.^[91]
• 무한 저항 체인 회로(저항 사다리 또는 무한 직렬 병렬 회로라고도 함)에서 측정된 전압 및 전류 값은 피보나치 수열을 따릅니다.교대 직렬과 병렬 저항을 더한 중간 결과는 연속적인 피보나치 수로 구성된 분수를 산출합니다.전체 회로의 등가 저항은 황금 ^[92]비율과 같습니다.
• Brasch et al. 2012는 일반화된 Fibonacci 시퀀스가 ^[93]경제학 분야와도 어떻게 연결될 수 있는지 보여줍니다.특히, 일반화된 Fibonacci 시퀀스가 하나의 상태와 하나의 제어 변수로 유한 수평 동적 최적화 문제의 제어 함수에 어떻게 진입하는지 보여줍니다.이 절차는 흔히 브록-미르만 경제 성장 모델이라고 불리는 예에서 설명됩니다.
• 마리오 메르츠(Mario ^[94]Merz)는 1970년부터 자신의 작품 중 일부에 피보나치 시퀀스(Fibonacci sequence)를 포함시켰습니다.
• Joseph Schillinger (1895–1943)는 일부 멜로디에서 피보나치 간격을 사용하는 작곡 체계를 개발했습니다; 그는 이것들을 자연 ^[95]안에서 명백하게 나타나는 정교한 조화에 대한 음악적인 대응물로 여겼습니다.황금비율 § 음악도 참고하세요.

참고 항목

• 피보나치 협회 – 피보나치 번호 연구 기구
• 대중문화의 피보나치 수
• Fibonacci word – Fibonacci 재발의 이진 시퀀스
• 무작위 피보나치 수열 – 피보나치 수열에 기초한 무작위화된 수학적 수열
• Withoff 배열 – Fibonacci 수열에서 파생된 정수의 무한 행렬

참고문헌

해설각주

인용문

인용작품

• Ball, Keith M (2003), "8: Fibonacci's Rabbits Revisited", Strange Curves, Counting Rabbits, and Other Mathematical Explorations, Princeton, NJ: Princeton University Press, ISBN 978-0-691-11321-0.
• Beck, Matthias; Geoghegan, Ross (2010), The Art of Proof: Basic Training for Deeper Mathematics, New York: Springer, ISBN 978-1-4419-7022-0.
• Bóna, Miklós (2011), A Walk Through Combinatorics (3rd ed.), New Jersey: World Scientific, ISBN 978-981-4335-23-2.
• Borwein, Jonathan M.; Borwein, Peter B. (July 1998), Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, Wiley, pp. 91–101, ISBN 978-0-471-31515-5
• Lemmermeyer, Franz (2000), Reciprocity Laws: From Euler to Eisenstein, Springer Monographs in Mathematics, New York: Springer, ISBN 978-3-540-66957-9.
• Livio, Mario (2003) [2002], The Golden Ratio: The Story of Phi, the World's Most Astonishing Number (First trade paperback ed.), New York City: Broadway Books, ISBN 0-7679-0816-3
• Lucas, Édouard (1891), Théorie des nombres (in French), vol. 1, Paris: Gauthier-Villars.
• Sigler, L. E. (2002), Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation, Sources and Studies in the History of Mathematics and Physical Sciences, Springer, ISBN 978-0-387-95419-6

외부 링크

• 해바라기와 피보나치 - 유튜브의 숫자 파일
• 수학 페이지에서 Fibonacci Sequences Modm의 주기
• 과학자들은 자연에서 피보나 나선의 형성의 실마리를 발견합니다.
• 피보나치의 BBC 우리 시간 순서
• "Fibonacci numbers", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• OEIS 시퀀스 A000045 (Fibonacci 번호)