Matematyka dyskretna 1/Ćwiczenia 1: Indukcja

From Studia Informatyczne

Indukcja

Ćwiczenie 1

Uczniowie i uczennice pewnej klasy postanowili z okazji świąt obdarować się prezentami. Każdy miał wybrać dokładnie jedną osobę, której kupi skromny upominek. Okazało się, że wszyscy dostali jakiś prezent. Pokaż, że każdy dostał prezent wyłącznie od jednej osoby.

Wskazówka

Nie wiemy ilu uczniów jest w klasie. Oznacz więc tę liczbę przez \displaystyle n i zastosuj indukcję ze względu \displaystyle n . Sprowadź problem do sytuacji, w której klasa liczy jedynie \displaystyle n-1 uczniów.

Rozwiązanie

Zastosujmy indukcję ze względu na \displaystyle n . Dla \displaystyle n=1 rozważana sytuacja sprowadza się do tego, że uczeń sobie samemu sprawia prezent, więc otrzymuje prezent od jednej osoby. Rozważmy klasę złożoną z \displaystyle n>1 uczniów. Wybierzmy dowolnego ucznia, którego nazwiemy Kamil. Załóżmy, że dawał on prezent Antkowi, zaś otrzymał od Michała. Usuńmy z klasy Kamila wraz z jego prezentem, zaś prezent Michała dajmy Antkowi. Otrzymaliśmy więc klasę złożoną z \displaystyle n-1 uczniów, w której każdy otrzymał prezent. Z założenia indukcyjnego wynika, że każdy dostał prezent wyłącznie od jednej osoby. Nie trudno zauważyć, że jeżeli ponownie wprowadzi się Kamila do klasy i powróci do pierwotnego układu obdarowań w klasie, to nadal będzie zachowany warunek, że każdy dostaje prezent od jednej osoby.

Ćwiczenie 2

Udowodnij, że dla dowolnej liczby naturalnej \displaystyle n>0 , liczba \displaystyle 11^n-3^n jest podzielna przez \displaystyle 8 .

Wskazówka

Zastosuj rozumowanie indukcyjne ze względu na \displaystyle n . Zauważ ponadto, że


\displaystyle 11\cdot 11^n-3\cdot 3^n=11\cdot 11^n-11\cdot 3^n+8\cdot 3^n.


Rozwiązanie

Dowód przeprowadźmy indukcyjnie ze względu na \displaystyle n . Dla \displaystyle n=1 otrzymujemy:


\displaystyle 11^n-3^n=11^1-3^1=8,


co oczywiście jest podzielne przez \displaystyle 8 . Z kolei dla \displaystyle n>1 otrzymujemy następujący ciąg równości


\displaystyle \aligned 11^n-3^n&=11\cdot 11^{n-1}-3\cdot 3^{n-1}\\ &=11\cdot 11^{n-1}-11\cdot 3^{n-1}+8\cdot 3^{n-1}\\ &=11\cdot\left( 11^{n-1}-3^{n-1} \right)+8\cdot 3^{n-1} \endaligned


Z założenia indukcyjnego wynika, że \displaystyle 11^{n-1}-3^{n-1} jest podzielne przez \displaystyle 8 . W konsekwencji otrzymujemy, że \displaystyle 11\cdot\left( 11^{n-1}-3^{n-1} \right) jak i \displaystyle 8\cdot 3^{n-1} jest podzielne przez \displaystyle 8 , a więc i suma


\displaystyle 11\cdot\left( 11^{n-1}-3^{n-1} \right)+8\cdot 3^n=11^n-3^n


jest podzielna przez \displaystyle 8 , co kończy dowód.

Ćwiczenie 3

Znajdź zbiór tych liczb naturalnych, dla których zachodzi nierówność \displaystyle 5n\leq n^2-3 ? Odpowiedź uzasadnij.

Wskazówka

Zbadaj kilka początkowych wartości i na tej podstawie wysuń hipotezę. Następnie spróbuj ją uzasadnić indukcyjnie ze względu na \displaystyle n .

Rozwiązanie

Dla początkowych wartości \displaystyle n mamy:


\displaystyle  \begin{array} {|c|c|c|} \hline n & 5n & n^2-3\\ \hline \hline 0 & 0 & -3 \\ \hline 1 & 5 & -2 \\ \hline 2 & 10 & 1 \\ \hline 3 & 15 & 6 \\ \hline 4 & 20 & 13 \\ \hline 5 & 25 & 22 \\ \hline 6 & 30 & 33 \\ \hline 7 & 35 & 46 \\ \hline \vdots & \vdots & \vdots \\ \end{array}


Wydaje się więc, że \displaystyle 5n\leq n^2-3 zachodzi dla \displaystyle n\geq 6 . Dla \displaystyle n=6 dowodzona nierówność jest prawdziwa. Załóżmy więc, że \displaystyle n>6 . Przekształcając prawą stronę dowodzonej nierówności otrzymujemy, że


\displaystyle \aligned n^2-3&=\left( \left( n-1 \right)+1 \right)^2-3\\ &=\left( n-1 \right)^2+2\left( n-1 \right)+1-3\\ &=\left( n-1 \right)^2+2n-4. \endaligned


Na mocy założenia indukcyjnego mamy, że \displaystyle 5\left( n-1 \right)\leq \left( n-1 \right)^2-3 . Dostajemy więc


\displaystyle \aligned n^2-3&=\left( n-1 \right)^2+2n-4\\ &\geq 5\left( n-1 \right)+2n-4\\ &=5n+\left( 2n-9 \right). \endaligned


Założyliśmy, że \displaystyle n\geq 6 , więc \displaystyle 2n-9\geq0 , co kończy dowód.

Ćwiczenie 4

Niech \displaystyle A \subseteq \mathbb{N} będzie zbiorem wszystkich tych liczb naturalnych \displaystyle n , dla których liczba


\displaystyle n^2-3n+3


jest parzysta. Pokaż, że jeśli \displaystyle n\in A to i \displaystyle n+1\in A . Jakie liczby należą więc do \displaystyle A ?

Wskazówka

Zadanie jest podchwytliwe. Zauważ, że odwrotna implikacja, tzn. jeśli \displaystyle n\notin A to i \displaystyle n+1\notin A , jest także prawdziwa. Sprawdź czy do \displaystyle A należą początkowe liczby naturalne.

Rozwiązanie

Załóżmy, że \displaystyle n\in A , czyli że \displaystyle n^2-3n+3 jest liczbą parzystą. Rozważmy więc wyrażenie postaci


\displaystyle \aligned \left( n+1 \right)^2-3\left( n+1 \right)+3&=n^2+2n+1-3n-3+3\\ &=n^2-3n+3+2\left( n-1 \right). \endaligned


Wartość \displaystyle n^2-3n+3 jest parzysta na mocy założenia indukcyjnego, więc i \displaystyle n^2-3n+3+2\left( n-1 \right) jest parzysta, co implikuje, że \displaystyle n+1\in A .

Zauważmy jednak, że dla \displaystyle n\notin A ,

liczba \displaystyle n^2-3n+3 jest nieparzysta, i wobec tego również liczba


\displaystyle \left( n+1 \right)^2-3\left( n+1 \right)+3=n^2-3n+3+2\left( n-1 \right)


jest nieparzysta. Uzyskujemy w konsekwencji, że \displaystyle n+1 jest elementem \displaystyle A . Mamy więc dwie następujące implikacje


\displaystyle \aligned n\in A&\Rightarrow n+1\in A,\\ n\notin A&\Rightarrow n+1\notin A, \endaligned


co oczywiście sobie nie przeczy! Orzeka jedynie, że albo \displaystyle A=\emptyset , albo \displaystyle A=\mathbb{N} Odpowiedź czy liczby postaci \displaystyle n^2-3n+3 są parzyste tkwi wartościach początkowych. Po podstawieniu za \displaystyle n=0 otrzymujemy


\displaystyle n^2-3n+3=3,


co jednoznacznie orzeka, że \displaystyle A jest puste.

Ćwiczenie 5

Pokaż, że dla dowolnej liczby \displaystyle n\in\mathbb{N} zachodzi następująca równość:


\displaystyle \frac{1}{1\cdot 7}+\frac{1}{7\cdot 13}+\frac{1}{13\cdot 19}+\ldots+\frac{1}{\left( 6n-5 \right)\cdot\left( 6n+1 \right)}=\frac{n}{6n+1}.


Wskazówka

Zastosuj rozumowanie indukcyjne ze względu na \displaystyle n . W kroku indukcyjnym uprość lewą stronę równości używając założenia indukcyjnego.

Rozwiązanie

Dowód przeprowadzimy indukcyjnie ze względu na \displaystyle n . Załóżmy na początku, że \displaystyle n=1 , otrzymując w ten sposób że


\displaystyle \sum_{k=1}^n\frac{1}{\left( 6k-5 \right)\cdot\left( 6k+1 \right)}=\frac{1}{1\cdot 7}=\frac{n}{6n+1}.


Załóżmy więc, że dowodzona równość jest prawdziwa dla wszystkich wartości nie większych niż \displaystyle n . W przypadku tym korzystając z założenia indukcyjnego uzyskujemy:


\displaystyle \aligned \frac{1}{1\cdot 7}+\ldots+\frac{1}{\left( 6n-5 \right)\left( 6n+1 \right)}+\frac{1}{\left( 6n+1 \right)\left( 6n+7 \right)}&=\frac{n}{6n+1}+\frac{1}{\left( 6n+1 \right)\left( 6n+7 \right)}\\ &=\frac{n\left( 6n+7 \right)+1}{\left( 6n+1 \right)\left( 6n+7 \right)}\\ &=\frac{6n^2+7n+1}{\left( 6n+1 \right)\left( 6n+7 \right)}\\ &=\frac{n+1}{6\left( n+1 \right)+1}, \endaligned


co kończy dowód.

Ćwiczenie 6

Dla ciągu \displaystyle \left( A_0,A_1,A_2,\ldots \right) podzbiorów zbioru \displaystyle X , ciąg zbiorów \displaystyle \left( B_0,B_1,B_2,\ldots \right) zdefiniujmy poprzez:


\displaystyle \left\{ \aligned B_0&= A_0,\\ B_n&= B_{n-1} \div A_n\quad\textrm{dla}\ n\geq 1, \endaligned  \right.


gdzie \displaystyle \div oznacza różnicę symetryczną zbiorów. Udowodnij, że \displaystyle x\in B_n wtedy i tylko wtedy, gdy \displaystyle x\in X występuje w nieparzystej liczbie zbiorów spośród: \displaystyle \left\lbrace A_0,A_1,A_2,\ldots,A_n \right\rbrace .

Wskazówka

Przeprowadź indukcję ze względu na \displaystyle n .

Rozwiązanie

Dla początkowej wartości \displaystyle n=0 mamy, że element \displaystyle x\in X występuje nieparzystą liczbę razy w rodzinie \displaystyle \left\lbrace A_0 \right\rbrace wtedy i tylko wtedy, gdy \displaystyle x\in A_0=B_0 . Załóżmy więc, że \displaystyle n>0 . Rozważmy przypadek, gdy \displaystyle x\in X występuje nieparzystą liczbę razy w rodzinie zbiorów \displaystyle \left\lbrace A_0,A_1,A_2,\ldots,A_n \right\rbrace . Otrzymujemy w ten sposób dwa podprzypadki:

1. Element \displaystyle x występuje nieparzystą liczbę razy w rodzinie zbiorów \displaystyle \left\lbrace A_0,A_1,A_2,\ldots,A_{n-1} \right\rbrace oraz \displaystyle x \notin A_n .

  Z założenia indukcyjnego otrzymujemy, że  \displaystyle x\in B_{n-1} i co za tym idzie \displaystyle x\in B_{n-1} \div A_n= B_n .

2. Element \displaystyle x występuje parzystą liczbę razy w rodzinie zbiorów \displaystyle \left\lbrace A_0,A_1,A_2,\ldots,A_{n-1} \right\rbrace oraz \displaystyle x \in A_n .

  Z założenia indukcyjnego otrzymujemy, że  \displaystyle x\notin B_{n-1}, co implikuje ponownie, że  \displaystyle x\in B_{n-1} \div A_n= B_n.

W przypadku, gdy \displaystyle x\in X występuje parzystą liczbę razy w rodzinie zbiorów \displaystyle \left\lbrace A_0,A_1,A_2,\ldots,A_n \right\rbrace rozumowanie jest analogiczne.