피보나치 수열이 기하 급수적으로 빠르게 증가한다는 것을 증명하기위한 유도 [중복]
유도를 사용하여 이것을 해결하는 방법은 무엇입니까?
귀납법을 사용하여
$F_n\ge2^{\frac n2}\;,\;$ ...에 대한 $n\ge6\;.$
$F_0=0\;,\;F_1=1\;,\;F_n=F_{n-1}+F_{n-2}\;.$
답변
유도 문제에는 세 단계가 있습니다.
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}}$$
$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\;.$