Rekurencja

Definicje rekurencyjne


Definicja rekurencyjna (indukcyjna):

  • nieformalnie - taka definicja, która odwołuje się do samej siebie - ale trzeba tu uważać, by odwołanie było do instancji o mniejszej komplikacji,
  • zwykle chodzi o ciąg \( \langle a_0, a_1, a_2, a_3, \ldots \rangle \), - dla którego przepis na element \( a_n \) wykorzystuje jakieś poprzednie elementy: \( a_{n-1}, a_{n-2}, \ldots \) itp.,
  • początkowy element (lub kilka początkowych) muszą być zadane konkretnie - żeby było od czego zacząć,
  • zwykle definicja rekurencyjna odwołuje się do jednego lub kilku poprzednich elementów, ale może też odwoływać się do wszystkich poprzednich.

Przykład

Silnia liczby \( n \) (zapisywana jako \( n! \)) to iloczyn kolejnych liczb naturalnych od \( 1 \) do \( n \), czyli

\( n!=n(n-1)\cdot\ldots\cdot2\cdot1. \)

Przyjmuje się że \( 0!=1 \). Oto wartości silni dla kilku początkowych liczb naturalnych


\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots \\ \hline n! & 1 & 1 & 2 & 6 & 24 & 120 & 720 & 5040 & 40320 & \cdots \\ \hline \end{array} \)

Ciąg \( 0!, 1!, 2!, 3!, 4!,\ldots \) aby mógł być precyzyjnie rozumiany np. przez komputer, powinien być zadany rekurencyjnie jako:

\( \begin{align*} s_0 & = 1 \\ s_{n} & = n \cdot s_{n-1} \quad dla \quad n\geq 1. \end{align*} \)

Ponieważ pierwszy wyraz jest zadany, to możemy kolejno obliczać:

\( \begin{align*} s_0 & = 1 \\ s_1 & = 1 \cdot s_{0} = 1 \cdot 1 = 1 \\ s_2 & = 2 \cdot s_{1} = 2 \cdot 1 = 2 \\ s_3 & = 3 \cdot s_{2} = 3 \cdot 2 = 6 \\ s_4 & = 4 \cdot s_{3} = 4 \cdot 6 = 24 \\ \ldots \end{align*} \)

Przykład

Jaki ciąg jest zdefiniowany poprzez małą modyfikację w definicji silni?

\( \begin{align*} s_0 & = 0 \\ s_{n} & = n \cdot s_{n-1}\quad {dla}\quad n\geq 1 \end{align*} \)

A co definiują następujące określenia:

\( \begin{align*} s_0 & =\frac{1}{2} \\ s_{n} & = n \cdot s_{n-1} \quad {dla}\quad n\geq 1 \end{align*} \)

oraz

\( \begin{align*} s_0 & = 1 \\ s_{n} & = n \cdot s_{n-2} \quad {dla}\quad n\geq 2. \end{align*} \)

W ostatnim przypadku widać, że ponieważ odwołanie jest dwa wyrazy wstecz, to już wyliczenie pierwszego wyrazu \( s_1 \) staje się niemożliwe.

Ciąg arytmetyczny

Przykład

W ciągu zadanym poprzez równania:

\( \begin{align*} s_0 & = 0 \\ s_{n} & = s_{n-1}+2 \quad {dla}\quad n\geq 1 \end{align*} \)

łatwo rozpoznać kolejne liczby parzyste:

\( s_n = 2n. \)

Ogólnie ciąg zadany poprzez ustalenie \( a_0 \) oraz

\( a_n = a_{n-1} + r \)

to tzw. ciąg arytmetyczny.
Jego \( n \)-ty wyraz dany jest wzorem:

\( a_n = a_0 + n\cdot r. \)

Aby to uzasadnić, pokazujemy indukcyjnie, że:

\( a_0 + 0\cdot r = a_0 \quad\textrm{jest rzeczywiście zerowym wyrazem ciągu} \)

oraz

\( a_0 + n\cdot r = (a_0 + (n-1)r) + r = a_{n-1}+r = a_n \)

Ciąg geometryczny

Przykład

W ciągu zadanym poprzez równania:

\( \begin{align*} s_0 & = 1 \\ s_{n} & = 2\cdot s_{n-1} \quad {dla}\quad n\geq 1 \end{align*} \)

łatwo rozpoznać kolejne potęgi liczby \( 2 \):


\( s_n = 2^n. \)

Ogólnie ciąg zadany poprzez ustalenie \( a_0 \) oraz zadanie

\( a_n = q\cdot a_{n-1} \)

to tzw. ciąg geometryczny.
Jego \( n \)-ty wyraz dany jest wzorem:

\( a_n = a_0 \cdot q^n. \)

Aby to uzasadnić, pokazujemy indukcyjnie, że:


\( a_0 \cdot q^0 = a_0 \cdot 1 = a_0 \quad\textrm{jest rzeczywiście zerowym wyrazem ciągu} \)

oraz

\( a_0 \cdot q^n = (a_0 \cdot q^{n-1})\cdot q = a_{n-1}\cdot q = a_n. \)

Wieże Hanoi

U zarania czasu Bóg umieścił 64 złote krążki na jednej z trzech diamentowych iglic tak, że krążki wyżej umieszczone miały mniejsze promienie.

Następnie Bóg polecił grupie mnichów przełożenie tych krążków na trzecią iglicę \( (C) \), ale tak by:

  • w jednym ruchu przenosić tylko jeden krążek,
  • krążek większy nigdy nie może leżeć na krążku mniejszym,
  • można posługiwać się iglicą \( B \).

Mnisi pracują od zarania dziejów dzień i noc ... .Ile czasu im to zajmie?

Wieże Hanoi - analiza

Przykład (E.Lucas, 1883)

By obliczyć ilość potrzebnych do wykonania ruchów, przeanalizujmy najpierw małe przypadki:
Łatwo zauważyć, że dla 1 krążka potrzebny jest jeden ruch: \( A \to C \)
Podobnie dla dwu krążków możemy postąpić: \( A \to B, \ \ A \to C, \ \ B \to C \)
Przy 3 krążkach postępujemy tak:

  • najpierw przenosimy dwa górne krążki na iglicę \( B \) posługując się iglicą \( C \):

\( A \to C, \ \ A \to B, \ \ C \to B \)

  • przenosimy największy krążek z \( A \) na \( C \):

\( A \to C \)

  • przenosimy krążki z \( B \) na \( C \) posługując się iglicą \( A \):

\( B \to A, \ \ B \to C, \ \ A \to C \)

co pokazuje, że potrzeba tu 7 ruchów.
Czy już wiesz jak rozwiązać to zadanie w ogólności (dla \( n \) krążków)?
Oznaczmy przez \( H_n \) liczbę ruchów potrzebnych do przeniesienia \( n \) krążków z jednej iglicy na drugą. Wiemy już, że:

\( \begin{align*} H_1 & = 1 \\ H_2 & =3 \\ H_3 & =7 \end{align*} \)

Aby przenieść \( n \) krążków z \( A \) na \( C \) możemy postąpić podobnie jak w przypadku 3 krążków, redukując zadanie do:

  • przenosimy \( n-1 \) górnych krążków na iglicę \( B \) posługując się iglicą \( C \) - potrzeba na to \( H_{n-1} \) ruchów
  • przenosimy największy krążek z \( A \) na \( C \) - to tylko jeden ruch
  • przenosimy \( n-1 \) krążków z \( B \) na \( C \) posługując się iglicą \( A \) - znów potrzeba na to \( H_{n-1} \) ruchów

A zatem

\( H_n = H_{n-1} +1 + H_{n-1} = 2\cdot H_{n-1} +1 \)

Ile wobec tego wynosi \( H_{64} \)?

Mamy więc równanie rekurencyjne

\( \begin{align*} H_1 & = 1 \\ H_{n} & = 2\cdot H_{n-1}+1 \quad \textrm{dla}\quad n\geq 2 \end{align*} \)

bardzo podobne do ciągu geometrycznego.
Możemy policzyć kilka jego wyrazów:


\( 1, \ \ 3, \ \ 7, \ \ 15, \ \ 31, \ \ 63, \ \ 127, \ldots \)

i rozpoznać w nim ciąg potęg dwójki zmniejszonych o 1.

Ale czy rzeczywiście \( H_n = 2^n -1 \)?

I znów, aby się upewnić, że nasze odgadnięcie było poprawne, sprawdzamy indukcyjnie, że

\( 2 \cdot H_{n-1} + 1= 2 \cdot (2^{n-1}-1) +1 = 2\cdot 2^{n-1} -2 +1 = 2^n -1 = H_n \)

co oznacza, że rzeczywiście ciąg \( 2^n-1 \) spełnia równanie rekurencyjne, którym zadany jest ciąg \( H_n \).
A wiec \( H_{64} =2^{64}-1 \approx 100~000~000~000~000~000~000 \), co przy przenoszeniu jednego krążka na sekundę zajmie ponad \( 3~000~000~000~000 \) lat, a przenosząc te krążki "komputerem" 3GHz potrzeba będzie... i tak ponad tysiąc lat!

Przykład

Znajdź postać zwartą zadanych ciągów rozwijając równanie rekurencyjne:

\( \begin{align*} a_0 & =2, \\ a_{n+1} & =a_n^2. \end{align*} \)

Wskazówka:
Policz kilka pierwszych wyrazów ciągu:

\( a_n = a_{n-1}^2=a_{n-2}^4=a_{n-3}^8= \ldots =a_0^{2^n}=2^{2^n}. \)

Przykład

Jaka jest największa możliwa liczba \( l_n \) obszarów wyznaczonych przez \( n \) prostych na płaszczyźnie?

Sprawdźmy najpierw kilka pierwszych wartości.

  • Gdy nie ma żadnej prostej obszar jest jeden.
  • Jedna prosta tworzy zawsze dwa różne obszary.
  • Kładąc drugą prostą (byle nie równoległą do pierwszej) otrzymujemy \( 4 \) obszary.

W tym momencie możemy pokusić się o zgadywanie i przypuścić, że \( l_n=2^n \). Jednakże

  • Dla trzech prostych jest to \( 7 \).

Zauważmy, że nowa prosta zwiększa ilość obszarów o \( k \) jeśli przecina dokładnie \( k-1 \) z poprzednich prostych i to w nowych punktach przecięć. Z drugiej strony dwie proste mogą się przeciąć w co najwyżej jednym punkcie i przecinają się o ile nie są równolegle. Widzimy zatem, że najwięcej obszarów dostaniemy kładąc kolejne proste w ten sposób aby żadne dwie nie były równoległe i żadne trzy nie przecinały się w jednym punkcie. Otrzymujemy następujące równanie rekurencyjne:

\( \begin{align*} l_0 & =1, \\ l_{n+1} & =l_n+n. \end{align*} \)

Ponownie rozwiążemy równanie rozwijając je:

\( \begin{align*} l_n & =l_{n-1}+n=l_{n-2}+(n-1)+n=l_{n-3}+(n-2)+(n-1)+n=\ldots \\ & =l_0+1+2+\ldots+n=1+\frac{n(n+1)}{2}, \end{align*} \)

gdzie ostatnia równość wynika z - już udowodnionego - wzoru na sumę kolejnych liczb naturalnych.

Liczby Fibonacciego

Spośród ciągów zdefiniowanych rekurencyjnie, jednym z najsłynniejszych jest ciąg Fibonacciego \( {\{ {f_i} \}\ }_{i\in\mathbb{N}} \) zadany przez

\( \begin{align*} f_0 & =0, \\ f_1 & =1, \\ f_{n+2} & =f_n+f_{n+1}. \end{align*} \)

Wszystkie wyrazy ciągu, oprócz pierwszych dwu, są sumą dwu poprzednich elementów. Oto kilka pierwszych wartości ciągu Fibonacciego:

\( \begin{array} {c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 \\ \end{array} \)

  • Jak odgadnąć wzór na ogólny wyraz ciągu?
  • Jeśli nie można odgadnąć, to jak oszacować szybkość wzrostu tego ciągu?
  • Czy rośnie on wielomianowo czy raczej wykładniczo?

Pierwsze pytanie - póki co - wydaje się dość beznadziejne.

Przykład

Na ile sposobów można ułożyć domina na prostokącie o rozmiarze \( 2 \times n \)?

\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \hline & & & & & & & & & & & & & & & & & & & & & & & & & & & \\ \hline \end{array} \)

Oznaczmy, tę liczbę przez \( d_n \) w zależności od \( n \).

  • Dla \( n=1 \) jest to możliwe na dokładnie jeden sposób, tzn. \( d_1=1 \)
  • Dla \( n=2 \) są już dwa takie sposoby:

- ustawiamy obie kostki poziomo, lub obie pionowo,
a zatem \( d_2=2 \).

  • Dla \( n=3 \) są trzy sposoby,
  • Pokrywając większy prostokąt \( 2 \times n \) musimy jakoś pokryć dwa skrajne pola przylegające do krótszej krawędzi o długości \( 2 \). Można to zrobić na dwa sposoby:
    • ułożyć jedno domino pionowo - pozostanie prostokąt \( 2 \times (n - 1) \), który można pokryć na \( d_{n-1} \) sposobów,
    • ułożyć dwa domina poziomo - pozostanie prostokąt \( 2 \times (n - 2) \), który można pokryć na \( d_{n-2} \) sposobów.

Czyli łącznie jest \( d_n = d_{n-1}+d_{n-2} \) sposobów pokrycia tablicy \( 2 \times n \).

Rozpoznajemy w tym łatwo ciąg Fibonacci'ego \( d_n = f_{n+1} \) (bo oczywiście pusty prostokąt \( 2 \times 0 \) można pokryć na dokładnie jeden sposób, \( d_0=1 \)).

Obserwacja 2.1

\( f_0+f_1+\ldots+f_n=f_{n+2}-1. \)

Dowód

Polecamy jako ćwiczenie bardzo łatwy dowód powyższej równości przez indukcję. Przedstawimy alternatywny dowód posługujący się intuicją z poprzedniego przykładu. Wiemy zatem, że prostokąt wielkości \( 2\times n \) można pokryć kostkami domina na \( f_{n+1} \) sposobów.

Dla dowodu obserwacji, policzmy na ile sposobów można ułożyć prostokąt wielkości \( 2 \times (n+1) \) w taki sposób aby było tam chociaż jedno domino ustawione poziomo. Policzymy to dwiema różnymi metodami:

  • Jest tylko jedna metoda ułożenia prostokąta \( 2 \times (n+1) \) bez poziomych klocków. A zatem jest \( f_{n+2}-1 \) sposobów ułożenia prostokąta \( 2 \times (n+1) \) z chociaż jednym dominem poziomym.
  • Rozważmy kolejne możliwe miejsca pierwszego poziomego domina (tak naprawdę pary domin) w prostokącie \( 2 \times (n+1) \) od lewej:
    • jeśli na samym początku jest para poziomych domin, to pozostaje prostokąt \( 2\times (n-1) \), który możemy wypełnić dowolnie na \( f_{n} \) sposobów;
    • jeśli na początku jest \( i \) (gdzie \( 0\leq i\leq n \)) pionowych domin, a potem następuje para poziomych, to pozostaje prostokąt \( 2\times (n-i-1) \), który można wypełnić na \( f_{n-i} \) sposobów;
    • para poziomych domin może się pojawić najdalej po \( i=n-1 \) pionowych dominach

To dowodzi, iż jest dokładnie \( f_n+f_{n-1}+\ldots+f_0 \) sposobów ułożenia prostokąta \( (n+1)\times2 \) z chociaż jednym dominem poziomym.

Policzyliśmy na dwa różne sposoby to samo, otrzymując obie strony postulowanej równości. To kończy dowód.

Obserwacja 2.2

\( f_0^2+f_1^2+\ldots+f_n^2=f_n\cdot f_{n+1}. \)

Dowód

Dowód przez indukcję po \( n \):

  • dla \( n=0 \) mamy \( f_0^2=0=f_0\cdot f_1 \),
  • do założonej indukcyjnie równości \( f_0^2+f_1^2+\ldots+f_k^2=f_k\cdot f_{k+1} \) dodajmy obustronnie \( f_{k+1}^2 \) otrzymując

\( f_0^2+f_1^2+\ldots+f_k^2+f_{k+1}^2 = f_k\cdot f_{k+1}+f_{k+1}^2 = f_{k+1}\cdot(f_k+f_{k+1}) = f_{k+1}\cdot f_{k+2}, \)

co kończy dowód kroku indukcyjnego.

Twierdzenie 2.3 [wzór Eulera-Bineta]

\( f_n=\frac{1}{\sqrt{5}} \left[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\right]. \)

Dowód

Rozważmy równanie:

\( f^2-f-1=0. \)

Mnożąc je obustronnie przez \( x^n \) otrzymujemy:

\( f^{n+2}=f^{n+1}+f^n. \)

Oznacza to, że jeśli \( x \) jest pierwiastkiem równania \( f^2-f-1=0 \), to ciąg \( f_n = x^n \) spełnia zależność rekurencyjną Fibonacci'ego:

\( f_{n+2} = f_n+f_{n+1}. \)

Tyle, że równanie ma dwa rzeczywiste rozwiązania:


\( x_1 = \frac{1+\sqrt{5}}{2} \ \ \ \ \ \ \ \ \ \ x_2 = \frac{1-\sqrt{5}}{2}. \)

Który więc z ciągów \( x_1^n, x_2^n \) jest ciągiem Fibonacci'ego? Okazuje się, że żaden, bo na przykład ilorazy kolejnych wyrazów ciągu Fibonacci'ego nie są stałe, a takie musiałyby być dla ciągów geometrycznych \( x_1^n, x_2^n \). Co więcej:

  • jeśli ciąg \( a_n \) spełnia zależność \( f^{n+2}=f^{n+1}+f^n \), to dla dowolnej liczby rzeczywistej \( \alpha \) ciąg \( \alpha\cdot a_n \) też spełnia tę zależność,
  • jeśli ciągi \( a_n \) i \( b_n \) spełniają zależność \( f^{n+2}=f^{n+1}+f^n \), to ich suma \( a_n+b_n \) też spełnia tę zależność.

Oznacza to w szczególności, że zbiór \( F \) ciągów spełniających zależność \( f^{n+2}=f^{n+1}+f^n \) jest podprzestrzenią wektorową przestrzeni \( \mathbb{R}^\mathbb{N} \).

Ćwiczenie: Przestrzen \( F \) jest dwuwymiarowa o bazie \( \varphi, 1-\varphi \)

Przypuśćmy na chwilę, że jakaś kombinacja liniowa ciągów \( x_1^n, x_2^n \), tzn.

\( c_1 \cdot x_1^n + c_2 \cdot x_2^n \)

jest poszukiwanym ciągiem Fibonacci'ego. Aby wyznaczyć stałe \( c_1, c_2 \) zauważmy, że muszą one spełniać układ równań:


\( f_0 = c_1 + c_2 \ \ \ \ \ \ \ f_1 = c_1\cdot x_1 + c_2 x_2 \)

co po rozwiązaniu daje:

\( \begin{align*} c_1 & = \frac{f_1 - f_0x_2}{x_1-x_2}= \frac{1}{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}} =\frac{1}{\sqrt{5}} \\ c_2 & = \frac{f_1 - f_0x_1}{x_2-x_1}= \frac{1}{\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2}} =-\frac{1}{\sqrt{5}} \end{align*} \)

i ostatecznie dostajemy ciąg:

\( F(n) = \frac{1}{\sqrt{5}}\cdot \left[(\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n} \right], \)

jako potencjalnego kandydata na ciąg Fibonacci'ego. W istocie potrzebujemy indukcyjnego dowodu, że \( F(n)=f_n \). Dla wygody oznaczmy \( \varphi=\frac{1+\sqrt{5}}{2} \).

  • Ponieważ liczby Fibonacci'ego są zadane wzorem odwołującym się do dwóch poprzednich elementów sprawdzamy dwie pierwsze wartości:
    • \( F(0)=\frac{1}{\sqrt{5}}\varphi^0-\frac{1}{\sqrt{5}}(1-\varphi)^0=\frac{1}{\sqrt{5}}-\frac{1}{\sqrt{5}}=0=f_0 \),
    • \( F(1)=\frac{1}{\sqrt{5}}\varphi-\frac{1}{\sqrt{5}}(1-\varphi)=\frac{1}{\sqrt{5}}(2\cdot\frac{1+\sqrt{5}}{2}-1)=1=f_1 \),
  • Aby pokazać, że \( F(k+2)=f_{k+2} \) użyjemy pod koniec naszych obliczeń założenia indukcyjnego, że \( F(k+1)=f_{k+1} \) i \( F(k)=f_{k} \), a także tego, że zarówno \( \varphi \) jak i \( 1-varphi \) spełniają zależność \( x^{k+2}=x^{k+1}+x^k \):


\( \begin{align*} F(k+2) & =\frac{1}{\sqrt{5}}\varphi^{k+2}-\frac{1}{\sqrt{5}}(1-\varphi)^{k+2} \\ & =\frac{1}{\sqrt{5}}(\varphi^{k}+\varphi^{k+1})-\frac{1}{\sqrt{5}}((1-\varphi)^{k}+(1-\varphi)^{k+1}) \\ & =\frac{1}{\sqrt{5}}(\varphi^{k}-(1-\varphi)^{k})+\frac{1}{\sqrt{5}}(\varphi^{k+1}-(1-\varphi)^{k+1}) \\ & =F(k)+F(k+1) \\ & =f_k+f_{k+1} \\ & =f_{k+2}. \end{align*} \)

Liczba \( \varphi=\frac{1+\sqrt{5}}{2} \) jest powszechnie znana jako złota liczba. Opisuje ona tak zwane złote proporcje w sztuce. Pojawia się ona również bardzo często przy okazji różnych obiektów kombinatorycznych. Występuje również w kolejnym wniosku, który po raz pierwszy zaobserwował Johannes Kepler.

Wniosek 2.4

\( \lim_{n \to \infty}\frac{f_{n+1}}{f_n}=\varphi. \)

Dowód

\( \begin{align*} \lim_{n \to \infty}\frac{f_{n+1}}{f_n} & =\lim_{n \to \infty}\frac{\frac{1}{\sqrt{5}}(\varphi^{n+1}-(1-\varphi)^{n+1})}{\frac{1}{\sqrt{5}}(\varphi^n-(1-\varphi)^n)} \\ & =\lim_{n \to \infty}\frac{\frac{1}{\sqrt{5}}\varphi-\frac{1}{\sqrt{5}}(1-\varphi)(\frac{1-\varphi}{\varphi})^n}{\frac{1}{\sqrt{5}}-\frac{1}{\sqrt{5}}(\frac{1-\varphi}{\varphi})^n} \\ & =\varphi, \end{align*} \)

gdzie ostatnia równość wynika z faktu, iż

\( \lim_{n \to \infty}(\frac{1-\varphi}{\varphi})^n=0, \)

jako że \( \vert\frac{1-\varphi}{\varphi}\vert < 1 \).

Macierze liczb Fibonacci'ego

Rozważając specjalne kwadratowe macierze \( 2\times2 \) liczb Fibonacci'ego postaci

\( \left[ \begin{array} {cc} f_{n+2} & f_{n+1} \\ f_{n+1} & f_n \end{array} \right] \)

łatwo zauważamy, że

\( \left[ \begin{array} {cc} f_{n+2} & f_{n+1} \\ f_{n+1} & f_n \end{array} \right] \left[ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \right] = \left[ \begin{array} {cc} f_{n+3} & f_{n+2} \\ f_{n+2} & f_{n+1} \end{array} \right]. \)

Ponieważ równocześnie:

\( \left[ \begin{array} {cc} f_2 & f_1 \\ f_1 & f_0 \end{array} \right] = \left[ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \right], \)

to łatwo indukcyjnie łatwo udowodnić, że


\( \left[ \begin{array} {cc} f_{n+1} & f_n \\ f_n & f_{n-1} \end{array} \right] = \left[ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \right]^n. \)

Przyrównując wyznaczniki obu macierzy otrzymujemy tożsamość, którą jako pierwszy opublikował Jean-Dominique Cassini w 1680 roku.

Obserwacja 2.5
\( f_{n+1}f_{n-1}-f_n^2=(-1)^n. \)

Korzystając z kolei z faktu, że \( A^mA^n=A^{m+n} \) dla dowolnej kwadratowej macierzy \( A \), otrzymujemy:

Obserwacja 2.6


\( \begin{align*} f_n^2+f_{n-1}^2 & =f_{2n-1}, \\ f_{n+1}f_m+f_nf_{m-1} & =f_{m+n}. \end{align*} \)

Rozwiązywanie liniowych równań rekurencyjnych - metoda ogólna

Rozumowanie dotyczące ciągu Fibonacci'ego możemy uogólnić. Chwilowo skupimy się jedynie na przypadku, gdy dla rozwiązania równania rekurencyjnego

\( s_n = a\cdot s_{n-1} + b\cdot s_{n-2}, \)
równanie kwadratowe

\( x^2 = ax+b \)

ma dokładnie dwa różne pierwiastki \( x_1, x_2 \). Wtedy bowiem łatwo pokazać, że ciąg

\( s_n = c_1 \cdot x_1^n + c_2 \cdot x_2^n \)

ze stałymi

\( c_1 = \frac{s_1 - s_0x_2}{x_1-x_2} \ \ \ \ \ \ \ \ c_2 = \frac{s_1 - s_0x_1}{x_2-x_1} \)

jest poszukiwanym rozwiązaniem.

Gdy równanie \( x^2 = ax+b \) ma tylko jeden pierwiastek \( x_0 \) (podwójny, gdy \( a^2=4b \)), to wkrótce pokażemy, że rozwiązaniem jest

\( s_n = c_1 \cdot x_0^n + c_2 \cdot n \cdot x_0^n \)

ze stałymi wyznaczonymi, jak poprzednio, poprzez dwa pierwsze wyrazy początkowe:

\( c_1 = s_0 \ \ \ \ \ \ \ \ c_2 = \frac{s_1 - s_0x_0}{x_0}. \)

Drzewa binarne

Poznaliśmy wiele przykładów ciągów liczbowych zadanych równaniami rekurencyjnymi. Teraz poznamy zupełnie inną strukturę zadaną definicją rekurencyjną.

Drzewo binarne to dowolny obiekt powstały zgodnie z regułami:

  • \( \perp \) jest drzewem binarnym,
  • jeśli \( T_0 \) i \( T_1 \) są drzewami binarnymi to \( T_0\wedge T_1 \) też jest drzewem binarnym.

Zbiór wszystkich drzew binarnych oznaczamy przez \( \mathbb{T} \). Wypisując konkretne drzewo binarne używamy nawiasów aby ujednoznacznic kolejność aplikacji reguł z definicji rekurencyjnej.

Wielkość drzewa binarnego jest wyznaczona funkcją

\( \mathbb{T} \ni T \mapsto \vert T\vert \in \mathbb{N} \)

zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

  • \( \vert\perp\vert=1 \),
  • \( \vert T_0\wedge T_1\vert=\vert T_0\vert+\vert T_1\vert+1 \).

Szerokość drzewa binarnego jest wyznaczona funkcją

\( \mathbb{T} \ni T \mapsto \mbox{\sf h}(T) \in \mathbb{N} \)

zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

  • \( \mbox{\sf w}(\perp)=1 \),
  • \( \mbox{\sf w}(T_0\wedge T_1)=\mbox{\sf w}(T_0)+\mbox{\sf w}(T_1) \).

Wysokość drzewa binarnego jest wyznaczona funkcją

\( \mathbb{T} \ni T \mapsto \mbox{\sf h}(T) \in \mathbb{N} \)

zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

  • \( \mbox{\sf h}(\perp)=0 \),
  • \( \mbox{\sf h}(T_0\wedge T_1)=\max(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) )+1 \).

Przykład

\( \begin{align*}\vert(\perp\wedge(\perp\wedge\perp))\wedge(\perp\wedge\perp)\vert & =\vert\perp\wedge(\perp\wedge\perp)\vert+\vert\perp\wedge\perp\vert+1 \\ & =(\vert\perp\vert+\vert\perp\wedge\perp\vert+1)+(\vert\perp\vert+\vert\perp\vert+1)+1 \\ & =(2+(\vert\perp\vert+\vert\perp\vert+1))+3+1 \\ & =9. \end{align*} \)

\( \begin{align*}\mbox{\sf w}((\perp\wedge(\perp\wedge\perp))\wedge(\perp\wedge\perp)) & =\mbox{\sf w}(\perp\wedge(\perp\wedge\perp))+\mbox{\sf w}(\perp\wedge\perp) \\ & =(\mbox{\sf w}(\perp)+\mbox{\sf w}(\perp\wedge\perp))+(\mbox{\sf w}(\perp)+\mbox{\sf w}(\perp)) \\ & =(\mbox{\sf w}(\perp)+(\mbox{\sf w}(\perp)+\mbox{\sf w}(\perp))+(\mbox{\sf w}(\perp)+\mbox{\sf w}(\perp)) \\ & =5. \end{align*} \)

\( \begin{align*}\mbox{\sf h}((\perp\wedge(\perp\wedge\perp))\wedge(\perp\wedge\perp)) & =\max(\mbox{\sf h}(\perp\wedge(\perp\wedge\perp)),\mbox{\sf h}(\perp\wedge\perp) )+1 \\ & =\max(\max(\mbox{\sf h}(\perp),\mbox{\sf h}(\perp\wedge\perp) )+1,\max(\mbox{\sf h}(\perp),\mbox{\sf h}(\perp) )+1 )+1 \\ & =4. \end{align*} \)

Obserwacja 2.7

Dla \( T=T_0\wedge T_1 \) mamy

  • \( \mbox{\sf h}(T_i) < \mbox{\sf h}(T) \),
  • \( \mbox{\sf w}(T_i) < \mbox{\sf w}(T) \),
  • \( \vert T_i\vert < \vert T\vert \).

Wniosek 2.8
Drzewo \( \perp \) jest jedynym drzewem o wysokości \( 0 \).

Twierdzenie 2.9 [Zasada Indukcji dla drzew binarnych]

Gdy \( S\subseteq\mathbb{T} \) jest zbiorem drzew binarnych spełniającym warunki:

  • \( \perp\in S \),
  • jeśli \( T_0,T_1\in S \) to \( T_0\wedge T_1\in S \),

to \( S=\mathbb{T} \).

Dowód

Dla dowodu niewprost załóżmy, że w \( S \) nie ma wszystkich drzew. Zatem zbiór \( S'=\mathbb{T}-S \) jest niepusty. Tym samym niepusty jest też zbiór \( Z={\{ {\mbox{\sf h}(T) : T \in S'} \}\ } \) Na mocy założenia o \( S \) wiemy, że \( \perp\notin S' \), co wraz z Wnioskiem 2.8 implikuje, że \( 0\notin Z \).

Ponieważ \( Z \) jest niepusty, to na podstawie Zasady Minimum ma element najmniejszy, powiedzmy \( z \). Wiemy już, że \( z>0 \). Niech \( T\in S' \) poświadcza fakt, że \( z\in Z \), tzn. \( \mbox{\sf h}(T)=z>0 \). Ponownie z Wniosku 2.8 dostajemy \( T'\neq\perp \), czyli \( T'=T_0\wedge T_1 \) dla pewnych \( T_1,T_2 \). Z Obserwacji 2.7 mamy \( \mbox{\sf h}(T_0) < \mbox{\sf h}(T)=z \) oraz \( \mbox{\sf h}(T_1) < \mbox{\sf h}(T)=z \). Zatem minimalność \( z \) w \( S_0' \) daje \( \mbox{\sf h}(T_0),\mbox{\sf h}(T_1)\notin Z \), czyli \( T_0,T_1\notin S' \) i w konsekwencji \( T_0,T_1\in S \).

Ale wtedy, z założenia o zbiorze \( S \), dostajemy \( T=T_0\wedge T_1=T\in S \). Sprzeczność.

Zasada Indukcji dla drzew binarnych to przykład na to, że w strukturach zdefiniowanych rekurencyjnie można dowodzić przy pomocy zasady analogicznej do Zasady Indukcji. Poniżej przedstawiamy przykład używający tego narzędzia.

Obserwacja 2.10

Dla dowolnego drzewa binarnego \( T\in\mathbb{T} \) mamy:

  • \( \mbox{\sf h}(T) \le \mbox{\sf w}(T) \le \vert T\vert \),
  • \( \vert T\vert=2\cdot\mbox{\sf w}(T)-1 \).

Dowód

Niech \( S\subseteq\mathbb{T} \) będzie zbiorem drzew binarnych spełniających powyższe własności.

  • \( \mbox{\sf h}(\perp)=0 \le 1 =\mbox{\sf w}(\perp)= \vert\perp\vert \), oraz \( \vert\perp\vert=1=2\mbox{\sf w}(\perp)-1 \), czyli \( \perp\in S \).
  • W kroku indukcyjnym zakładamy, że \( T=T_0\wedge T_1 \) oraz że drzewa \( T_0,T_1 \) mają już opisane w Obserwacji własności. Wtedy


\( \begin{align*}\vert T_0\wedge T_1\vert & =\vert T_0\vert+\vert T_1\vert+1 =(2\mbox{\sf w}(T_0)-1)+(2\mbox{\sf w}(T_1)-1)+1 \\ & =2(\mbox{\sf w}(T_0)+\mbox{\sf w}(T_1))-1 \\ & =2\mbox{\sf w}(T_0\wedge T_1)-1. \end{align*} \)

Podobnie

\( \begin{align*}\mbox{\sf h}(T_0\wedge T_1) & =\max(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) )+1 \\ & \leq \max(\mbox{\sf w}(T_0),\mbox{\sf w}(T_1) )+1 \\ & \leq \mbox{\sf w}(T_0)+\mbox{\sf w}(T_1) \\ & =\mbox{\sf w}(T_0\wedge T_1), \end{align*} \)

gdzie ostatnia nierówność wynika bezpośrednio z faktu, że szerokość każdego drzewa wynosi co najmniej \( 1 \).