Sumo de neparaj nombroj (Maurolicus 1575)

La laŭpaŝa kalkulado de la sumo de la unuaj ${\displaystyle n}$ neparaj nombroj supozigas la sekvan konjekton: La sumo de ĉiuj neparaj nombroj de 1 ĝis ${\displaystyle 2n-1}$ egalas al la kvadrato de ${\displaystyle n}$:

1 = 1

1 + 3 = 4

1 + 3 + 5 = 9

1 + 3 + 5 + 7 = 16

La ĝenerala teoremo estas: ${\displaystyle \sum _{i=1}^{n}(2i-1)=n^{2}.}$. Ĝin pruvis Maurolicus en 1575 per matematika indukto.^[4] Pruvo kun nuntempe kutimaj kalkulreguloj tekstas jene:

La indukto-bazo validas, ĉar ${\displaystyle \sum _{i=1}^{1}(2i-1)=2\cdot 1-1=1=1^{2}}$.

Ĉe la indukto-paŝo pruvendas jeno: Se ${\displaystyle \sum _{i=1}^{n}(2i-1)=n^{2}}$, tiam ${\displaystyle \sum _{i=1}^{n+1}(2i-1)=(n+1)^{2}}$. Tio sekvas el egalaĵo-ĉeno, ĉe kiu oni uzas la induktan hipotezon ĉe la dua transformo: ${\displaystyle \sum _{i=1}^{n+1}(2i-1)=\sum _{i=1}^{n}(2i-1)+(2(n+1)-1)=n^{2}+2(n+1)-1=n^{2}+2n+1=(n+1)^{2}}$.

La sumformulo de Gauss

La sumformulo de Gauss tekstas jene: Por ĉiuj naturaj nombroj ${\displaystyle n\geq 1}$, ${\displaystyle \sum _{k=1}^{n}k=1+2+\cdots +n={\frac {n(n+1)}{2}}}$.

La bazo de la indukto tuj pruveblas:

${\displaystyle \sum _{k=1}^{1}k=1={\frac {1(1+1)}{2}}}$

La paŝo de la indukto por ajnaj naturaj nombroj ${\displaystyle \,n}$ estas atingata per la jena egalaĵo-ĉeno, ĉe kiu la indukta hipotezo estas uzata ĉe la dua transformo:

${\displaystyle {\begin{aligned}\sum _{k=1}^{n+1}k=\sum _{k=1}^{n}k+(n+1)={\frac {n(n+1)}{2}}+(n+1)\\={\frac {n(n+1)+2(n+1)}{2}}={\frac {(n+2)(n+1)}{2}}\end{aligned}}}$

Neegalaĵo de Bernoulli

La neegalaĵo de Bernoulli asertas ke por reala nombro ${\displaystyle \,x}$ tia ke ${\displaystyle x+1\geq 0}$ kaj natura nombro ${\displaystyle n\geq 0}$,

${\displaystyle (1+x)^{n}\geq 1+nx}$.

La indukto-bazo ĉi tie validas ĉar ${\displaystyle (1+x)^{0}=1\geq 1}$. La indukto-paŝon oni atingas per jena derivaĵo, kiu en la dua paŝo uzas la induktan hipotezon, kaj ĉe kiu la supra kondiĉo por ${\displaystyle \,x}$ certigas, ke la termo ne iĝas negativa:

${\displaystyle {\begin{aligned}(1+x)^{n+1}=(1+x)^{n}\cdot (1+x)\geq (1+nx)\cdot (1+x)=\\=1+x+nx+nx^{2}\geq 1+x+nx=1+(n+1)x\end{aligned}}}$

Indukto kun ajna komenco

Indukta pruvo de la neegalaĵo ${\displaystyle 2^{n}\geq n^{2}}$ por naturaj nombroj ${\displaystyle n\geq 4}$:

La indukto-bazo por ${\displaystyle \,n=4}$ sekvas el ${\displaystyle 2^{4}=16\geq 16=4^{2}}$.

La indukto-paŝo validas pro la jena derivaĵo, ĉe kiu en la dua paŝo uziĝas la indukta hipotezo kaj en la kvara kaj sesa paŝoj la kondiĉo ${\displaystyle n\geq 4}$:

${\displaystyle 2^{n+1}=2\cdot 2^{n}\geq 2\cdot n^{2}=n^{2}+n\cdot n\geq n^{2}+4n=n^{2}+2n+2n\geq n^{2}+2n+2\cdot 4\geq n^{2}+2n+1=(n+1)^{2}}$.

La finhava kvanto de okazoj kiujn tia induktopruvo ne kovras povas esti studataj aparte. En ĉi tiu ekzemplo la neeglaĵo klare malveras por ${\displaystyle \,n=3}$.

Indukto kun pluraj antaŭantoj

Ĉe kelkaj indukto-pruvoj oni bezonas indukto-hipotezon por pluraj antaŭantoj; la indukto-bazo tiam estas pruvenda por pluraj komencaj valoroj. Se ekzemple por la derivaĵo de formulo estas bezonata indukta hipotezo por n kaj n-1, tiam la indukobazo estas pruvenda por du sinsekvaj nombroj, ekzemple 0 kaj 1.^[15] Kiel indukta hipotezo ankaŭ povas roli la aserto por ĉiu nombroj inter la komenca valoro kaj n. Unu ekzemplo estas la pruvo, ke ĉiu natura nombro ${\displaystyle n\geq 2}$ havas priman dividanton.

Indukto-bazo: 2 estas dividebla per 2.

Indukto-paŝo: La aserto estu vera por ĉiu ${\displaystyle \,m}$ tia ke ${\displaystyle 2\leq m\leq n}$. Se ${\displaystyle \,n+1}$ estas primo, tiam ${\displaystyle \,n+1}$ mem estas la serĉata dividanto. Se ${\displaystyle \,n+1}$ ne estas primo, tiam ekzistas du nombroj ${\displaystyle \,a,b}$ tiaj ke ${\displaystyle a\cdot b=n+1}$ kaj ${\displaystyle 2\leq a,b\leq n}$. Do ambaŭ nombroj plenumas la induktan hipotezon. Do certe ${\displaystyle \,a}$ havas priman dividanton ${\displaystyle \,p}$. ${\displaystyle \,p}$ ankaŭ dividas ${\displaystyle \,n+1}$ kaj sekve estas prima dividanto de ${\displaystyle \,n+1}$.