Matematyka dyskretna 1/Wykład 2: 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 $⟨a_0,a_1,a_2,a_3,\dots ⟩$, - dla którego przepis na element $a_n$ wykorzystuje jakieś poprzednie elementy: $a_{n-1},a_{n-2},\dots$ 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 \dots \cdot 2\cdot 1.$

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

$\begin{array}{ccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& \cdots \\ n!& 1& 1& 2& 6& 24& 120& 720& 5040& 40320& \cdots \end{array}$

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

$\begin{array}{rl}{s}_0& =1\\ s_n& =n\cdot s_{n-1}\text{dla}n\ge 1.\end{array}$

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

$\begin{array}{rl}{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\\ \dots \end{array}$

Przykład

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

$\begin{array}{rl}{s}_0& =0\\ s_n& =n\cdot s_{n-1}\text{dla}n\ge 1\end{array}$

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

$\begin{array}{rl}{s}_0& =\frac{1}{2}\\ s_n& =n\cdot s_{n-1}\text{dla}n\ge 1\end{array}$

oraz

$\begin{array}{rl}{s}_0& =1\\ s_n& =n\cdot s_{n-2}\text{dla}n\ge 2.\end{array}$

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{array}{rl}{s}_0& =0\\ s_n& =s_{n-1}+2\text{dla}n\ge 1\end{array}$

ł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\text{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{array}{rl}{s}_0& =1\\ s_n& =2\cdot s_{n-1}\text{dla}n\ge 1\end{array}$

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

<flashwrap>file=Wieza hanoi.swf|size=small</flashwrap>

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\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{array}{rl}{H}_1& =1\\ H_2& =3\\ H_3& =7\end{array}$

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{array}{rl}{H}_1& =1\\ H_n& =2\cdot H_{n-1}+1\text{dla}n\ge 2\end{array}$

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

$1,3,7,15,31,63,127,\dots$

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 100000000000000000000$, co przy przenoszeniu jednego krążka na sekundę zajmie ponad $3000000000000$ lat, a przenosząc te krążki "komputerem" 3GHz potrzeba będzie... i tak ponad tysiąc lat!

Przykład

{{{3}}}

Load video

Local File

Local File might collect personal data.

Continue Dismiss

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:

$\begin{array}{rl}{l}_0& =1,\\ l_{n+1}& =l_n+n.\end{array}$

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

$\begin{array}{rl}{l}_n& =l_{n-1}+n=l_{n-2}+(n-1)+n=l_{n-3}+(n-2)+(n-1)+n=\dots \\ & =l_0+1+2+\dots +n=1+\frac{n(n+1)}{2},\end{array}$

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

Liczby Fibonacciego

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{\mathbb{N}}}$ zadany przez

$\begin{array}{rl}{f}_0& =0,\\ f_1& =1,\\ f_{n+2}& =f_n+f_{n+1}.\end{array}$

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

$\begin{array}{cccccccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14\\ 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.

Plik:Domino-1.6-1.8.mp4

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}{cccccccccccccccccccccccccccc}& & & & & & & & & & & & & & & & & & & & & & & & & & & \\ & & & & & & & & & & & & & & & & & & & & & & & & & & & \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+\dots +f_n=f_{n+2}-1.$

<flash>file=MD1-1.10.swf|width=350|height=150</flash>

<div.thumbcaption>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\le i\le 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}+\dots +f_0$ sposobów ułożenia prostokąta $(n+1)\times 2$ 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.

Load video

Local File

Local File might collect personal data.

Continue Dismiss

AM1.M15.W.R01

Obserwacja 2.2

$f_0^2+f_1^2+\dots +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+\dots +f_k^2=f_k\cdot f_{k+1}$ dodajmy obustronnie $f_{k+1}^2$ otrzymując

$f_0^2+f_1^2+\dots +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}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n].$

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{ℝ}}^{\mathbb{\mathbb{N}}}$.

Ćwiczenie: Przestrzen $F$ jest dwuwymiarowa o bazie $\phi ,1-\phi$

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{array}{rl}{c}_1& =\frac{f_1-f_0{x}_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_0{x}_1}{x_2-x_1}=\frac{1}{\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2}}=-\frac{1}{\sqrt{5}}\end{array}$

i ostatecznie dostajemy ciąg:

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

jako potencjalnego kandydata na ciąg Fibonacci'ego. W istocie potrzebujemy indukcyjnego dowodu, że $F(n)=f_n$. Dla wygody oznaczmy $\phi =\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}}{\phi }^0-\frac{1}{\sqrt{5}}(1-\phi {)}^0=\frac{1}{\sqrt{5}}-\frac{1}{\sqrt{5}}=0=f_0$,
  • $F(1)=\frac{1}{\sqrt{5}}\phi -\frac{1}{\sqrt{5}}(1-\phi )=\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 $\phi$ jak i $1-varphi$ spełniają zależność $x^{k+2}=x^{k+1}+x^k$:

$\begin{array}{rl}F(k+2)& =\frac{1}{\sqrt{5}}{\phi }^{k+2}-\frac{1}{\sqrt{5}}(1-\phi {)}^{k+2}\\ & =\frac{1}{\sqrt{5}}({\phi }^k+{\phi }^{k+1})-\frac{1}{\sqrt{5}}((1-\phi {)}^k+(1-\phi {)}^{k+1})\\ & =\frac{1}{\sqrt{5}}({\phi }^k-(1-\phi {)}^k)+\frac{1}{\sqrt{5}}({\phi }^{k+1}-(1-\phi {)}^{k+1})\\ & =F(k)+F(k+1)\\ & =f_k+f_{k+1}\\ & =f_{k+2}.\end{array}$

Jan Kepler (1571-1630)
Zobacz biografię

Liczba $\phi =\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

$\underset{n\to \mathrm{\infty }}{\lim }\frac{f_{n+1}}{f_n}=\phi .$

Dowód

$\begin{array}{rl}\underset{n\to \mathrm{\infty }}{\lim }\frac{f_{n+1}}{f_n}& =\underset{n\to \mathrm{\infty }}{\lim }\frac{\frac{1}{\sqrt{5}}({\phi }^{n+1}-(1-\phi {)}^{n+1})}{\frac{1}{\sqrt{5}}({\phi }^n-(1-\phi {)}^n)}\\ & =\underset{n\to \mathrm{\infty }}{\lim }\frac{\frac{1}{\sqrt{5}}\phi -\frac{1}{\sqrt{5}}(1-\phi )(\frac{1-\phi }{\phi }{)}^n}{\frac{1}{\sqrt{5}}-\frac{1}{\sqrt{5}}(\frac{1-\phi }{\phi }{)}^n}\\ & =\phi ,\end{array}$

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

$\underset{n\to \mathrm{\infty }}{\lim }{\left(\frac{1-\phi }{\phi }\right)}^n=0,$

jako że $\left|\frac{1-\phi }{\phi }\right|<1$.

Macierze liczb Fibonacci'ego

Rozważając specjalne kwadratowe macierze $2\times 2$ 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ę

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^m{A}^n=A^{m+n}$ dla dowolnej kwadratowej macierzy $A$, otrzymujemy:

Obserwacja 2.6

$\begin{array}{rl}{f}_n^2+f_{n-1}^2& =f_{2n-1},\\ f_{n+1}{f}_m+f_n{f}_{m-1}& =f_{m+n}.\end{array}$

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_0{x}_2}{x_1-x_2}{c}_2=\frac{s_1-s_0{x}_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_0{x}_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ą.

<flash>file=MD1-1.12.swf|width=350|height=200</flash>

<div.thumbcaption>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{𝕋}$. Wypisując konkretne drzewo binarne używamy nawiasów aby ujednoznacznic kolejność aplikacji reguł z definicji rekurencyjnej.

Wielkość drzewa binarnego jest wyznaczona funkcją

$\mathbb{𝕋}\ni T\mapsto \left|T\right|\in \mathbb{\mathbb{N}}$

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

• $|\perp |=1$,

• $|T_0\wedge T_1|=\left|T_0\right|+\left|T_1\right|+1$.

Szerokość drzewa binarnego jest wyznaczona funkcją

$\mathbb{𝕋}\ni T\mapsto \mathsf{h}(T)\in \mathbb{\mathbb{N}}$

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

• $\mathsf{w}(\perp )=1$,

• $\mathsf{w}(T_0\wedge T_1)=\mathsf{w}(T_0)+\mathsf{w}(T_1)$.

Wysokość drzewa binarnego jest wyznaczona funkcją

$\mathbb{𝕋}\ni T\mapsto \mathsf{h}(T)\in \mathbb{\mathbb{N}}$

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

• $\mathsf{h}(\perp )=0$,

• $\mathsf{h}(T_0\wedge T_1)=\max (\mathsf{h}(T_0),\mathsf{h}(T_1))+1$.

<flash>file=MD1-1.13.swf|width=200|height=200</flash>

<div.thumbcaption>1-13

Przykład

$\begin{array}{rl}|(\perp \wedge (\perp \wedge \perp ))\wedge (\perp \wedge \perp )|& =|\perp \wedge (\perp \wedge \perp )|+|\perp \wedge \perp |+1\\ & =(|\perp |+|\perp \wedge \perp |+1)+(|\perp |+|\perp |+1)+1\\ & =(2+(|\perp |+|\perp |+1))+3+1\\ & =9.\end{array}$

$\begin{array}{rl}\mathsf{w}((\perp \wedge (\perp \wedge \perp ))\wedge (\perp \wedge \perp ))& =\mathsf{w}(\perp \wedge (\perp \wedge \perp ))+\mathsf{w}(\perp \wedge \perp )\\ & =(\mathsf{w}(\perp )+\mathsf{w}(\perp \wedge \perp ))+(\mathsf{w}(\perp )+\mathsf{w}(\perp ))\\ & =(\mathsf{w}(\perp )+(\mathsf{w}(\perp )+\mathsf{w}(\perp ))+(\mathsf{w}(\perp )+\mathsf{w}(\perp ))\\ & =5.\end{array}$

$\begin{array}{rl}\mathsf{h}((\perp \wedge (\perp \wedge \perp ))\wedge (\perp \wedge \perp ))& =\max (\mathsf{h}(\perp \wedge (\perp \wedge \perp )),\mathsf{h}(\perp \wedge \perp ))+1\\ & =\max (\max (\mathsf{h}(\perp ),\mathsf{h}(\perp \wedge \perp ))+1,\max (\mathsf{h}(\perp ),\mathsf{h}(\perp ))+1)+1\\ & =4.\end{array}$

<flash>file=MD1-1.14.swf|width=350|height=250</flash>

<div.thumbcaption>1-14

Obserwacja 2.7

Dla $T=T_0\wedge T_1$ mamy

• $\mathsf{h}(T_i)<\mathsf{h}(T)$,

• $\mathsf{w}(T_i)<\mathsf{w}(T)$,

• $\left|T_i\right|<\left|T\right|$.

Wniosek 2.8

Drzewo $\perp$ jest jedynym drzewem o wysokości $0$.

Twierdzenie 2.9 [Zasada Indukcji dla drzew binarnych]

Gdy $S\subseteq \mathbb{𝕋}$ 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{𝕋}$.

Dowód

Dla dowodu niewprost załóżmy, że w $S$ nie ma wszystkich drzew. Zatem zbiór $S^{\prime }=\mathbb{𝕋}-S$ jest niepusty. Tym samym niepusty jest też zbiór $Z=\left\{\mathsf{h}(T):T\in S^{\prime }\right\}$ Na mocy założenia o $S$ wiemy, że $\perp \notin S^{\prime }$, 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^{\prime }$ poświadcza fakt, że $z\in Z$, tzn. $\mathsf{h}(T)=z>0$. Ponownie z Wniosku 2.8 dostajemy $T^{\prime }\ne \perp$, czyli $T^{\prime }=T_0\wedge T_1$ dla pewnych $T_1,T_2$. Z Obserwacji 2.7 mamy $\mathsf{h}(T_0)<\mathsf{h}(T)=z$ oraz $\mathsf{h}(T_1)<\mathsf{h}(T)=z$. Zatem minimalność $z$ w ${S_0}^{\prime }$ daje $\mathsf{h}(T_0),\mathsf{h}(T_1)\notin Z$, czyli $T_0,T_1\notin S^{\prime }$ 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{𝕋}$ mamy:

• $\mathsf{h}(T)\le \mathsf{w}(T)\le \left|T\right|$,

• $\left|T\right|=2\cdot \mathsf{w}(T)-1$.

Dowód

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

• $\mathsf{h}(\perp )=0\le 1=\mathsf{w}(\perp )=|\perp |$, oraz $|\perp |=1=2\mathsf{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{array}{rl}|T_0\wedge T_1|& =\left|T_0\right|+\left|T_1\right|+1=(2\mathsf{w}(T_0)-1)+(2\mathsf{w}(T_1)-1)+1\\ & =2(\mathsf{w}(T_0)+\mathsf{w}(T_1))-1\\ & =2\mathsf{w}(T_0\wedge T_1)-1.\end{array}$

Podobnie

$\begin{array}{rl}\mathsf{h}(T_0\wedge T_1)& =\max (\mathsf{h}(T_0),\mathsf{h}(T_1))+1\\ & \le \max (\mathsf{w}(T_0),\mathsf{w}(T_1))+1\\ & \le \mathsf{w}(T_0)+\mathsf{w}(T_1)\\ & =\mathsf{w}(T_0\wedge T_1),\end{array}$

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