Matematické Fórum

pizet · 15. 01. 2011 09:39

Ako toto dokázať indukciou?
$F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_{n}$ , pre $n = 0,1,2,\dots$ .
Dokážte, že pre každé $n\geq 0$ platí
$F_n\leq (\frac{1+\sqrt{5}}{2})^{n-1}$
Prvý krok je jasný ale neviem potom ako sa pohnúť. Keby ste mi len trocha poradili, netreba nutne vyriešiť, bol by som rád. Ďakujem.

FailED · 15. 01. 2011 11:36

↑ pizet:

Předpokládej, že to platí pro všechna m<n+2 (budeš potřebovat n a n+1) a dokaž, že potom to platí i pro n+2.

pizet · 15. 01. 2011 12:53

↑ FailED: Dík za radu, podobne som skúšal ale asi až teraz mi doplo. Mohl by vlastne celý dôkaz vyzerať nejak takto (ako uvádzam ďalej)? Trocha som matematickú indukciu modifikoval ale to je hádam ok.

1. Overíme vzťah pre n = 0 a pre n = 1.

$F_0\leq\frac{2}{1+\sqrt{5}}\nl F_1\leq 1$

2. Predpokladajme, že platí $F_n\leq ((1+\sqrt{5})/2)^{n-1}$ a $F_{n+1}\leq ((1+\sqrt{5})/2)^{n}$ . Dokážeme, že platí aj
$F_{n+2}\leq (\frac{1+\sqrt{5}}{2})^{n+1}$ , čiže
$F_{n} + F_{n+1}\leq (\frac{1+\sqrt{5}}{2})^{n+1}$ .

Podľa predpokladu

$(\frac{1+\sqrt{5}}{2})^{n-1} + (\frac{1+\sqrt{5}}{2})^{n}\leq (\frac{1+\sqrt{5}}{2})^{n+1}\nl \frac{1+\sqrt{5}}{2})^{n-1}(1+\frac{1+\sqrt{5}}{2})\leq \frac{1+\sqrt{5}}{2})^{n+1}\nl 1+\frac{1+\sqrt{5}}{2}\leq (\frac{1+\sqrt{5}}{2})^{2}\nl 1+\frac{1+\sqrt{5}}{2}\leq \frac{1+2\sqrt{5} + 5}{4}\nl 4 + 2 + 2\sqrt{5}\leq 1 + 2\sqrt{5} + 5\nl 6\leq 6$

$6\leq 6$ je pravdivý výrok, teda platí aj $F_{n+2}\leq (\frac{1+\sqrt{5}}{2})^{n+1}$ . QED.

Myslím, že by to takto mohlo fungovať, keď n = 0, n+1 = 1, tak platí aj pre n+2 = 2, keď n = 1 a n+1 = 2, platí aj pre n+2 = 3, atď.

FailED · 15. 01. 2011 13:17

↑ pizet:

Přesně tak, šlo by ještě zdůraznit, jak použijeme ten předpoklad, tedy

$F_{n+2}=F_{n} + F_{n+1}\le $\frac{1+\sqrt{5}}{2}$^{n-1} + $\frac{1+\sqrt{5}}{2}$^{n}\le $\frac{1+\sqrt{5}}{2}$^{n+1}$

ale to už jsou detaily a myslím že je to dost jasné.

pizet · 15. 01. 2011 13:24

↑ FailED: Ďakujem ti. Vyriešené.

Matematické Fórum

#1 15. 01. 2011 09:39

Matematiká indukcia

#2 15. 01. 2011 11:36

Re: Matematiká indukcia

#3 15. 01. 2011 12:53

Re: Matematiká indukcia

#4 15. 01. 2011 13:17

Re: Matematiká indukcia

#5 15. 01. 2011 13:24

Re: Matematiká indukcia

Zápatí