Dokazovanje z matematično indukcijo

Dokazati želimo, da neka trditev velja za vsak . Kot primer vzemimo trditev

Če hočemo res dobro razumeti indukcijo, moramo najprej vedeti, kaj sploh pravi in kaj pomenijo posamezni izrazi. Najbolj natančno lahko zapišemo indukcijo kot logični sklep

1. A(1)

2. A(n)=>A(n+1)

3. A(n) za vsak n naravno število

naj razložim, kaj se skriva v zgornjem sklepu. A(n) je predikat, logični izraz, ki je odvisen od n. A(n) je trditev, ki jo hočemo dokazati za vsak n. V našem primeru

A(n): za n velja 

trditev 1. je baza indukcije

trditev 2. je indukcijski korak

Indukcijski korak 2. je implikacija, ki jo lahko dokažemo z indukcijsko predpostavko (IP). Predpostavka je splošna metoda za dokazovanje implikacije. Trditev P=>B, lahko dokažemo tako, da ob predpostavki, da P velja, dokažemo B. Razmislite, kako bi dokazali npr. implikacijo n < − 1 = > n² > 1. Predpostavili bi, da je n<-1 in nato šli dokazovat trditev n² > 1. V tem primeru je n<-1 predpostavka, za katero predpostavimo, da velja, čeprav tega ne vemo.

Če zaključim. IP je predpostavka, da A(n) velja. Če to predpostavko privzamemo kot čisto resnico in tako zaslepljeni znamo dokazati trditev A(n+1), potem smo dokazali implikacijo A(n)=>A(n+1), to je indukcijski korak 2.

V naši nalogi je indukcijska predpostavka, da velja . Torej če velja IP, ali znamo dokazati, da velja 1^2+...+(n+1)^2=1/6(n+1)(n+1+1)(2(n+1)+1)? Če je odgovor da, potem velja indukcijski korak 2 in je s tem dokaz z indukcijo zaključen.

Bodimo pozorni na ta »če velja«. Pravo vprašanje pri dokazovanju indukcijskega koraka je

   Če velja A(n), ali velja tudi A(n+1)? 

Na to vprašanje moramo odgovoriti, ko uporabljamo indukcijo.

Umetnost dokazovanja z indukcijo je v tem, kako uporabimo IP. V našem primeru lahko vsoto na levi zapišemo kot

12 + ... + n2 + (n + 1)2 = (12 + ... + n2) + (n + 1)2

in za prvi sumand uporabimo IP

Ostane nam le še, da dobljeni izraz primerjamo z desno stranjo trditve za n + 1

Alternativen pogled

Naj bo množica vseh števil n, za katere trditev T(n) velja. Dokaz z indukcijo ima dva koraka:

1. baza indukcije:

; velja

1. indukcijska predpostavka

recimo, da je

torej velja

pokažemo, da od tod sledi , torej tudi velja.

Primer

Dokažimo z indukcijo v dveh korakih:

1. baza indukcije:

, torej

1. indukcijska predpostavka:

recimo, da za nek n velja

dokazati moramo, da od tod sledi veljavnost tudi za n + 1

iz indukcijske predpostavke sledi:

Jozefusov problem

Jozefusov problem je teoretični problem, ki se pojavlja v matematiki in računalništvu. V krogu stoji n ljudi, ki čakajo, da bodo usmrčeni. Ko usmrtijo prvega človeka, preskočijo naslednjih k - 1 ljudi in k-ti človek je spet usmrčen. Usmrtitveni proces se nadaljuje v krogu, le ta pa se nenehno manjša, saj ostaja vse manj ljudi. Na koncu ostane samo en preživeli.

Problem se imenuje po judovskem zgodovinarju Flaviusu Josephusu.

Primer napačne uporabe indukcije

Poišči kaj je narobe z naslednjim dokazom

Trditev

Vse krave so iste barve. 

Dokaz

Trditev dokažemo z indukcijo po moči množice.

Indukcija

• Baza indukcije

n=1 Očitno imajo v vsaki množici z eno kravo vse krave enako barvo

• Indukcijski korak

Predpostavimo, da za velja:

V vsaki množici krav moči n so vse krave iste barve.

Vzemimo poljubno množico krav M moči n+1 in izberimo poljubni dve kravi. Imenujmo ju Liska in Rjavka.

Množica A=M\{Liska} je moči n zato so po indukcijski predpostavki v njej vse krave iste barve npr. rjave. Označimo z B množico B=M\{Rjavka}. Velja ,zato so vse krave v rjave.

Prav tako so v B vse krave iste barve, torej iste barve kot v njeni podmnožici , torej iste barve kot v A. Ker je so tudi v M vse krave iste barve! Q.E.D.

Rešitev

Kaj je narobe z zgornjim dokazom. Da ne bi kolegom pokvarili veselja ob iskanju rešitve, je rešitev na drugi strani!