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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& 1 \\ s_{n} &=& n \cdot s_{n-1} \quad \textnormal{dla} \quad n\geqlant 1. \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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?

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned s_0 &=& \frac{1}{2} \\ s_{n} &=& n \cdot s_{n-1} \quad \textnormal{dla}\quad n\geq 1 \endaligned}

oraz

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a_0 + 0\cdot r = a_0 \quad\textnormal{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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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.

rys.wieże Hanoi-3 krażki

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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,\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}}}

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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned l_0&=&1,\\ l_{n+1}&=&l_n+n. \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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

foto, notka

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}{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.

Przykład

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

rys.prostokat-kratka 2xn

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$

     Rysunek: 1.6 Szkic na kartce

• Dla $n=2$ są już dwa takie sposoby:
  

- ustawiamy obie kostki poziomo, lub obie pionowo,
a zatem $d_2=2$.

     Rysunek: 1.7 Szkic na kartce

• Dla $n=3$ są trzy sposoby,

     Rysunek: 1.8 Szkic na kartce

• 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=0$).

Obserwacja 2.1

$f_0+f_1+\dots +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\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;

     Rysunek: 1.10 Szkic na kartce

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

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:

Parser nie mógł rozpoznać (nieznana funkcja „\alignedc”): {\displaystyle \alignedc_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(\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$:

Parser nie mógł rozpoznać (nieznana funkcja „\alignedF”): {\displaystyle \alignedF(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}

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.

foto, notka

Wniosek 2.4

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

Dowód

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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ż

$\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.$

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

foto, notka

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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_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ą.

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.

Przykład

Interpretacja graficzna kilku, małych drzew binarnych:

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ą

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbb{T} \ni T \mapsto \mbox{\sf h}(T) \in \mathbb{N} }

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

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf w}(\perp)=1} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf w}(T_0\wedge T_1)=\mbox{\sf w}(T_0)+\mbox{\sf w}(T_1)} .

Wysokość drzewa binarnego jest wyznaczona funkcją

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathbb{T} \ni T \mapsto \mbox{\sf h}(T) \in \mathbb{N} }

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

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(\perp)=0} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(T_0\wedge T_1)=\max\left(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) \right)+1} .

Przykład

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}

Przykład

Obserwacja 2.7

Dla $T=T_0\wedge T_1$ mamy

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(T_i)<\mbox{\sf h}(T)} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf w}(T_i)<\mbox{\sf 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle Z={\left\{ {\mbox{\sf h}(T) : T \in S'} \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. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(T_0)<\mbox{\sf h}(T)=z} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(T_1)<\mbox{\sf h}(T)=z} . Zatem minimalność $z$ w ${S_0}^{\prime }$ daje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(T_0),\mbox{\sf 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:

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(T) \le \mbox{\sf w}(T) \le \left\vert T\right\vert} ,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert T\right\vert=2\cdot\mbox{\sf w}(T)-1} .

Dowód

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

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf h}(\perp)=0 \le 1 =\mbox{\sf w}(\perp)= \left\vert\perp\right\vert} , oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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$.