Równanie rekurencyjne a ciąg Fibonacciego

[DFP]

Witam.
Mam takie zadanie: Mamy prostokąt o wymiarach 2xn gdzie n jest podane przez nas samych. Może być dowolne. Musimy ten prostokąt wypełnić kostkami domina w każdej możliwym sposobie. Czyli kostki mogą być poukładane dowolnie: poziomo i pionowo. Zauważyłem, że spełniony jest warunek ciągu Fibonacciego. Z tym, że pierwsze wyrazy ciągu to 1,2,3 a nie jak w ciągu 1,1,2 itp.

Moje pytanie: podać wzór na n-ty wyraz takiego ciągu, korzystając z równania rekurencyjnego.

Wzór na ciąg Fibonacciego:
\(\displaystyle{ f_{n-1} + f_{n-2}}\)

Jak rozumiem ogólnie wzór będzie wyglądał tak:
\(\displaystyle{ a_1=a_2=1,\\ a_{n+2}=a_{n+1}+a_n,\qquad n\geqslant 1}\)

Powyższy wzór jest na 3 wyraz ciągu. Z tym, że a(n) = 1 a a(n+1) = 2

Wiem, że można obliczyć n-ty wyraz ciągu z wzoru:
\(\displaystyle{ \frac{1}{ \sqrt{5}} ( \frac{1 + \sqrt{5} }{2} } ) ^{n}}\)

Więc jaki będzie wzór na dowolny wraz ciągu? Prosiłbym najlepiej krok po kroku z dokładnym tłumaczeniem jak dla przedszkolaka skąd i co sie wzięło.

Z góry bardzo dziękuję.

[szatkus]

Na wiki jest to ładnie pokazane:

[DFP]

No tak ale tam są użyte funkcje tworzące a nie to jest mi niestety potrzebne w tym zadaniu. Mam rozwiązać to zadanie tylko za pomocą równań rekurencyjnych.

[szatkus]

\(\displaystyle{ a_{n+2}=a_{n+1}+a_{n}\\
x^2=x+1\\
x^2-x-1=0\\
\Delta=5\\
x_1=\frac{1-\sqrt{5}}{2}\\
x_2=\frac{1+\sqrt{5}}{2}\\
a_n=A(\frac{1-\sqrt{5}}{2})^n+B(\frac{1+\sqrt{5}}{2})^n\\
\begin{cases}
A\frac{1-\sqrt{5}}{2}+B\frac{1+\sqrt{5}}{2}=1\\
A(\frac{1-\sqrt{5}}{2})^2+B(\frac{1+\sqrt{5}}{2})^2=1\\
\end{cases}}\)
I tu wyznaczyć sobie A i B.

[DFP]

Dobrze chyba powoli rozumiem.
Więc robi się to tak:
1. mamy wzór na n-ty wyraz ciągu Fibonacciego, który spełnia warunek taki, że \(\displaystyle{ a_{n+2} = a_{n+1} + a_{n}}\)
2. możemy to także wyrazić jako \(\displaystyle{ x^{2} = x + 1}\) . Z tego wyliczamy wartość \(\displaystyle{ x_{1}}\) oraz \(\displaystyle{ x_{2}}\) poprzez deltę. Otrzymujemy wzór \(\displaystyle{ a_{n} = A ( \frac{1 - \sqrt{5} }{2} )^{n} ...}\)
3. Podstawiamy zamiast n w potęgach wartości pierwszego i drugiego wyrazu ciągu czyli 1 i 2 tak? Z tego wyznaczamy poprzez równanie z 2 niewiadomymi wartości A i B.

Mam w takim razie parę pytań:
1. przeglądając google natrafiłem na niejedno podstawienie zamiast \(\displaystyle{ a_{n+2} = a_{n+1} + a_{n}}\) równania kwadratowego \(\displaystyle{ x^{2} = x + 1}\). Rozumiem, że jest doprowadzenie do równania charakterystycznego tak?
2. Podstawiamy to do wzoru: \(\displaystyle{ a_{n} = A*x1 + B*x2}\). A i B są to współczynniki czyż nie? Jeżeli obliczę już A i B to otrzymam gotowy wzór jak rozumiem tak? Tylko gdzie te wyliczone A i B potem podstawić?

Wybaczcie za pytania ale chciałbym bardzo w pełni zrozumieć co sie dzieje w tym zadaniu.

[szatkus]

Sam sobie odpowiedziałeś.
\(\displaystyle{ a_{n} = A*x1 + B*x2}\)
Podstawiasz wyliczone A, B, x1, x2.
\(\displaystyle{ F_n=\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n}\)
I masz wzór na ciąg fibonacciego.

[DFP]

Witam.
Bardzo dziękuje za pomoc w zadaniu.
Jeżeli nie będzie to problem to chciałbym jeszcze poprosić o pomoc w obliczeniach...

\(\displaystyle{ A ( \frac{-1- \sqrt{5} }{2} ) + B ( \frac{-1+ \sqrt{5} }{2} ) = 1}\)
\(\displaystyle{ A ( \frac{-1- \sqrt{5} }{2} )^{2} + B ( \frac{-1+ \sqrt{5} }{2} )^{2} = 1}\)

Potęga n = 2? Czyli liczymy dla 2 wyrazu tak? W moim wypadku drugi wyraz ma wartość 2 więc całość powinna być \(\displaystyle{ A ( \frac{-1- \sqrt{5} }{2} )^{2} + B ( \frac{-1+ \sqrt{5} }{2} )^{2} = 2}\) czyż nie?

Teraz:
Wyciągam A z pierwszego równania:
\(\displaystyle{ A ( \frac{-1- \sqrt{5} }{2} ) + B ( \frac{-1+ \sqrt{5} }{2} ) = 1}\)
\(\displaystyle{ A ( \frac{-1- \sqrt{5} }{2} ) = 1 - B ( \frac{-1+ \sqrt{5} }{2} )}\)
to dzielimy przez:
\(\displaystyle{ ( \frac{-1- \sqrt{5} }{2} )}\)
Więc:
\(\displaystyle{ A= \frac{1}{\frac{-1- \sqrt{5} }{2}} - B*( \frac{-1+ \sqrt{5} }{2} ) * ( \frac{2}{-1 - \sqrt{5} } )}\)
\(\displaystyle{ A= \frac{1}{\frac{-1- \sqrt{5}}{2}} - B*( \frac{-1+ \sqrt{5} }{-1 - \sqrt{5} } )}\)
\(\displaystyle{ A = 1 * \frac{2}{-1- \sqrt{5}} - B*( \frac{-1+ \sqrt{5} }{-1 - \sqrt{5} } )}\)
\(\displaystyle{ A = - B * \frac{1 + \sqrt{5} }{-1 - \sqrt{5} }}\)
Podstawiam to do równania zamiast A:
\(\displaystyle{ - B * \frac{1 + \sqrt{5} }{-1 - \sqrt{5} } * ( \frac{-1- \sqrt{5} }{2} )^{2} + B*( \frac{-1+ \sqrt{5} }{2} )^{2} = 2}\)
\(\displaystyle{ - B * \frac{1 + \sqrt{5} }{-1 - \sqrt{5} } + B * \frac{3 + \sqrt{5} }{1} = 2}\)

Czy mogę prosić o poradę co dalej? Czy dobrą drogą idę i co dalej zrobić z powyższym?

[szatkus]

Przede wszystkim zamienić tamtą dwójkę na jedynkę. Ciąg Fibonacciego to 1, 1, 2, 3, 5...
Czemu nagle zniknęło \(\displaystyle{ \frac{2}{-1- \sqrt{5}}}\)?
Potem podstaw A i cierpliwie licz tą sieczkę aż nie wyruguje się wartość B.

[DFP]

No ok tylko w moim wypadku 2 wyraz ciągu ma wartość 2. A to dlatego, że mając pole 2x2 mamy do wyboru 2 kombinacje klocków domina - poziomo i pionowo. Nie ma więcej. Dlatego to nie jest do końca ciąg fibonacciego. On sie ciągnie tak: 1,2,3,5 itd.

Te \(\displaystyle{ \frac{2}{ -1 - \sqrt{5} }}\) wydawało mi się, że mogę połączyć z\(\displaystyle{ - B* \frac{-1 + \sqrt{5} }{-1 - \sqrt{5} }}\)

Na moje rozumowanie -B * przez licznik ułamka nie wpłynie na to aby mając wspólny mianownik nie zrobić \(\displaystyle{ 2 - 1 + \sqrt{5}}\)

Czy sie mylę?

A co do samych obliczeń to potrzebuję trochę pomocy bo nie za bardzo właśnie w tej postaci co mam wiem co zrobić

Dochodząc do postaci \(\displaystyle{ - B * \frac{1 + \sqrt{5} }{-1 - \sqrt{5} } + B * \frac{3 + \sqrt{5} }{1} = 2}\) Sprowadzać do wspólnego mianownika? To dostaniemy według moich obliczeń:
\(\displaystyle{ - B * \frac{1 + \sqrt{5} }{- 1 - \sqrt{5} } + B*\frac{-8 - 4 \sqrt{5} }{- 1 - \sqrt{5} }}\)

Czyż nie?

[szatkus]

No ok tylko w moim wypadku 2 wyraz ciągu ma wartość 2. A to dlatego, że mając pole 2x2 mamy do wyboru 2 kombinacje klocków domina - poziomo i pionowo. Nie ma więcej. Dlatego to nie jest do końca ciąg fibonacciego. On sie ciągnie tak: 1,2,3,5 itd.

Aha, to w porządku, ważne, że zależność rekurencyjna jest taka sama. Po prostu wyjdzie inny wzór.
Możesz też liczyć dalej Fibonnaciego i potem zmienić wyrazy początkowe i zwięszyć potęgi we wzorze o jeden.

Te \(\displaystyle{ \frac{2}{ -1 - \sqrt{5} }}\) wydawało mi się, że mogę połączyć z\(\displaystyle{ - B* \frac{-1 + \sqrt{5} }{-1 - \sqrt{5} }}\)

Na moje rozumowanie -B * przez licznik ułamka nie wpłynie na to aby mając wspólny mianownik nie zrobić \(\displaystyle{ 2 - 1 + \sqrt{5}}\)

Do ostatniego słowa miałeś rację, w liczniku wyjdzie \(\displaystyle{ 2 - B(-1 + \sqrt{5})}\)

A co do samych obliczeń to potrzebuję trochę pomocy bo nie za bardzo właśnie w tej postaci co mam wiem co zrobić

Na początek wyrazy wolne przerzuć na prawą stronę, po lewej zostaną te związane z B. Wyciągnij B przed nawias, wszystko w środku złącz w jeden ułamek i podziel stronami przez niego.