- Kombinatorika
- Halmazok, rendezett párok, leképezések
- Matematikai logika, ítéletkalkulus
- Gráfelméleti alapok
- Gráfok izomorfiája és síkbarajzolhatósága
- Gráfok bejárása és gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózatok
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Lineáris leképezések
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
- Sajátérték, sajátvektor, sajátfelbontás
- Teljes indukció
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák
- Mátrixok
- Lineáris egyenletrendszerek
- Determináns, adjungált, kvadratikus alakok
- Komplex számok
- Polinomok
- Interpolációs polinomok
- Csoportok, gyűrűk, testek
Teljes indukció
Teljes indukció
A teljes indukció olyan állítások bizonyítására alkalmas, melyek $n$ pozitív egész számtól függenek.
A teljes indukciós bizonyítás lépései:
1. lépés: Igazoljuk, hogy az állítás $n=1$ esetén vagy az első néhány $n$-re igaz.
2. lépés: Igazoljuk, hogy ha az állítás $n$-re igaz, akkor $n+1$ esetén is igaz.
Ezzel az állítást minden $n$ pozitív egész számra belátjuk.
Bizonyítsuk be, hogy $1+3+5+\dots + 2n-1 = n^2$ minden pozitív egész $n$ esetén.
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( 1\cdot 4 + 2\cdot 7 + \dots + n\cdot (3n+1) = n \cdot (n+1)^2 \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( \frac{1}{1\cdot 2} + \frac{1}{3 \cdot 4} + \dots + \frac{1}{(2n-1)2n)} = \frac{1}{n+1} + \frac{1}{n+2} + \frac{1}{n+3} + \dots + \frac{1}{2n} \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( 1\cdot 2 + 2\cdot 3 + \dots + n (n+1) = \frac{ n(n+1)(n+2)}{3} \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( \left( 1- \frac{1}{4} \right) \cdot \left( 1- \frac{1}{9} \right) \cdot \left( 1- \frac{1}{16} \right) \cdot \dots \cdot \left( 1 - \frac{1}{n^2} \right) = \frac{n+1}{2n} \)
Igazoljuk teljes indukcióval, hogy $n$ db. egyenes a síkot legfeljebb $ \frac{n^2+n+2}{2}$ részre osztja.
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( (2+1) \cdot (2^2+1) \cdot \dots \cdot \left( 2^{2^n} + 1 \right) = 2^{2^{n+1}} -1 \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( \frac{1}{2} \cdot \frac{3}{4} \cdot \frac{5}{6} \cdot \dots \cdot \frac{2n-1}{2n} \geq \frac{1}{2 \sqrt{n}} \)
Igazoljuk teljes indukcióval, hogy minden $n$ pozitív egész számra
\( \frac{n}{2} < 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \dots + \frac{1}{2^{n-1}} \)
Igazoljuk teljes indukcióval, hogy $n$ db. kör a síkot legfeljebb $ n^2-n+2 $ részre osztja.
Hogyan működik a teljes indukció, Domino-elv, Az indukciós feltevés, Mese a teljes indukcióról
