Matematyka dyskretna 1/Ćwiczenia 1: Indukcja

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 $n$ i zastosuj indukcję ze względu $n$ . Sprowadź problem do sytuacji, w której klasa liczy jedynie $n-1$ uczniów.

Rozwiązanie

Zastosujmy indukcję ze względu na $n$ . Dla $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 $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 $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 $n>0$ , liczba $11^n-3^n$ jest podzielna przez $8$ .

Wskazówka

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

$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 $n$ . Dla $n=1$ otrzymujemy:

$11^n-3^n=11^1-3^1=8$,

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

$\begin{array}{rl}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 (11^{n-1}-3^{n-1})+8\cdot 3^{n-1}\end{array}$

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

$11\cdot (11^{n-1}-3^{n-1})+8\cdot 3^n=11^n-3^n$

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

Ćwiczenie 3

Znajdź zbiór tych liczb naturalnych, dla których zachodzi nierówność $5n\le 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 $n$ .

Rozwiązanie

Dla początkowych wartości $n$ mamy:

$\begin{array}{ccc}n& 5n& n^2-3\\ HLINE\; TBD0& 0& -3\\ 1& 5& -2\\ 2& 10& 1\\ 3& 15& 6\\ 4& 20& 13\\ 5& 25& 22\\ 6& 30& 33\\ 7& 35& 46\\ ⋮& ⋮& ⋮\\ \end{array}$

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

$\begin{array}{rl}{n}^2-3& ={((n-1)+1)}^2-3\\ & ={(n-1)}^2+2(n-1)+1-3\\ & ={(n-1)}^2+2n-4\end{array}$

Na mocy założenia indukcyjnego mamy, że $5(n-1)\le {(n-1)}^2-3$. Dostajemy więc

$\begin{array}{rl}{n}^2-3& ={(n-1)}^2+2n-4\\ & \ge 5(n-1)+2n-4\\ & =5n+(2n-9)\end{array}$

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

Ćwiczenie 4

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

$n^2-3n+3$

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

Wskazówka

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

Rozwiązanie

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

$\begin{array}{rl}{(n+1)}^2-3(n+1)+3& =n^2+2n+1-3n-3+3\\ & =n^2-3n+3+2(n-1).\end{array}$

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

Zauważmy jednak, że dla $n\notin A$ , liczba $n^2-3n+3$ jest nieparzysta, i wobec tego również liczba

${(n+1)}^2-3(n+1)+3=n^2-3n+3+2(n-1)$

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

$\begin{array}{rl}n\in A& \Rightarrow n+1\in A,\\ n\notin A& \Rightarrow n+1\notin A,\end{array}$

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

$n^2-3n+3=3$

co jednoznacznie orzeka, że $A$ jest puste.

Ćwiczenie 5

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

$\frac{1}{1\cdot 7}+\frac{1}{7\cdot 13}+\frac{1}{13\cdot 19}+\dots +\frac{1}{(6n-5)\cdot (6n+1)}=\frac{n}{6n+1}$

Wskazówka

Zastosuj rozumowanie indukcyjne ze względu na $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 $n$ . Załóżmy na początku, że $n=1$ , otrzymując w ten sposób że

$\sum _{k=1}^n\frac{1}{(6k-5)\cdot (6k+1)}=\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ż $n$ . W przypadku tym korzystając z założenia indukcyjnego uzyskujemy:

$\begin{array}{rl}\frac{1}{1\cdot 7}+\dots +\frac{1}{(6n-5)(6n+1)}+\frac{1}{(6n+1)(6n+7)}& =\frac{n}{6n+1}+\frac{1}{(6n+1)(6n+7)}\\ & =\frac{n(6n+7)+1}{(6n+1)(6n+7)}\\ & =\frac{6n^2+7n+1}{(6n+1)(6n+7)}\\ & =\frac{n+1}{6(n+1)+1},\end{array}$

co kończy dowód.

Ćwiczenie 6

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

$\{\begin{array}{rl}{B}_0& =A_0,\\ B_n& =B_{n-1}÷A_n\text{dla}n\ge 1,\end{array}$

gdzie $÷$ oznacza różnicę symetryczną zbiorów. Udowodnij, że $x\in B_n$ wtedy i tylko wtedy, gdy $x\in X$ występuje w nieparzystej liczbie zbiorów spośród: $\{A_0,A_1,A_2,\dots ,A_n\}$ .

Wskazówka

Przeprowadź indukcję ze względu na $n$ .

Rozwiązanie

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

1. Element $x$ występuje nieparzystą liczbę razy w rodzinie zbiorów $\{A_0,A_1,A_2,\dots ,A_{n-1}\}$ oraz $x\notin A_n$ .

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

2. Element $x$ występuje parzystą liczbę razy w rodzinie zbiorów $\{A_0,A_1,A_2,\dots ,A_{n-1}\}$ oraz $x\in A_n$ .

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

W przypadku, gdy $x\in X$ występuje parzystą liczbę razy w rodzinie zbiorów $\{A_0,A_1,A_2,\dots ,A_n\}$ rozumowanie jest analogiczne.