Matematyka dyskretna 1/Wykład 1: Indukcja

Wprowadzenie

Matematyka dyskretna to zbiorcza nazwa działów matematyki, zajmujących się badaniem struktur nieciągłych, czyli skończonych lub co najwyżej przeliczalnych. Matematyka dyskretna stała się popularna w ostatnich latach dzięki zastosowaniom w informatyce, która w sposób naturalny zajmuje się jedynie strukturami skończonymi. Oto niektóre działy i tematy mające bardzo silny związek z matematyką dyskretną:

• logika,

• teoria mnogości,

• algebra struktur skończonych,

• algebra liniowa,

• kombinatoryka,

• teoria liczb,

• algorytmika,

• teoria informacji,

• złożoność obliczeniowa,

• rachunek prawdopodobieństwa,

• teoria grafów,

• teoria i częściowych porządków.

Wiele z powyższych zagadnień będzie omawiane w trakcie późniejszych kursów. Część już poznaliście w trakcie kursów:

• Logika i teoria mnogości,

• Algebra liniowa z geometrią analityczną,

do których będziemy się często odwoływać.

W trakcie kursu Matematyka dyskretna 1 i jego rozszerzenia Matematyka dyskretna 2 skoncentrujemy się natomiast na następujących zagadnieniach:

• Matematyka dyskretna 1:
  • kombinatoryka,
  • teoria grafów,
  • teoria liczb.

• Matematyka dyskretna 2:
  • zaawansowana teoria grafów,
  • teoria grup i ciał skończonych,
  • elementy kryptografii.

Notacja:

• Oznaczenia zbiorów:
  • $\mathbb{\mathbb{N}}$ - zbiór liczb naturalnych, czyli $\left\{0,1,2,\dots \right\}$. Tak, tak $0$ jest liczbą naturalną!
  • $\mathbb{\mathbb{Z}}$ - zbiór liczb całkowitych,
  • $\mathbb{\mathbb{Q}}$ - zbiór liczb wymiernych,
  • $\mathbb{ℝ}$ - zbiór liczb rzeczywistych,
  • $\mathbb{ℂ}$ - zbiór liczb zespolonych.

• Oznaczenia niektórych funkcji:
  • $\log x$ - to logarytm z liczby $x$ przy podstawie $10$,
  • $\lg x$ - to logarytm z liczby $x$ przy podstawie $2$,
  • $\lfloor x\rfloor$ - to największa liczba całkowita nie większa od $x$,
  • $\lceil x\rceil$ - to najmniejsza liczba całkowita nie mniejsza od $x$.

Podłoga:	$\mathbb{ℝ}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$	$\lfloor x\rfloor$ to największa liczba całkowita mniejsza lub równa $x$
Sufit:	$\mathbb{ℝ}\ni x\mapsto \lceil x\rceil \in \mathbb{\mathbb{Z}}$	$\lceil x\rceil$ to najmniejsza liczba całkowita większa lub równa $x$

I tak na przykład:

x	$\lfloor x\rfloor$	$\lceil x\rceil$
2	2	2
-2	-2	-2
2.5	2	3
-2.5	-3	-2
$\pi$	3	4

Przykład

Funkcji $\lfloor x\rfloor$ w połączeniu z funkcją logarytmu można użyć do wyliczania liczby cyfr liczby naturalnej $k$ zapisanej w układzie dziesiętnym. Jest to mianowicie

$\lfloor {\log }_{10}k\rfloor +1$

Podobnie

$\lfloor {\log }_{2}k\rfloor +1$

jest liczbą bitów potrzebnych do zapisania liczby naturalnej $k$.

W dalszym ciągu przyjmujemy, że jeśli nie jest napisane jakie wartości może przyjmować zmienna, to przyjmuje ona wartości z $\mathbb{\mathbb{N}}$.

Indukcja matematyczna

Indukcja matematyczna będzie przez nas używana jako metoda dowodzenia twierdzeń. Zazwyczaj są to twierdzenia dotyczące liczb naturalnych, ale - jak się jeszcze wielokrotnie przekonamy - wiele różnych twierdzeń, pozornie nie dotyczących liczb naturalnych, można sformułować tak, by można było je poddać dowodowi indukcyjnemu.

Poprawność indukcji matematycznej wynika z dobrego uporządkowania liczb naturalnych, czyli z następującej zasady minimum:

Zasada Minimum

Dowolny niepusty podzbiór $S\subseteq \mathbb{\mathbb{N}}$ zbioru liczb naturalnych ma w sobie liczbę najmniejszą.

Założenie, że zbiór $S$ nie jest pusty jest oczywiście konieczne, gdyż w zbiorze pustym nie istnieje żadna liczba.

Przykład

Pierwszy, znany dowód używający indukcji przedstawił Francesco Maurolio

zdjecie, zyciorys

w 1575 roku. Udowodnił on, że suma początkowych $n$ liczb nieparzystych wynosi $n^2$, tzn.:

$1+3+5+\dots +(2n-1)=n^2$

Istotnie, bardzo łatwo sprawdzić, że dla wybranej wartości $n$ jest to prawda. Na przykład:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned 1+3 &=& 4 = 2^2 \\ 1+3+5 &=& 9 = 3^2 \\ 1+3+5+7 &=& 16 = 4^2 \\ 1+3+5+7+9 &=& 25 = 5^2 \endaligned}

Ale jak pokazać, że jest to prawdą dla wszystkich liczb?

Z pomocą może nam tu przyjść Zasada Minimum. Gdyby rozważana równość nie zachodziła dla wszystkich liczb naturalnych, to zbiór

$S=\left\{n\in \mathbb{\mathbb{N}}:1+3+5+\dots +(2n-1)\ne n^2\right\}$

byłby niepusty, i zgodnie z Zasadą Minimum miałby liczbę najmniejszą. Ten najmniejszy kontrprzykład dla równości Maurolio, tzn. najmniejszą liczbę w zbiorze $S$, oznaczmy sobie przez $s$. Wiemy już, że $s\ne 1,2,3,4,5$, bo te liczby spełniają równości Maurolio, więc nie leżą w zbiorze $S$. Również $s\ne 0$ no oczywiście suma zerowej liczby nieparzystych liczb wynosi $0=0^2$, wiec $0\in ̸S$. Oznacza to, że $s>5$.

Z drugiej strony, skoro $s$ jest najmniejszym kontrprzykładem, to $s-1$ spełnia równość Maurolio więc:

$1+3+5+\dots +(2s-3)=(s-1{)}^2.$

Dodając teraz do obu stron równości kolejną liczbę nieparzystą, czyli $2s+1$, dostajemy

$1+3+5+\dots +(2s-3)+(2s-1)=(s-1{)}^2+(2s-1)=s^2-2s+1+2s-1=s^2,$

co oczywiście oznacza, że $s\in ̸S$. Tym samym $s$ nie może być najmniejszą liczbą w zbiorze kontrprzykładów, a więc w ogóle taki kontrprzykład istnieć nie może, i wobec tego wszystkie liczby naturalne spełniają równość Maurolio.

Rozumowanie przeprowadzone na przykładzie równości Maurolio wskazuje, że jeśli tylko $Z\subseteq \mathbb{\mathbb{N}}$ jest jakimś zbiorem liczb naturalnych,

• w którym jest zero, tzn. $0\in Z$,

• oraz $Z$ wraz z każdą liczbą naturalną $k$ zawiera również kolejną liczbę $k+1$, tzn. $\mathrm{\forall }k\in Zk+1\in Z$,

to wtedy $Z$ musi już zawierać wszystkie liczby naturalne, tzn. $Z=\mathbb{\mathbb{N}}$.

Przykład

Pokażemy, że dla dowolnej liczby naturalnej $n$ zachodzi:

$0+1+2+\dots +n=\frac{n(n+1)}{2}\text{<mrow data-mjx-texclass="ORD">dla</mrow>}n\ge 0$

Rysunek: 1.1 Szkic na kartce

Podobnie jak poprzednio łatwo udowodnić, iż jest to prawda dla wybranych, konkretnych $n$. W szczególności:

• dla $n=2$ mamy $1+2=3$ oraz $\frac{2\cdot (2+1)}{2}=3$,

• dla $n=5$ mamy $1+2+3+4+5=15$ oraz $\frac{5\cdot (5+1)}{2}=15$,

• dla $n=14$ mamy $1+2+\dots +14=105$ oraz $\frac{14\cdot (14+1)}{2}=105$.

Jednak te wszystkie równości nie dowodzą, iż jest to prawda dla dowolnego $n\in \mathbb{\mathbb{N}}$. Żadnym skończonym ciągiem sprawdzeń nie jesteśmy w stanie uzasadnić tej równości dla wszystkich liczb naturalnych z osobna, gdyż jest ich zbyt wiele. Z pomocą przychodzi jednak schemat rozumowania indukcyjnego zaproponowany powyżej:

Niech

$Z=\left\{n\in \mathbb{\mathbb{N}}:0+1+2+\dots +n=\frac{n(n+1)}{2}\right\}.$

Wtedy

• $0\in Z$, bo $0=\frac{0\cdot (0+1)}{2}$,

• nadto, gdy $k\in Z$, tzn.

$0+1+2+\cdots +(k-1)+k=\frac{k(k+1)}{2},$

to, badając, czy $k+1\in Z$ rozważamy sumę

$\begin{array}{rcccl}0+1+2+\cdots +k+(k+1)& =& [0+1+2+\cdots +k]& +& (k+1)\\ [1,5ex]& =& \left[\frac{k(k+1)}{2}\right]& +& (k+1)\\ [1,5ex]& =& \frac{k(k+1)+2(k+1)}{2}& & \\ [1,5ex]& =& \frac{(k+1)(k+2)}{2}& & \\ [1,5ex]& =& \frac{(k+1)((k+1)+1)}{2}& & \end{array}$

co świadczy o tym, że $k+1\in Z$.

A stąd już możemy wnosić, podobnie jak w przypadku równości Maurolio, że $Z=\mathbb{\mathbb{N}}$.

Przykład

Niech

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Z={\left\{ {n\in\mathbb{N} : 0^2+1^2+2^2+3^2+ \cdots + (n-1)^2 +n^2 = \frac{n(n+1)(2n+1)}{6} } \right\}\}. }

Jeśli pokażemy, że $Z=\mathbb{\mathbb{N}}$, to dostaniemy ważny wzór na sumę kolejnych kwadratów.

Oczywiście $0\in Z$.

Nadto, gdy $k\in Z$, to aby stwierdzić czy $k+1$ jest w $Z$ rozważamy sumę

$\begin{array}{rcccl}{0}^2+1^2+2^2+\cdots +k^2+(k+1{)}^2& =& [0^2+1^2+2^2+\cdots +k^2]& +& (k+1{)}^2\\ [1,5ex]& =& \left[\frac{k(k+1)(2k+1)}{6}\right]& +& (k+1{)}^2\\ [1,5ex]& =& \frac{k(k+1)(2k+1)+6(k+1{)}^2}{6}\\ [1,5ex]& =& \frac{(k+1)[k(2k+1)+6(k+1)]}{6}\\ [1,5ex]& =& \frac{(k+1)[2k^2+7k+6]}{6}\\ [1,5ex]& =& \frac{(k+1)[(k+2)(2k+3)]}{6}\\ [1,5ex]& =& \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}& & \end{array}$

co świadczy o tym, że $k+1\in Z$.

Przykład

Można zauważyć, że funkcja $n\mapsto n^2$ rośnie wolniej niż $n\mapsto 2^n$. Co prawda dla początkowych wartości mamy

$n$	0	1	2	3	4	5	6	7	8	...
$n^2$	0	1	4	9	16	25	36	49	64	...
$2^n$	1	2	4	8	16	32	64	128	256	...

i zachowanie tych dwu funkcji nie jest zdecydowane, ale już dla większych wartości $n$, liczba $2^n$ znacznie dominuje $n^2$. }}

Często, tak jak w powyższym przykładzie, pewna własność nie dotyczy wszystkich liczb naturalnych, ale prawie wszystkich, tzn. wszystkich poza być może pewną skończoną liczba wartości początkowych. Wtedy z pomocą przychodzi już następujące sformułowanie Zasady Indukcji Matematycznej.