피보나치 수열이 기하 급수적으로 빠르게 증가한다는 것을 증명하기위한 유도 [중복]

Nov 27 2020

유도를 사용하여 이것을 해결하는 방법은 무엇입니까?

귀납법을 사용하여

$F_n\ge2^{\frac n2}\;,\;$ ...에 대한 $n\ge6\;.$

$F_0=0\;,\;F_1=1\;,\;F_n=F_{n-1}+F_{n-2}\;.$

답변

RhysHughes Nov 27 2020 at 22:29

유도 문제에는 세 단계가 있습니다.

1 단계, 기본 사례를 증명합니다. 이 경우, 먼저 보여 것을$F(n)\geq 2^\frac n2$ 언제 $n=6$ (즉 $F(6)\geq 2^3=8$). 운동$F(6)$여기에 충분합니다. 재귀 적 정의는 두 가지 이전 사례 ($F(n)=F(n-1)+F(n-2)$, RHS에는 두 가지 용어가 있습니다), 두 번째 기본 사례도 필요합니다. 다음 사례도 필요합니다. $n=7$, 그래서 그것을 보여주십시오 $F(7)\geq 2^\frac 72$ (힌트 : 대략적인 수치를 찾으려면이 숫자를 제곱하십시오)

2 단계, 속성이 주어진 $k,k+1$. 즉, 가정$F(k)\geq 2^\frac k2, F(k+1)\geq 2^{\frac{k+1}{2}}\tag1$

3 단계 : 다음 케이스에 대한 진술이 유효 함을 증명하기 위해 이것을 사용합니다. $(1)$ 그것을 의미 $$F(k+2)=F(k+1)+F(k)\geq 2^{\frac{k+2}{2}}$$

Angelo Nov 27 2020 at 22:37

$F_6=8\ge2^{\frac62}\;.$

$F_7=13\ge\sqrt{2^7}=2^{\frac72}\;.$

이제 $\;n\ge8\;,$ 우리는 $\;F_{n-2}\ge2^\frac{n-2}{2},\;F_{n-1}\ge2^\frac{n-1}{2}$ 그리고 그것을 증명 $\;F_n\ge2^\frac n2.$

$F_n=F_{n-1}+F_{n-2}\ge2^{\frac{n-1}{2}}+2^{\frac{n-2}{2}}=2^{\frac{n-2}{2}}\big(\sqrt 2+1\big)\ge$

$\ge2^{\frac n2-1}\cdot 2=2^{\frac n2}.$

따라서, $n$, 그것은 다음과 같습니다

$F_n\ge2^\frac n2\quad$ 모든 $\;n\ge6\;.$