Indukce je jednou z metod matematického důkazu, který umožňuje stanovit věrnost jistému tvrzení pro všechna přirozená čísla. Základní myšlenkou indukce je dokázat, že tvrzení platí pro první přirozené číslo, a poté ukázat, že pokud tvrzení platí pro určité číslo, bude platit i pro další číslo.
K prokázání indukčního tvrzení je třeba provést dva kroky. Nejprve zkontrolujte základní případ, to znamená zajistit, aby tvrzení platilo pro první přirozené číslo. Za druhé, provést indukční krok, který spočívá v důkazu, že pokud tvrzení platí pro určité číslo, bude platit i pro další číslo.
Při provádění dvou indukčních kroků lze tedy prokázat, že tvrzení platí pro všechna přirozená čísla. Pomocí této metody je možné řešit různé úkoly, které vyžadují prokázat věrnost tvrzení definovaným pro všechna přirozená čísla. Indukce se často používá k prokázání vzorců a tvrzení v algebře, kombinatorice a dalších oblastech matematiky.
Indukční důkaz
Indukční důkaz se skládá ze dvou kroků: základního kroku a indukčního kroku.
Základní krok: V základním kroku ověřujeme pravdivost tvrzení pro první přirozené číslo (obvykle pro číslo 1 nebo 0).
Indukční krok: V indukčním kroku předpokládáme, že tvrzení je pravdivé pro nějaké přirozené číslo k a dokazujeme, že platí pro další číslo k+1.
Indukční důkaz tedy umožňuje tvrdit, že tvrzení platí pro všechna přirozená čísla, počínaje základním případem.
Použití indukčního důkazu šetří čas a úsilí, zejména při dokazování tvrzení, která popisují vzorce nebo vlastnosti všech přirozených čísel.
Poznámka: Indukční důkaz je jedním z hlavních nástrojů matematického důkazu a je široce používán v různých oblastech, včetně algebry, analýzy, kombinatoriky a diskrétní matematiky.
Indukční základna
- Pro přirozené číslo 1 je tvrzení dokázáno identicky, protože součet prvního přirozeného čísla je roven samotnému číslu: 1 = 1.
- Nechť tvrzení platí pro nějaké přirozené číslo k, tj. součet prvních k přirozených čísel je k (k + 1)/2. To platí i pro číslo k + 1.
- Součet prvních k + 1 přirozených čísel se rovná součtu prvních k čísel a čísla k + 1:
1 + 2 + 3 + . + k + (k + 1) = k(k + 1)/2 + (k + 1)
- Zjednodušíme výraz:
Tvrzení tedy platí i pro číslo k + 1, které doplňuje indukční důkaz.
Indukční předpoklad
Formálně lze indukční předpoklad zaznamenat následovně:
Nechť P (n) je tvrzení závislé na n, které je třeba prokázat.
1. Indukční základna: předpokládáme, že tvrzení P(n) platí pro určitou pevnou hodnotu n.
2. Indukční krok: Předpokládáme, že tvrzení P(k) platí pro určitou hodnotu k, a dokazujeme, že z toho vyplývá, že tvrzení P(K+1) je pravdivé.
Indukční předpoklad nám tedy umožňuje spojit věrnost tvrzení pro jednu hodnotu n s jeho věrností pro další hodnotu.
Indukční krok
- Indukční základna: Tvrzení platí pro počáteční hodnotu, obvykle pro číslo 1.
- Krok indukce: ukázat, že pokud tvrzení platí pro určité číslo n, platí to i pro n + 1.
Pro začátek testujeme indukční základnu, tedy tvrzení pro n = 1. Pokud je indukční základna spuštěna, můžeme přejít k druhému kroku.
V indukčním kroku předpokládáme, že tvrzení platí pro určité číslo n a dokazujeme, že platí pro n + 1. Zde použijeme indukční předpoklad k odvození nového tvrzení.
Nakonec ukážeme, že tvrzení platí pro všechna přirozená čísla, počínaje indukční základnou a konče indukčním krokem pro každé další číslo. To stačí k prokázání pravdivosti tohoto tvrzení.