5. Indukcja i rekurencja

5.1. Indukcja.

Niech dla \(n\in \mathbb{N}\), \(T(n)\) będzie zdaniem określającym pewną własność liczb naturalnych.

Zasada indukcji. Załóżmy, że

• istnieje \(n_0\in \mathbb{N}\) takie że \(T(n_0)\) jest prawdziwe;

• z faktu, że \(T(n)\) jest prawdziwe dla \(n\geq n_0\) wynika, że \(T(n+1)\) jest prawdziwe.

Wtedy zdanie \(T(n)\) jest prawdziwe dla każdego \(n\geq n_0 .\)

Zasada silnej indukcji. Załóżmy, że

• istnieje \(n_0\in \mathbb{N}\) takie że \(T(n_0)\) jest prawdziwe;

• z faktu, że \(T(n_0), T(n_0+1),\ldots T(n-1), T(n)\) są prawdziwe wynika, że \(T(n+1)\) jest prawdziwe.

Wtedy zdanie \(T(n)\) jest prawdziwe dla każdego \(n\geq n_0 .\)

Zasada minimum. Każdy niepusty podzbiór liczb naturalnych zawiera liczbę najmniejszą.

Ciągi zadane rekurencyjnie. Ciągi liczbowe o wyrazach rzeczywistych można określać przez podanie dokładnej wartości początkowych wyrazów ciągu oraz wzoru na wyraz ogólny zależny od kilku wyrazów poprzedzających. Niektóre rekurencje bardzo łatwo zamienić na wzór jawny.

Przykład 5.7

Niech ciąg \((a_n)\) będzie zdefiniowany następująco:

\[a_0=a\in\mathbb{R}, \quad a_n=\frac{a_{n-1}}{2a_{n-1}+1}.\]

Stąd

\[a_0=\frac{a_{0}}{0a_{0}+1}, \; a_1=\frac{a_{0}}{2a_{0}+1}, \; a_2=\frac{a_{1}}{2a_{1}+1}=\frac{\frac{a_{0}}{2a_{0}+1}}{\frac{2a_{0}}{2a_{0}+1}+1}=\frac{a_{0}}{4a_{0}+1}, \; a_3=\frac{a_{2}}{2a_{2}+1}=\frac{\frac{a_{0}}{4a_{0}+1}}{\frac{2a_{0}}{4a_{0}+1}+1}=\frac{a_{0}}{6a_{0}+1}\]

Przypuśćmy, że wyraz ogólny ciągu ma postać:

\[a_n=\frac{a_{0}}{2na_{0}+1}.\]

Wtedy dla \(n=0\) mamy \(a_0=a\) oraz na mocy założenia indukcyjnego otrzymujemy:

\[a_{n+1}=\frac{a_{n}}{2a_{n}+1}=\frac{\frac{a_{0}}{2na_{0}+1}}{2\frac{a_{0}}{2na_{0}+1}+1}=\frac{a_0}{2a_0+2na_0+1}=\frac{a_0}{2(n+1)a_0+1},\]

co na mocy zasady indukcji matematycznej potwierdza trafność wzoru \eqref{prz}.

Zazwyczaj jednak znalezienie wzoru jawnego dla ciągu zadanego rekurencyjnie nie jest rzeczą prostą. Jedna z klasycznych metod rozwiązywania rekurencji dotyczy tzw. rekurencji liniowych.

5.2. Rekurencje liniowe

Metoda umożliwia rozwiązywanie zależności rekurencyjnych, w których każdy wyraz jest wyrażony przez sumę stałych wielokrotności ustalonej liczby poprzedzających wyrazów. Przedstawiona poniżej metoda dotyczy przypadku, gdy zależność rekurencyjna jest związana z dwoma poprzedzającymi wyrazami.

Niech będą zadane \(a_0,a_1\in \mathbb{R}\) oraz niech \(a_2,a_3,\ldots\) będą określone zależnością rekurencyjną:

\[a_n=Aa_{n-1}+Ba_{n-2},\quad n>1,\]

gdzie \(A\) i \(B\) są stałymi rzeczywistymi. Niech \(\alpha, \beta\) będą pierwiastkami równania kwadratowego

\[x^2=Ax+B\]

zwanego równaniem charakterystycznym.

Twierdzenie 5.7

Jeżeli \(\alpha\neq\beta\in \mathbb{R}\), to istnieją stałe \(c,d\in\mathbb{R}\) takie, że

\[a_n=c\alpha^n+d\beta^n, \quad \forall n\geq 0\]

Jeżeli \(\alpha=\beta\in\mathbb{R}\), to istnieją stałe \(c,d\in\mathbb{R}\) takie, że

\[a_n=(c+dn)\alpha^n, \quad \forall n\geq 0\]

Jeżeli \(\alpha=r(\cos\varphi+i\sin\varphi)\) jest zespolonym pierwiastkiem równania charakterystycznego, to istnieją stałe \(c,d\in\mathbb{R}\) takie, że

\[a_n=r^n(c\cos n\varphi+d\sin n\varphi), \quad \forall n\geq 0\]

Dowód. Niech \(\alpha\) i \(\beta\) będą dwoma różnymi pierwiastkami równania kwadratowego \(x^2=Ax+B\), czyli \(\alpha^2=A\alpha+B\) oraz \(\beta^2=A\beta+B .\) Zauważmy, że dla dowolnych stałych \(c\) i \(d\), ciąg o wyrazach \(a_n=c\alpha^n+d\beta^n\) spełnia zależność \eqref{rek}:

\[\begin{split}&Aa_{n-1}+Ba_{n-2}=A(c\alpha^{n-1}+d\beta^{n-1})+B(c\alpha^{n-2}+d\beta^{n-2})=\\ &c\alpha^{n-2}(A\alpha+B)+d\beta^{n-2}(A\beta+B)=c\alpha^{n-2}\alpha^2+d\beta^{n-2}\beta^2=c\alpha^{n}+d\beta^{n}=a_n.\end{split}\]

Stałe \(c\) i \(d\) wybieramy tak, aby wzór \eqref{rek} zachodził w przypadkach dla \(n=0\) oraz \(n=1\), tzn. by

\[c+d=c\alpha^0+d\beta^0=a_0\quad oraz \quad c\alpha+b\beta=a_1.\]

Ponieważ \(\alpha\neq\beta\), układ ma jednoznaczne rozwiązanie.

Dowody w dwóch pozostałych przypadkach przebiegają podobnie.

5.3. Zadania na zajęcia

Ćwiczenie 5.6

Udowodnić indukcyjnie, że dla każdego \(n\in \mathbb{N}++\):

• \(1\cdot 1!+2\cdot 2!+3\cdot 3!+\ldots + n\cdot n!=(n+1)!-1\)

• \((1+x)^n \geq 1+nx\), dla \(x>-1\) (nierówność Bernoulliego)

• \(8|(11^n-3^n)\)

Ćwiczenie 5.7

Udowodnić, że dla dowolnego \(n\)-elementowego zbioru \(X\), jego zbiór potęgowy \(2^X\) ma \(2^n\) elementów.

Ćwiczenie 5.8

Udowodnić za pomocą rekurencji, że otrzymany wzór jest poprawny: \(a_1=0\), \(a_2=5\) oraz \(a_{n}=7a_{n-1}-12a_{n-2}\), dla \(n\geq 2 .\)

Ćwiczenie 5.9

Udowodnić za pomocą rekurencji, że otrzymany wzór jest poprawny: \(a_{n+2}=6a_{n+1}-9a_n\), dla \(a_0=3\) oraz \(a_1=6 .\)

5.4. Zadania dodatkowe

Ćwiczenie 5.10

Jakie kwoty można odliczyć za pomocą monet o nominałach 3 i 5?

Ćwiczenie 5.11

Udowodnić, że aby połamać czekoladę o wymiarach \(p\) na \(r\) tak, aby były same kawałki 1 na 1 potrzeba \(p\cdot r -1\) złamań oraz że ta liczba nie zależy od sposobu łamania.

Ćwiczenie 5.12

Liczby Fermata: \(F_n=2^{2^n}+1\) dla \(n\geq 0 .\) Udowodnić, że dla każdego \(n\geq 1\), \(F_n=F_0F_1\cdot \ldots \cdot F_{n-1}+2 .\)

Ćwiczenie 5.13

Wieża Hanoi. Dane są trzy pionowe paliki. Na pierwszy z nich nałożono \(n\) krążków, wszystkie różnej wielkości, ułożone tak, że na spodzie leży krążek o największym promieniu a wyżej krążki według malejących promieni. Zadanie polega na tym, aby przenieść wszystkie krążki na jeden z dwu pozostałych prętów, przestrzegając przy tym dwóch reguł:

• za każdym razem przenosimy tylko jeden krążek,

• krążek mniejszy leży zawsze nad większym.

Pokazać, że aby zrealizować to zadanie należy wykonać \(2^n-1\) przełożeń krążków i, że procedura ta jest optymalna, tzn. nie można osiągnąć celu za pomocą mniejszej liczby ruchów.

Ćwiczenie 5.14

Niech \(A=\{n\in\mathbb{N}: 2|(n^2-3n+3)\} .\) Wykazać, że jeśli \(n\in A\) to \(n+1\in A .\) Znaleźć dowolny element zbioru \(A .\)

Ćwiczenie 5.15

Udowodnimy indukcyjnie, że wszystkie koty są tego samego koloru.

Krok pierwszy: Weźmy jednego kota. Jest on tego samego koloru co on sam.

Krok indukcyjny: Załóżmy że każde \(n\) kotów jest tego samego koloru. Pokażemy, że wtedy każde \(n+1\) kotów jest tego samego koloru.

Weźmy \(n+1\) kotów. Bez pierwszego będzie ich \(n\), zatem są tego samego koloru na mocy założenia indukcyjnego. Bez ostatniego też jest ich \(n\), więc są tego samego koloru. Środkowe koty nie zmieniają koloru, więc wszystkie \(n+1\) muszą mieć ten sam kolor. Na podstawie indukcji matematycznej wykazaliśmy, że wszystkie koty mają ten sam kolor.

Jaki to kolor?

Ćwiczenie 5.16

Znaleźć wyraz ogólny ciągu \((a_n)\) zadanego rekurencyjnie \(a_0=1\), \(a_1=2\), \(a_n=\frac{a_{n-1}^2}{a_{n-2}}\), dla \(n\geq 2 .\)

Ćwiczenie 5.17

Znaleźć równanie rekurencyjne, które definiuje:

1. ciąg arytmetyczny o \(n\)-tym wyrazie \(a_n=a_0+n\cdot r\)

2. ciąg geometryczny o \(n\)-tym wyrazie \(b_n=a_0\cdot q^n\)

Informacja

Materiały na tej stronie przygotowała Agata Pilitowska.

Projekt „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.

Zadanie 7 pn. „Pilotażowa realizacja innowacyjnej ścieżki kształcenia obejmującej znaczny komponent zespołowych zajęć projektowych we wczesnej fazie studiów” realizowane w ramach projektu „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.