25. Tétel

Állítás: Tetszőleges $a, b \in \mathbb{R}^+$ (pozitív valós számok) esetén érvényes, hogy $\frac{a+b}{2} \ge \sqrt{ab}$, és az egyenlőség akkor és csak akkor teljesül, ha $a = b$.

Direkt bizonyítás: Induljunk ki egy minden valós számra igaz, ismert állításból. Tudjuk, hogy bármely valós szám négyzete nemnegatív. Írjuk fel ezt a $\sqrt{a} - \sqrt{b}$ (amely értelmezett, hiszen $a, b > 0$) valós számra:

$$(\sqrt{a} - \sqrt{b})^2 \ge 0$$

Végezzük el a négyzetre emelést a nevezetes azonosság alapján:

$$a - 2\sqrt{ab} + b \ge 0$$

Rendezzük át az egyenlőtlenséget (adjunk hozzá mindkét oldalhoz $2\sqrt{ab}$-t):

$$a + b \ge 2\sqrt{ab}$$

Osztjuk el mindkét oldalt $2$-vel, ami pozitív szám lévén nem változtatja meg az egyenlőtlenség irányát:

$$\frac{a+b}{2} \ge \sqrt{ab}$$

A bizonyítás során végig ekvivalens átalakításokat hajtottunk végre. Az egyenlőség pontosan akkor teljesül, ha a kiindulópontban $(\sqrt{a} - \sqrt{b})^2 = 0$, ami akkor és csak akkor igaz, ha $\sqrt{a} = \sqrt{b}$, azaz ha $a = b$. Q.E.D.

Állítás: Nem létezik olyan racionális szám, amelynek a négyzete $2$.

Indirekt bizonyítás: Tegyük fel az állítás ellenkezőjét, azaz hogy $\sqrt{2}$ racionális. Ekkor felírható két egész szám, $p$ és $q$ hányadosaként, ahol $q \neq 0$. Feltehetjük, hogy a törtet már a végtelenségig egyszerűsítettük, így $p$ és $q$ relatív prímek (legnagyobb közös osztójuk 1).

$$\sqrt{2} = \frac{p}{q}$$

Emeljük mindkét oldalt négyzetre, majd szorozzunk $q^2$-tel:

$$2 = \frac{p^2}{q^2} \implies 2q^2 = p^2$$

Mivel $q^2$ egy egész szám, a bal oldal páros. Ezért $p^2$-nek is párosnak kell lennie. Mivel csak páros egész szám négyzete páros, ez azt jelenti, hogy $p$ maga is páros. Írjuk fel $p = 2k$ alakban, ahol $k \in \mathbb{Z}$. Helyettesítsük ezt vissza az egyenletbe:

$$2q^2 = (2k)^2 \implies 2q^2 = 4k^2 \implies q^2 = 2k^2$$

Ez az egyenlet azt mutatja, hogy $q^2$ páros szám (hiszen $2$-szerese egy egész számnak), tehát $q$ maga is páros. Ugyanakkor korábban bebizonyítottuk, hogy $p$ is páros. Ez viszont ellentmondás, hiszen a feltételezésünk az volt, hogy $p$ és $q$ relatív prímek (nem lehet mindkettő páros, mert akkor mindkettő osztható lenne $2$-vel). Mivel az ellentmondást hibátlan logikai levezetéssel kaptuk, az eredeti feltételezésünk hamis volt. Tehát $\sqrt{2}$ irracionális. Q.E.D.

Állítás: Minden $n \in \mathbb{Z}^+$ esetén érvényes, hogy $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$.

Bizonyítás teljes indukcióval:

1. Alaplépés ($n=1$): Helyettesítsünk a képletbe 1-et.
Bal oldal: $1$. Jobb oldal: $\frac{1(1+1)}{2} = \frac{2}{2} = 1$. Az állítás $n=1$-re igaz.

2. Indukciós feltevés: Tegyük fel, hogy valamilyen $k \ge 1$ egész számra az állítás igaz. Ezt indukciós feltevésnek hívjuk: $$1 + 2 + \dots + k = \frac{k(k+1)}{2}$$

3. Indukciós lépés: Bizonyítsuk be az állítást $n = k+1$-re. Vizsgáljuk a bal oldalt $k+1$ tag esetén:

$$1 + 2 + \dots + k + (k+1)$$

Az első $k$ tag összegét az indukciós feltevés alapján behelyettesíthetjük:

$$= \left( \frac{k(k+1)}{2} \right) + (k+1)$$

Hozzuk közös nevezőre a kifejezést:

$$= \frac{k(k+1) + 2(k+1)}{2}$$

Emeljük ki a közös $(k+1)$ tényezőt a számlálóban:

$$= \frac{(k+1)(k+2)}{2} = \frac{(k+1)((k+1)+1)}{2}$$

Ezzel pontosan azt az alakot kaptuk, mintha az eredeti képletbe $n$ helyére $(k+1)$-et írtunk volna. A dominó-elv alapján, mivel $n=1$-re igaz, és minden lépésből következik a következő, az állítás minden pozitív egész számra igaz. Q.E.D.

Állítás: Bármely, legalább kétpontú egyszerű gráfban létezik legalább két azonos fokszámú csúcs.

Bizonyítás skatulyaelvvel:

Legyen a gráfunk pontjainak (csúcsainak) száma $n$, ahol $n \ge 2$. Mivel a gráf egyszerű (nincsenek többszörös élek és hurokélek), egyetlen csúcs sem köthető össze önmagával, és bármely két csúcs között legfeljebb egy él fut.

Ebből következik, hogy egy csúcs fokszáma (a ráfutó élek száma) minimum $0$ (izolált pont), és maximum $n-1$ (minden más ponttal össze van kötve). A lehetséges fokszámok halmaza tehát: $\{0, 1, 2, \dots, n-1\}$. Ez pontosan $n$ darab különböző lehetséges érték (ezek lesznek a "skatulyák").

De vegyük észre a következőt: egy egyszerű gráfban nem lehet egyszerre jelen olyan csúcs, amelynek a fokszáma $0$ (senkivel nincs összekötve) ÉS olyan csúcs, amelynek a fokszáma $n-1$ (mindenkivel, tehát a $0$ fokszámúval is össze van kötve). E kettő kizárja egymást.

Ez azt jelenti, hogy a gráf $n$ darab csúcsa ténylegesen csak $n-1$ féle fokszámot (skatulyát) vehet fel: vagy a $\{1, 2, \dots, n-1\}$ halmazból, vagy a $\{0, 1, \dots, n-2\}$ halmazból.

Van tehát $n$ darab csúcsunk (a "tárgyak"), amelyeket legfeljebb $n-1$ darab lehetséges fokszám-skatulyába kell besorolnunk. A skatulyaelv értelmében, mivel több a tárgy ($n$), mint a skatulya ($n-1$), legalább egy skatulyába minimum két csúcsnak kell kerülnie. Tehát biztosan van legalább két azonos fokszámú csúcs a gráfban. Q.E.D.