Osoitamme induktion avulla, että $$\begin{equation*} \sum_{i=1}^n i = 1+2 + 3+\ldots +n = \frac{n(n+1)}2,\quad n\geq 1. \end{equation*}$$ Väite $P(n)$ on siis $\sum_{i=1}^n i= \frac{n(n+1)}2$ ja $n_0=1$.

• Väite $P(n_0)$ on sama kuin $1= \frac {1(1+1)}2$ mikä pitää paikkansa.
• Oletamme seuraavaksi, että $P(k)$ on tosi ja $k\geq 1$. Koska $P(k)$ pätee, niin $\sum_{i=1}^k i = \frac {k(k+1)}2$ mistä seuraa, että $$\sum_{i=1}^{k+1} i = \sum_{i=1}^k i+ (k+1)= \frac {k(k+1)}2+ (k+1) \\ =(k+1)\left(\frac{k}2+1\right )=\frac {(k+1)(k+2)}2 = \frac{(k+1)((k+1)+1)}{2},$$ joka taas merkitsee sitä, että $P(k+1)$ on tosi.
• Induktioperiaatteen nojalla toteamme, että $P(n)$ pätee kaikilla $n\geq 1$.

• Linja-autossa on 6 matkustajaa, joilla on valkoinen hattu ja 6 joilla on musta hattu ja kaikilla on hyvä ja samanlainen päättelykyky.
• Kukaan ei näe omaa hattuaan (eikä tiedä minkävärinen se on), mutta jokainen näkee kaikkien muiden hatut.
• Jokaiselle on annettu ohjeeksi, että jos ja kun hän tietää että hänellä on valkoinen hattu, hänen tulee astua ulos linja-autosta seuraavalla pysäkillä.
• Kuljettaja sanoo matkustajille, että ainakin yhdellä matkustajalla on valkoinen hattu.
• Kuudennella pysäkillä tämän jälkeen kaikki matkustajat, joilla on valkoinen hattu astuvat ulos linja-autosta.

Kysymyksiä: [+]

1. Mitä väliä on sillä, että kuljettaja sanoo, että "ainakin yhdellä matkustajalla on valkoinen hattu", kaikkihan sen näkevät? Lyhyt vastaus [+]
   Kaikki tietävät silloin myös, että kaikki tietävät, että kaikki tietävät jne. että ainakin yhdellä matkustajalla on valkoinen hattu.
2. Miksi juuri kuudennella pysäkillä? Lyhyt vastaus [+]
   Koska viidennellä, samoin neljännellä pysäkillä jne. kukaan ei astunut ulos.

Vastaus [+]

Jos alkuperäinen ongelma ei ratkea kannattaa valita tutkittavaksi jokin yksinkertaisempi versio:
Jos linja-autossa on vain yksi henkilö jolla on valkoinen hattu niin hän ei näe yhtään valkoista hattua ja kun kuljettaja sanoo, että ''ainakin yhdellä matkustajalla on valkoinen hattu'', hän ymmärtää, että hänellä on sellainen ja astuu ulos seuraavalla, eli ensimmäisellä, pysäkillä.

Jatk. [+]

Entä jos kahdella henkilöllä on valkoinen hattu?
Nyt kaikki tietävät että ''ainakin yhdellä matkustajalla on valkoinen hattu'' joten kumpikaan valkohattuisista matkustajista ei pysty suoraan päättelemään, että hänellä on valkoinen hattu eikä astu ulos ensimmäisellä pysäkillä mutta kun kuljettaja on tämän sanonut niin kaikki myös tietävät, että kaikki tietävät, että ''ainakin yhdellä matkustajalla on valkoinen hattu''. Eli ensimmäisen pysäkin jälkeen molemmat matkustajat, joilla on valkoinen hattu voivat päätellä, että toinen valkohattuinen myös näkee valkoisen hatun eli heillä molemmilla täytyy olla valkoinen hattu päässä ja siten astuvat ulos toisella pysäkillä.

Jatk. [+]

Yleinen tapaus induktiolla:
Olkoon $P(n)$ väite: Jokainen matkustaja päättelee oikein, että hän voi astua ulos $n$:nnellä pysäkillä jos ja vain jos hän näkee $n-1$ valkoista hattua kun tullaan tälle pysäkille.

Jos tämä väite pätee kaikilla $n\geq 1$ niin tästä seuraa, että jos linja-autossa on $m$ matkustajaa joilla on valkoinen hattu, he voivat kaikki astua ulos $m$:nnellä pysäkillä.

• Edellä näimme, että väite $P(1)$ (ja myös $P(2)$) on tosi.
• Oletamme, että väite $P(k)$ on tosi. Kun linja-auto on tulossa $k+1$:lle pysäkille niin jokainen matkustaja, joka näkee $k$ valkoista hattua tietää induktio-oletuksen nojalla, että nämä valkohattuiset matkustajat eivät ole nähneet ainoastaan $k-1$ valkoista hattua ennen edellistä pysäkkiä koska silloin he olisivat astuneet ulos ja näin ollen hänellä itsellään täytyy olla valkoinen hattu ja hän astuu ulos $k+1$:llä pysäkillä.
  Induktio-oletuksen nojalla linja-autossa ei voi olla $1,2,\ldots,k$ valkoista hattua linja-autossa kun se on tulossa $k+1$:lle pysäkille koska silloin valkohattuiset olisivat jo astuneet ulos. Mustahattuiset näkevät siis joko vähintään $k+1$ valkoista hattua tai ei yhtään tässä vaiheessa joten jos joku ei näe $k$ valkoista hattua hän ei voi päätellä että hänellä olisi valkoinen hattu ja hänen pitäisi astua ulos linja-autosta.
• Induktioperiaatteen nojalla toteamme, että $P(n)$ pätee kun $n\geq 1$.
       

           

       

• Väite: Jos $0< a< 1$ niin $a>a^2$.
  Suora todistus:
• $1-a >0$ koska $a<1$.
• $a\cdot (1-a) >0$ koska $a>0$ ja $(1-a)>0$.
• $a>a^2$ koska $a\cdot (1-a)= a- a^2>0$ jolloin $a=a-a^2+a^2>a^2$.
• Väite: Jos $0< a<1$ niin $\sqrt a> a$.
  Epäsuora todistus:
• Vastaoletus: $a\leq a^2$.
• $a\cdot (1-a) =a-a^2 \leq 0$ koska $a\leq a^2$.
• $a\leq 0$ koska $1-a>0$ kun $a<1$ ja kun jaamme positiivisellä luvulla epäyhtälö pysyy muuttumattomana.
• $a\leq 0$ on ristiriidassa oletuksen $a>0$ kanssa joten vastaoletus ei pidä paikkansa.

Olkoon $\mathcal P(X)$ joukon $X$ osajoukkojen joukko, eli $A\in \mathcal P(X)$ jos ja vain jos $A\subseteq X$. Jos nyt $X$ ja $Y$ ovat kaksi joukkoa niin onko toinen joukoista $\mathcal P(X)\setminus \mathcal P(Y)$ ja $\mathcal P(X\setminus Y)$ toisen osajoukko?

Vastaus [+]

• Koska tyhjä joukko on jokaisen joukon osajoukko niin $\emptyset \in \mathcal P(X\setminus Y)$. Samoin $\emptyset \in \mathcal P(Y)$ joten $\emptyset\notin \mathcal P(X)\setminus \mathcal P(Y)$. Tästä seuraa, ettei koskaan päde $\mathcal P(X\setminus Y) \subseteq \mathcal P(X)\setminus \mathcal P(Y)$ (eli aina pätee $\mathcal P(X\setminus Y) \not \subseteq \mathcal P(X)\setminus \mathcal P(Y)$).
• Jos $X=Y$ niin $\mathcal P(X)=\mathcal P(Y)$ joten $\mathcal P(X)\setminus \mathcal P(Y)=\emptyset \subseteq \{\emptyset\}= \mathcal P(\emptyset)= \mathcal P(X\setminus Y)$ koska tyhjä joukko on jokaisen joukon osajoukko ja tyhjän joukon ainoa osajoukko on tyhjä joukko.
• Mutta jos esimerkiksi $X=\{0,1\}$ ja $Y=\{0\}$ niin $\mathcal P(X)\setminus \mathcal P(Y)=\{\{0,1\},\{1\}\}$ mutta $\{0,1\}\notin \mathcal P(X\setminus Y)= \mathcal P(\{1\})=\{\{1\},\emptyset\}$ joten tässä tapauksessa $\mathcal P(X)\setminus \mathcal P(Y) \not \subseteq \mathcal P(X\setminus Y)$.
• Lopputulos on siis ettei koskaan päde $\mathcal P(X\setminus Y) \subseteq \mathcal P(X)\setminus \mathcal P(Y)$ mutta riippuu joukoista $X$ ja $Y$ päteekö $\mathcal P(X)\setminus \mathcal P(Y) \subseteq \mathcal P(X\setminus Y)$ vai ei.
• Huomaa myös, että väite $A\subseteq B$ on $\forall z\,(z\in A \to z\in B)$ joten sen negaatio on $\exists z (z\in A \And z\notin B)$ joten yksi esimerkki alkiosta $z$ jolle pätee $z\in A$ ja $z\notin B$ riittää osoittamaan että $A\not\subseteq B$.