Matematické Fórum

jirinaK · 20. 10. 2007 13:32

Prosím, nemohu přijít na to, čím začít. Obzvláš? u té dvojky. Nevíte někdo?
1) X, Y množiny, rozhodněte, zda platí (a hlavně dokažte): X=Y "právě tehdy, když" 2^X = 2^Y.

2) Dokažte, že Fibonacciho posloupnost má exponenciální růst. Podle mě teda musí existovat reálné číslo "a" a přirozené n_0 takové, že pro všechna n >=n_0 je a^n <= F_n

Kondr · 20. 10. 2007 13:56

1)
implikace zleva doprava: pokud jsou dvě množiny stejné, mají stejnou množinu podmnožin - zřejmé.
Zprava doleva: Pokud mají dvě množiny stejnou množinu podmnožin, mají i stejnou množinu jednoprvkových podmnožin, mají proto stejné prvky, takže jsou shodné.

2)PrvkyFibonacciho posloupnosti rostou stejně rychle, jako posloupnostn a_n=z^n, kde
z=1,618... je zlatý řez; kořen rovnice x^2=x+1 (této rovnsti později využijeme při dosazování za z+1=z^2).
Pro něj platí,že z^{n-2} <= F_n, což pro exponenciální růst stačí.
Naše tvrzení dokážeme indukcí:
-základní (bázový krok):
$F_3=2>z^1$
$F_4=3>z^2$
-indukční krok: ukazujeme, že pokud pro n<k platí $z^{n-2} \leq F_n$ , platí i $z^{k-2} \leq F_k$ .
Z definice
$F_k=F_{k-1}+F_{k-2}>z^{k-3}+z^{k-4}=(z+1)z^{k-4}=z^2z^{k-4}=z^{k-2}$ ,
což jsme chtěli dokázat.

Matematické Fórum

#1 20. 10. 2007 13:32

Množiny, ibonacciho posloupnoust

#2 20. 10. 2007 13:56

Re: Množiny, ibonacciho posloupnoust

Zápatí