Matematyka dyskretna 1/Wykład 2: Rekurencja

From Studia Informatyczne

Spis treści

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 \left\langle a_0, a_1, a_2, a_3, \ldots \right\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:


\aligned s_0 &= 1 \\ s_{n} &= n \cdot s_{n-1} \quad \textnormal{dla} \quad n\geq 1.  \endaligned


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


\aligned 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 \endaligned


Przykład

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


\aligned s_0 &= 0 \\ s_{n} &= n \cdot s_{n-1}\quad \textnormal{dla}\quad n\geq 1 \endaligned


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


\aligned s_0 &=\frac{1}{2} \\ s_{n} &= n \cdot s_{n-1} \quad \textnormal{dla}\quad n\geq 1 \endaligned


oraz


\aligned s_0 &= 1 \\ s_{n} &= n \cdot s_{n-2} \quad \textnormal{dla}\quad n\geq 2. \endaligned


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:


\aligned s_0 &= 0 \\ s_{n} &= s_{n-1}+2 \quad \textnormal{dla}\quad n\geq 1 \endaligned


ł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:


\aligned s_0 &= 1 \\ s_{n} &= 2\cdot s_{n-1} \quad \textnormal{dla}\quad n\geq 1 \endaligned


ł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\textnormal{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



Przykład (E.Lucas, 1883)

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

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\rightarrow C
Podobnie dla dwu krążków możemy postąpić: A\rightarrow B, \ \ A\rightarrow C, \ \ B\rightarrow 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\rightarrow C, \ \  A\rightarrow B, \ \ C\rightarrow B
  • przenosimy największy krążek z A na C:
A\rightarrow C
  • przenosimy krążki z B na C posługując się iglicą A:
B\rightarrow A, \ \ B\rightarrow C, \ \ A\rightarrow 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:


\aligned H_1 &= 1 \\ H_2 &=3 \\ H_3 &=7 \endaligned


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


\aligned H_1 &= 1 \\ H_{n} &= 2\cdot H_{n-1}+1 \quad \textnormal{dla}\quad n\geq 2 \endaligned


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:


\aligned a_0&=2,\\ a_{n+1}&=a_n^2. \endaligned


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




MD1-1.5.swf

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:

\aligned l_0&=1,\\ l_{n+1}&=l_n+n. \endaligned

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

\aligned 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}, \endaligned

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

Liczby Fibonacciego

Leonardo Fibonacci (1175-1250)Zobacz biografię
Enlarge
Leonardo Fibonacci (1175-1250)
Zobacz biografię

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


\aligned f_0&=0,\\ f_1&=1,\\ f_{n+2}&=f_n+f_{n+1}. \endaligned


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.



Domino-1.6-1.8.swf

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.



1.10

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.

image:End_of_proof.gif


AM1.M15.W.R01

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.

image:End_of_proof.gif

Twierdzenie 2.3 [wzór Eulera-Bineta]


f_n=\frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^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:


\aligned 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}} \endaligned


i ostatecznie dostajemy ciąg:


F(n) = \frac{1}{\sqrt{5}}\cdot\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{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:


\aligned 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}. \endaligned


image:End_of_proof.gif
Jan Kepler (1571-1630)Zobacz biografię
Enlarge
Jan Kepler (1571-1630)
Zobacz biografię

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\rightarrow\infty}\frac{f_{n+1}}{f_n}=\varphi.


Dowód


\aligned \lim_{n\rightarrow\infty}\frac{f_{n+1}}{f_n}&=\lim_{n\rightarrow\infty}\frac{\frac{1}{\sqrt{5}}(\varphi^{n+1}-(1-\varphi)^{n+1})}{\frac{1}{\sqrt{5}}(\varphi^n-(1-\varphi)^n)}\\ &=\lim_{n\rightarrow\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, \endaligned


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


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


jako że \left\vert\frac{1-\varphi}{\varphi}\right\vert<1.

image:End_of_proof.gif

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.


Giovanni Domenico Cassini (1625-1712)Zobacz biografię
Enlarge
Giovanni Domenico Cassini (1625-1712)
Zobacz biografię
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


\aligned f_n^2+f_{n-1}^2&=f_{2n-1},\\ f_{n+1}f_m+f_nf_{m-1}&=f_{m+n}. \endaligned


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



Interpretacja graficzna kilku, małych drzew binarnych

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 \left\vert T\right\vert \in \mathbb{N}


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

  • \left\vert\perp\right\vert=1,
  • \left\vert T_0\wedge T_1\right\vert=\left\vert T_0\right\vert+\left\vert T_1\right\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\left(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) \right)+1.


1-13

Przykład

\aligned\left\vert(\perp\wedge(\perp\wedge\perp))\wedge(\perp\wedge\perp)\right\vert&=\left\vert\perp\wedge(\perp\wedge\perp)\right\vert+\left\vert\perp\wedge\perp\right\vert+1\\ &=(\left\vert\perp\right\vert+\left\vert\perp\wedge\perp\right\vert+1)+(\left\vert\perp\right\vert+\left\vert\perp\right\vert+1)+1\\ &=(2+(\left\vert\perp\right\vert+\left\vert\perp\right\vert+1))+3+1\\ &=9. \endaligned


\aligned\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. \endaligned


\aligned\mbox{\sf h}((\perp\wedge(\perp\wedge\perp))\wedge(\perp\wedge\perp)) &=\max\left(\mbox{\sf h}(\perp\wedge(\perp\wedge\perp)),\mbox{\sf h}(\perp\wedge\perp) \right)+1\\ &=\max\left(\max\left(\mbox{\sf h}(\perp),\mbox{\sf h}(\perp\wedge\perp) \right)+1,\max\left(\mbox{\sf h}(\perp),\mbox{\sf h}(\perp) \right)+1 \right)+1\\ &=4. \endaligned




1-14

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),
  • \left\vert T_i\right\vert < \left\vert T\right\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={\left\{ {\mbox{\sf h}(T) : T \in S'} \right\}\ } 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ść.

image:End_of_proof.gif

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 \left\vert T\right\vert,
  • \left\vert T\right\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)= \left\vert\perp\right\vert, oraz \left\vert\perp\right\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


\aligned\left\vert T_0\wedge T_1\right\vert&=\left\vert T_0\right\vert+\left\vert T_1\right\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. \endaligned


Podobnie


\aligned\mbox{\sf h}(T_0\wedge T_1) &=\max\left(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) \right)+1 \\ &\leq \max\left(\mbox{\sf w}(T_0),\mbox{\sf w}(T_1) \right)+1 \\ &\leq \mbox{\sf w}(T_0)+\mbox{\sf w}(T_1) \\ &=\mbox{\sf w}(T_0\wedge T_1), \endaligned


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

image:End_of_proof.gif