--- title: "Indukcja i rekurencja" lecture_number: 4 has_solutions: false has_exercises: true --- ```{include} ../_includes/sagecell-loader.md ``` # Indukcja i rekurencja ## 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. :::{prf:example} Niech ciąg $(a_n)$ będzie zdefiniowany następująco: ```{math} a_0=a\in\mathbb{R}, \quad a_n=\frac{a_{n-1}}{2a_{n-1}+1}. ``` Stąd ```{math} 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ć: ```{math} a_n=\frac{a_{0}}{2na_{0}+1}. ``` Wtedy dla $n=0$ mamy $a_0=a$ oraz na mocy założenia indukcyjnego otrzymujemy: ```{math} 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*. ## 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ą: ```{math} 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 ```{math} x^2=Ax+B ``` zwanego *równaniem charakterystycznym*. :::{prf:theorem} Jeżeli $\alpha\neq\beta\in \mathbb{R}$, to istnieją stałe $c,d\in\mathbb{R}$ takie, że ```{math} 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 ```{math} 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 ```{math} 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}: ```{math} &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. ``` Stałe $c$ i $d$ wybieramy tak, aby wzór \eqref{rek} zachodził w przypadkach dla $n=0$ oraz $n=1$, tzn. by ```{math} 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. ## Zadania na zajęcia ::::{exercise} :class: [exercise] 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)$ :::: ::::{exercise} :class: [exercise] Udowodnić, że dla dowolnego $n$-elementowego zbioru $X$, jego zbiór potęgowy $2^X$ ma $2^n$ elementów. :::: ::::{exercise} :class: [exercise] 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 .$ :::: ::::{exercise} :class: [exercise] 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 .$ :::: ## Zadania dodatkowe ::::{exercise} :class: [exercise] Jakie kwoty można odliczyć za pomocą monet o nominałach 3 i 5? :::: ::::{exercise} :class: [exercise] 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. :::: ::::{exercise} :class: [exercise] 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 .$ :::: ::::{exercise} :class: [exercise] 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. :::: ::::{exercise} :class: [exercise] 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 .$ :::: ::::{exercise} :class: [exercise] 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? :::: ::::{exercise} :class: [exercise] 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 .$ :::: ::::{exercise} :class: [exercise] 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$ :::: ```{include} ../_includes/titlepage-info.md ```