Wiadomo, że dla ciagu Fibonacciego \(\displaystyle{ 0, 1, 1, 2, 3, 5, 8, 13, 21}\) iloraz kolejnych wyrazów coraz bardziej zbiega do liczby "golden ration" 1,681.. Natomiast ten iloraz można także wrazić za pomocą wyrazów:
\(\displaystyle{ \frac{1+ \sqrt{5}}{2}}\) oraz \(\displaystyle{ \frac{1 - \sqrt{5}}{2}}\)
I teraz jak wyznaczyć te wyrazy mając dany tylko ciag fibonacciego?
Raczej: \(\displaystyle{ F_{n} = \frac{1}{\sqrt{5}} \left [ \left( \frac{1 +\sqrt{5}}{2}\right)^{n} - \left( \frac{1 -\sqrt{5}}{2}\right)^{n} \right]}\)
Wzór ten to rozwiązanie równania rekurencyjnego, jednorodnego: \(\displaystyle{ a_{n+2}=a_{n+1}+a_n}\)
przy warunkach początkowych \(\displaystyle{ a_1=a_2=1}\)
Sądzę, że Mondo potrafi to policzyć (o ile będzie mu to potrzebne).
Re: Wyznaczenie ilorazu ciagu Fibonacciego
: 26 wrz 2020, o 19:01
autor: janusz47
Jest także ładna metoda algebraiczna wyznaczenia tego równania.
kerajs pisze: 26 wrz 2020, o 18:35
Sądzę, że Mondo potrafi to policzyć (o ile będzie mu to potrzebne).
Tak, ale natknałem się na jedną niejasność - kiedy wyróżnik równania charakterystycznego (rekurencyjnego) wyjdzie 0 wtedy mamy tylko jeden perwiastek i wtedy \(\displaystyle{ a_n = (C + Dn)r_{1}^{n}}\) - dlaczego stała \(\displaystyle{ D}\) jest mnożona przez \(\displaystyle{ n}\) i czym to \(\displaystyle{ n}\) jest?
A także dlaczego równanie rekurencyjne Fibonacciego nazywamy "jednorodnym"?
janusz47 pisze: 26 wrz 2020, o 19:01
Jest także ładna metoda algebraiczna wyznaczenia tego równania.
@janusz47, a mógłbyś tę metodę pokazać?
Re: Wyznaczenie ilorazu ciagu Fibonacciego
: 27 wrz 2020, o 13:26
autor: a4karo
Wyznaczenie granicy ilorazu \(\displaystyle{ \frac{F_{n+1}}{F_n}}\) nie wymaga wcale takich silnych narzędzi jak wzór Bineta czy narzędzia algebraiczne. Wystarczy elementarna wiedza o ciągach i szeregu geometrycznym.
Jeżeli istnieje granica ciagu `e_n` i jest równa `g`, to musi spełniać równanie `1=g+g^2` i stąd `g=\frac{\sqrt{5}-1}{2}`.
Jest troszeczkę kłopotu z uzasadnieniem zbieżności ciągu `e_n`, bo choć ograniczony, to nie jest monotoniczny.
`F_n=F_{n-1}+F_{n-2}>2F_{n-2}`
Iterując to postępowanie i uwzględniając fakt, że `F_0=F_1=1` dostajemy oszacowanie `F_n>\sqrt{2}^n`.
Z drugiej strony mamy znaną tożsamość `F_{n+1}F_{n-1}-F_n^2=\pm1` skąd dzieląc obie strony przez `F_{n+1}F_{n}` dostajemy \(\displaystyle{ |e_{n-1}-e_n|=\frac{1}{F_{n+1}F_{n}}<\frac{1}{2^n}}\)
Stąd łatwo widać, że `e_n` jest ciagiem Cauchy'ego.
Re: Wyznaczenie ilorazu ciagu Fibonacciego
: 27 wrz 2020, o 17:09
autor: Mondo
a4karo, ciekawe podejście, ale mam kilka wątpliwośći:
a4karo pisze: 27 wrz 2020, o 13:26
Jest troszeczkę kłopotu z uzasadnieniem zbieżności ciągu `e_n`, bo choć ograniczony, to nie jest monotoniczny.
Prośba, mógłbyś uzasadnich dlaczego ograniczony oraz dlaczego nie monotoniczny? Sam ciag Fibonacciego jest ogranicozny tylko z lewej strony, a monotoniczny jest dla \(\displaystyle{ n > 2}\) (zakładając, że \(\displaystyle{ a_1 = 0}\)).
a4karo pisze: 27 wrz 2020, o 13:26
`F_n=F_{n-1}+F_{n-2}>2F_{n-2}`
Czy to równanie, które wynika chyba z "empirycznej" obserwacji ciagu nie dowodzi, że jest on rosnący, a tym samym monotoniczny?
a4karo pisze: 27 wrz 2020, o 13:26
Iterując to postępowanie i uwzględniając fakt, że `F_0=F_1=1` dostajemy oszacowanie `F_n>\sqrt{2}^n`.
Skąd `\sqrt{2}^n` ?
Dziekuję
Re: Wyznaczenie ilorazu ciagu Fibonacciego
: 27 wrz 2020, o 17:48
autor: a4karo
Brak monotoniczności wynika za wzoru \(\displaystyle{ e_{n}-e_{n-1}=\pm\frac{1}{F_{n+1}F_n}}\) bo znaki po prawej stronie występują naprzemiennie.
Zauważ, że z monotoniczności ciągu `F` nie musi wynikać monotoniczność `e`. Tak właśnie jest w tym przypadku
Rzeczywiście, troszkę nakłamałem. Mamy dla indeksów parzystych
`F_{2n}>2F_{2n-2}=\sqrt2^2F_{2n-2}>\sqrt2^4F_{2n-4}>...>\sqrt2^{2n}F_{2n-2n}=2^{n}`
i podobnie
`F_{2n+1}>2F_{2n+1-2}=\sqrt2^2F_{2n+1-2}>\sqrt2^4F_{2n+1-4}>...>\sqrt2^{2n}F_{2n+1-2n}=2^n`
co można zapisać jednym wzorkiem `F_k>2^{\lfloor k/2 \rfloor}`, a to wystarcza aby ciąg `e` był Cauchyego.
Re: Wyznaczenie ilorazu ciagu Fibonacciego
: 1 paź 2020, o 21:06
autor: Mondo
a4karo, mam jeszcze parę pytań, piszesz
a4karo pisze: 27 wrz 2020, o 13:26
Z drugiej strony mamy znaną tożsamość `F_{n+1}F_{n-1}-F_n^2=\pm1`
Z czego to zostało wyznaczone? Nie widzę tego za bardzo
Podobnie tutaj
a4karo pisze: 27 wrz 2020, o 17:48
Brak monotoniczności wynika za wzoru \(\displaystyle{ e_{n}-e_{n-1}=\pm\frac{1}{F_{n+1}F_n}}\) bo znaki po prawej stronie występują naprzemiennie.
W jaki sposób udowodnimy, że prawa strona powyższego równania przyjmuje na przemian wartości dodanie i ujemne?
Oznacza się funkcje tworzącą dla ciagu Fibonacciego poprzez \(\displaystyle{ F(x) = \sum_{n=0}^{\infty} F_{n}x^n = F_0 x^0 + F_1 x^1 + \sum_{n=2}^{\infty} (F_{n-2} + F_{n-1}) x^n }\)
I teraz kilka pytan:
1. Wydawało mi się, że celem funkcji tworzacej jest podanie formuły na obliczenie wartości ntego wyrau ciagu. Natomiast tutaj tak nie jest bo sprawdzmy np dla `x = 1` mamy `F(1) = 0 + 1 + 0 \cdot1^2 + 1 \cdot 1^2` = 2, a więc niepoprawnie. Gdzie tutaj popełniam błąd?
2. Dla czego w tej funkcji tworzącej mnożywmy każdy wyraz przez jednomiany `x^n`?
3. W podanym artykule na wikipedi przeprowadzane są rózne dziwne dla mnie kroki, np. jak wyrażenie `F(x) = F_1 x + x^2 \sum_{n=2}^{\infty} F_{n-1}x^{n-2}` zostało przepisane na `F(x) = F_1 x + x^2 \sum_{n=0}^{\infty} F_{n}x^n`? Czyli zmieniono zakres sumy w drugim wyrazie z `\sum_{n=2}^{\infty}` na `\sum_{n=0}^{\infty}`, ale to nie ma dla mnie sensu bo po tym przekształceniu mmay sytuację w której sumujemy wraz pierwszy, a w drugiym wyrazie wciąż sumujemy od początku bo `n=0`.
Re: Wyznaczenie ilorazu ciagu Fibonacciego
: 4 paź 2020, o 08:53
autor: kerajs
Errata:
Przepraszam, jakoś uciekł mi ten (i nie tylko ten) post.
Mondo pisze: 26 wrz 2020, o 20:24 natknałem się na jedną niejasność - kiedy wyróżnik równania charakterystycznego (rekurencyjnego) wyjdzie 0 wtedy mamy tylko jeden perwiastek i wtedy \(\displaystyle{ a_n = (C + Dn)r_{1}^{n}}\) - dlaczego stała \(\displaystyle{ D}\) jest mnożona przez \(\displaystyle{ n}\) i czym to \(\displaystyle{ n}\) jest?
Zakładam, iż pytasz o równanie różnicowe którego równaniem charakterystycznym jest równanie kwadratowe. Przy zerowym wyróżniku mamy dwa równe pierwiastki (teraz modny jest pierwiastek podwójny), więc każdego z nich nie może dawać identycznego rozwiązania. Rozwiązanie dla drugiego należy wzmocnić o n (dla kilku równych pierwiastków wzmacniasz je kolejno o \(\displaystyle{ n \ , \ n^2 \ , \ n^3 \ ... }\) )
Mondo pisze: 26 wrz 2020, o 20:24
A także dlaczego równanie rekurencyjne Fibonacciego nazywamy "jednorodnym"?
Ściślej jest to jednorodne równanie liniowe drugiego stopnia o współczynnikach całkowitych.
Równanie liniowe jednorodne to takie, którego prawa strona jest zerem jeśli po lewej wszystkie składniki zawierają wyłącznie wyrazy ciągu \(\displaystyle{ \left\{ a_n\right\} }\).
Np: \(\displaystyle{
a_{n+1}+a_n=0\\
a_{n+1}+na_n=0\\
a_{n+1}+2^na_n=0}\)
Niejednorodne: \(\displaystyle{
a_{n+1}+a_n=2\\
a_{n+1}+a_n=2n\\
a_{n+1}+a_n=2^n\\
a_{n+1}+a_n=2+n+2^n\\
a_{n+1}+na_n=3\\
a_{n+1}+2^na_n=n^2}\)
kerajs pisze: 4 paź 2020, o 08:53
Przepraszam, jakoś uciekł mi ten (i nie tylko ten) post.
Mondo pisze: 26 wrz 2020, o 20:24 natknałem się na jedną niejasność - kiedy wyróżnik równania charakterystycznego (rekurencyjnego) wyjdzie 0 wtedy mamy tylko jeden perwiastek i wtedy \(\displaystyle{ a_n = (C + Dn)r_{1}^{n}}\) - dlaczego stała \(\displaystyle{ D}\) jest mnożona przez \(\displaystyle{ n}\) i czym to \(\displaystyle{ n}\) jest?
Zakładam, iż pytasz o równanie różnicowe którego równaniem charakterystycznym jest równanie kwadratowe. Przy zerowym wyróżniku mamy dwa równe pierwiastki (teraz modny jest pierwiastek podwójny), więc każdego z nich nie może dawać identycznego rozwiązania. Rozwiązanie dla drugiego należy wzmocnić o n (dla kilku równych pierwiastków wzmacniasz je kolejno o \(\displaystyle{ n \ , \ n^2 \ , \ n^3 \ ... }\) )
Ok, ma to sens chociaz to `n` wprowadza trochę zamieszania. Dziękuję.
Mondo pisze: 26 wrz 2020, o 20:24
A także dlaczego równanie rekurencyjne Fibonacciego nazywamy "jednorodnym"?
Ściślej jest to jednorodne równanie liniowe drugiego stopnia o współczynnikach całkowitych.
Równanie liniowe jednorodne to takie, którego prawa strona jest zerem jeśli po lewej wszystkie składniki zawierają wyłącznie wyrazy ciągu \(\displaystyle{ \left\{ a_n\right\} }\).
Np: \(\displaystyle{
a_{n+1}+a_n=0\\
a_{n+1}+na_n=0\\
a_{n+1}+2^na_n=0}\)
Niejednorodne: \(\displaystyle{
a_{n+1}+a_n=2\\
a_{n+1}+a_n=2n\\
a_{n+1}+a_n=2^n\\
a_{n+1}+a_n=2+n+2^n\\
a_{n+1}+na_n=3\\
a_{n+1}+2^na_n=n^2}\)
Dziękuję za wyjaśnienie. Co do:
Ściślej jest to jednorodne równanie liniowe drugiego stopnia o współczynnikach całkowitych
To mam jeszcze pytanie dlaczego drugiego stopnia skoro nie ma nim ani drugiej potęgi ani też podwójnej pochodnej. Więc jak w tym wypadku zdefiniowany jest stopień równania?
Ściślej jest to jednorodne równanie liniowe drugiego stopnia o współczynnikach całkowitych
To mam jeszcze pytanie dlaczego drugiego stopnia skoro nie ma nim ani drugiej potęgi ani też podwójnej pochodnej. Więc jak w tym wypadku zdefiniowany jest stopień równania?
Stopień równania to różnica między największym, a najmniejszym indeksem wyrazów ciągu użytych w równaniu rekurencyjnym. Wszystkie moje przykłady są równaniami pierwszego stopnia.
