Wyznaczenie ilorazu ciagu Fibonacciego

Mondo · Post autor: **Mondo** » 26 wrz 2020, o 18:22

Witam,

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?

kerajs · Post autor: **kerajs** » 26 wrz 2020, o 18:35

Z wzoru Bineta:
\(\displaystyle{
\lim_{ n\to \infty } \frac{F_{n+1}}{F_n}= \lim_{ n\to \infty } \frac{ \frac{1}{ \sqrt{5} } \left[ \left( \frac{1+ \sqrt{5} }{2} \right)^{n+1}-\left( \frac{1- \sqrt{5} }{2} \right)^{n+1}\right] }{\frac{1}{ \sqrt{5} } \left[ \left( \frac{1+ \sqrt{5} }{2} \right)^{n}-\left( \frac{1- \sqrt{5} }{2} \right)^{n}\right] } = \frac{1+ \sqrt{5} }{2}}\)

janusz47 · Post autor: **janusz47** » 26 wrz 2020, o 18:45

Trzeba jeszcze udowodnić wzór Jacque'a Bineta na \(\displaystyle{ n -}\) wyraz ciągu Fibbonaciego:

\(\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].}\)

kerajs · Post autor: **kerajs** » 26 wrz 2020, o 18:54

janusz47 pisze: 26 wrz 2020, o 18:45 Trzeba jeszcze udowodnić wzór Jacques'a Bineta na \(\displaystyle{ n -}\) wyraz ciągu Fibbonaciego:

\(\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]}\)

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).

janusz47 · Post autor: **janusz47** » 26 wrz 2020, o 19:01

Jest także ładna metoda algebraiczna wyznaczenia tego równania.

Mondo · Post autor: **Mondo** » 26 wrz 2020, o 20:24

kerajs pisze: 26 wrz 2020, o 18:35 Z wzoru Bineta

Dzięku dokładnie tego potrzebowałem.

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ć?

a4karo · Post autor: **a4karo** » 27 wrz 2020, o 13:26

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.

Oznaczmy \(\displaystyle{ e_n=\frac{F_n}{F_{n+1}}}\)
Ciąg Fibonacciego spełnia równanie
\(\displaystyle{ F_{n+1}=F_n+F_{n-1}}\)
skąd dostajemy
\(\displaystyle{ 1=\frac{F_n}{F_{n+1}}+\frac{F_{n-1}}{F_{n+1}}=\frac{F_n}{F_{n+1}}+\frac{F_{n-1}}{F_{n}}\frac{F_{n}}{F_{n+1}}=e_n+e_{n-1}e_{n}}\)

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.

Mondo · Post autor: **Mondo** » 27 wrz 2020, o 17:09

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ę

a4karo · Post autor: **a4karo** » 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.

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.

Mondo · Post autor: **Mondo** » 1 paź 2020, o 21:06

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?

a4karo · Post autor: **a4karo** » 1 paź 2020, o 22:49

Ad 1. To jest zalezność Cassiniego

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego

Ad 2. Mianownik jest dodatni, a znaki występują na przemian.

Mondo · Post autor: **Mondo** » 2 paź 2020, o 17:13

a4karo pisze: 1 paź 2020, o 22:49 Ad 1. To jest zalezność Cassiniego
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego

Dziękuję

a4karo pisze: 1 paź 2020, o 22:49 Ad 2. Mianownik jest dodatni, a znaki występują na przemian.

Jeśli mianownik jest dodatni, to i całe wyrażenie musi takie być ponieważ w liczniku mamy stałą równą `1`

W kontekscie ciagów Fibonacciego wróciłem jeszcze uwagę na tzn "funkcje tworzące". Analizuję przykład ->

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Funkcja_tworz%C4%85ca#Liczby_Fibonacciego

i mam takie pytania:

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`.

kerajs · Post autor: **kerajs** » 4 paź 2020, o 08:53

Errata:

Mondo · Post autor: **Mondo** » 4 paź 2020, o 13:10

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ę.

kerajs pisze: 4 paź 2020, o 08:53
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?

kerajs pisze: 4 paź 2020, o 08:53
Mondo pisze: 26 wrz 2020, o 20:24
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ć?
Przypuszczam, że jest ona tutaj:
O ciągu Fibonacciego

Zgadza sie, zdaje się, że mój post był motywacją do tego artykułu

kerajs · Post autor: **kerajs** » 4 paź 2020, o 17:59

Mondo pisze: 4 paź 2020, o 13:10 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?

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.

Matematyka.pl

Wyznaczenie ilorazu ciagu Fibonacciego

Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego

Re: Wyznaczenie ilorazu ciagu Fibonacciego