Induktionsbevis

når man viser noget ved induktion så skal man have en ide om hvad det skal være altså

1/2 + 1/4 + 1/8 + ......... + 1/2^n = ???

man viser så det gælder for n=3

og man antager så det gælder for n og viser det gælder for n+1.

Det er en simpel kvotientrække, hvor summen er a*(1-qⁿ)/(1-q) hvor a er første led og q er kvotienten

Hvis vi kalder

S_n = ∑ⁿ_k=1 1/2^k ,

har vi

S_n = 1/2ⁿ · ∑^n-1_k=1 2^k .

Det er forholdvis let at vise (eller det kan måske antages at være kendt), at

∑^n-1_k=1 2^k = 2ⁿ - 1 ,

hvorfor

S_n = 1 - 1/2ⁿ

Rækken er en kvotientrække  med kvotienten ½, så summen af de n første led er ½*(1-(½)ⁿ)/(1-½) = 1-(½)ⁿ

Nu ser vi på de (n+1) første led i rækken. Summen af disse led bliver 1-(½)ⁿ + (½)ⁿ⁺¹ = 1 - [(½)ⁿ -(½)ⁿ⁺¹] = 1 - (½)ⁿ[1-½] = 1 - (½)ⁿ⁺¹.  Altså: hvis reglen gælder for n, gælder den også for n +1.

For n = 2 fås: 1/2 + 1/4 = 3/4 = 1 - (½)². Hermed er summen bevist ved induktion: hvis den gælder for n = 2, gælder den også for n = 3, og hvis den gælder for n = 3 gælder den også for n = 4 osv. osv. QED