Definicja rekurencyjna (indukcyjna):
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 \mathrm{dla} \quad n\geq 1. \end{align*} \)
Ponieważ pierwszy wyraz jest zadany, to możemy kolejno obliczać:
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 \mathrm{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 \mathrm{dla}\quad n\geq 1 \end{align*} \)
oraz
\( \begin{align*} s_0 & = 1 \\ s_{n} & = n \cdot s_{n-2} \quad \mathrm{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.
Przykład
W ciągu zadanym poprzez równania:
\( \begin{align*} s_0 & = 0 \\ s_{n} & = s_{n-1}+2 \quad \mathrm{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 \)
Przykład
W ciągu zadanym poprzez równania:
\( \begin{align*} s_0 & = 1 \\ s_{n} & = 2\cdot s_{n-1} \quad \mathrm{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 \mathrm{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. \)
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:
Mnisi pracują od zarania dziejów dzień i noc ... .Ile czasu im to zajmie?
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 \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:
\( A \rightarrow C, \ \ A \rightarrow B, \ \ C \rightarrow B \)
\( A \rightarrow C \)
\( 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:
\( \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:
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 \mathrm{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.
W tym momencie możemy pokusić się o zgadywanie i przypuścić, że \( l_n=2^n \). Jednakże
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:
Ponownie rozwiążemy równanie rozwijając je:
gdzie ostatnia równość wynika z - już udowodnionego - wzoru na sumę kolejnych liczb naturalnych.
Wszystkie wyrazy ciągu, oprócz pierwszych dwu, są sumą dwu poprzednich elementów. Oto kilka pierwszych wartości ciągu Fibonacciego:
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 \)?
Oznaczmy, tę liczbę przez \( d_n \) w zależności od \( n \).
- ustawiamy obie kostki poziomo, lub obie pionowo,
a zatem \( d_2=2 \).
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:
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 \):
co kończy dowód kroku indukcyjnego.
Twierdzenie 2.3 [wzór Eulera-Bineta]
Dowód
Rozważmy równanie:
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:
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[(\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n}], \)
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} \).
\( \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
Dowód
gdzie ostatnia równość wynika z faktu, iż
jako że \( \vert\frac{1-\varphi}{\varphi}\vert < 1 \).
Rozważając specjalne kwadratowe macierze \( 2\times2 \) liczb Fibonacci'ego postaci
łatwo zauważamy, że
Ponieważ równocześnie:
to łatwo indukcyjnie łatwo udowodnić, że
\( \bigg [ \begin{array} {cc} f_{n+1} & f_n \\ f_n & f_{n-1} \end{array} \bigg ] = \bigg [ \begin{array} {cc} 1 & 1 \\ 1 & 0 \end{array} \bigg ]^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*} \)
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}. \)
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:
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ą
zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:
Szerokość drzewa binarnego jest wyznaczona funkcją
zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:
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:
Przykład
Obserwacja 2.7
Dla \( T=T_0\wedge T_1 \) mamy
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:
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:
Dowód
Niech \( S\subseteq\mathbb{T} \) będzie zbiorem drzew binarnych spełniających powyższe własności.
\( \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 \).