Summationsbevis

Det drejer sig om at vise formlen

∑ⁿ_i=1 2ⁱ = 2ⁿ⁺¹ - 2 .

Formlen kan vises ved induktion efter n. Vi først, at den gælder for n = 1. Vis dernæst, at hvis den gælder for et n, så gælder den også for n+1 .

TIl #1

Antager vi, formlen gælder for n, har vi

∑ⁿ⁺¹_i=1 2ⁱ = (∑ⁿ_i=1 2ⁱ) + 2ⁿ⁺¹ = 2ⁿ⁺¹ - 2 + 2ⁿ⁺¹ = 2·2ⁿ⁺¹ - 2 = 2ⁿ⁺² - 2 = 2^(n+1)+1 - 2