Teljes indukció

Teljes indukció
Ha azon esetek, melyekre valamely bebizonyítandó tétel vonatkozik, egy első, egy magasabb második, egy harmadik satöbbi osztályba sorozhatók, ...

A teljes indukció módszere a dominóeffektusra hasonlít.
A teljes indukció (ritkábban: matematikai indukció) a matematika egyik legfontosabb és leggyakrabban használt bizonyítási módszere a természetes számok körében.

teljes indukció
A teljes indukcióval való bizonyítás módszere a következő elven alapul: Tegyük fel, hogy minden n pozitív egésznek megfeleltethető egy állítás, amely vagy igaz, vagy hamis. Ha
igaz, és ...

Teljes indukcióval könnyen adódik, hogy . Ennek alapján az (1) feltétel ekvivalens az
oszthatósággal. A jobb oldalt -vel szorozva miatt
(2) ...

Itt a teljes indukciós bizonyítást a rekurziós összefüggés segítségével lehet elvégezni. Ebben az esetben is egyenértékű a teljes indukció és a rekurzió módszerét használó megoldás, bár a teljes indukció alkalmazásához ismerni kell a végeredményt.

Teljes indukciót alkalmazunk n-re. Az állítás n=4-re az, hogy négypontú, legalább öt élű gráfban van a megadott alakzat. De ilyen gráf csak kettő van: a teljes négyes és az a gráf, amelyet ebből egy él elvételével kapunk.

Ezekután a teljes indukciós állítás alapján találhatunk k darab éldiszjunkt ts~ utat G_s-ben. Legyenek ezek P_1,P_2,...,P_k. Hasonlóan nyerhetők Q_1,Q_2,...,Q_k éldiszjunkt st~ utak G_t-ben.

Bizonyítsuk be a tételt teljes indukcióhoz hasonlóan!
Ha hozzáadunk egy újabb csúcsot, akkor ahhoz, hogy összefüggő maradjon, ...

Ebből azt sejtjük: . Teljes indukcióval megvizsgáljuk, hogy ez a sejtés igaz-e.

Ez az eljárás láthatóan akármekkora n-re működik. A pontos bizonyítást jelentő n+1-ig terjedő teljes indukciót itt elhagyjuk.

I. 45. - A négynél több oldalú sokszög esete ugyanígy (szigorúan véve teljes indukcióval) intézhető el. Ez a tétel és I. 41. biztosítja, hogy I. 44. háromszög helyett bármely sokszögre alkalmazható legyen.

See also: Indukció, Bizonyítás, Hasonló, Összeg, Sorozat