Důkaz rozborem případů

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Důkaz rozborem případů neboli dokonalá indukce nebo důkaz hrubou silou je metoda matematického důkazu založená na tom, že dokazované tvrzení se rozpadne na konečný počet dílčích případů a důkaz je podán zvlášť pro každý z těchto dílčích případů. Důkaz tedy sestává ze dvou fází:

  1. Dokáže se, že seznam dílčích případů je vyčerpávající, tedy že každá instance tvrzení se dá zahrnout aspoň do jednoho z nich.
  2. Pro každý z dílčích případů se zvlášť provede důkaz tvrzení.

Příklad: Dokažme tvrzení

Je-li číslo m třetí mocninou nějakého přirozeného čísla, pak se neliší o víc než o jednu od nějakého přirozeného násobku devíti.

Označme jako n přirozené číslo, jehož je m třetí mocninou. Každé n je buď a) samo násobkem tří, nebo b) je o jednu vyšší než nějaký přirozený násobek tří, nebo konečně c) je o jednu nižší než nějaký přirozený násobek tří. Tyto tři kategorie odpovídají třem možným zbytkům po dělení přirozeného čísla třemi, tedy 0, 1 a 2, takže pokrývají všechny možnosti. Pro každou z těchto tří kategorií n zvlášť dokážeme uvedené tvrzení.

a) Je-li n násobkem tří, lze ho napsat jako 3p, a pak n3 = 27p3, což je přímo dělitelné devíti.
b) Je-li n = 3p + 1, tak podle binomické věty n3 = 27p3 + 27p2 + 9p + 1, což je o jednu vyšší než násobek devíti 27p3 + 27p2 + 9p.
c) Je-li n = 3p − 1, tak podobně n3 = 27p3 − 27p2 + 9p − 1, což je o jednu menší než násobek devíti.

Protože tvrzení platí pro všechny možné tři typy n, z nichž m mohlo vzniknout umocněním na třetí, musí platit obecně, a tím je dokázáno.