Demostració Per Inducció: Tipus de demostració matemàtica

L'any 1575 Francesco Maurolico va fer la primera demostració per inducció al seu treball Arithmeticorum libri duo. En una forma general mostra que les formes que poden ser avaluades són equivalents en el que es coneix com a inducció estructural. La Demostració per inducció és una regla d'inferència usada en proves formals, que són exemples de raonament deductiu.

Suposem que volem demostrar la relació (fórmula de la suma dels n primers nombres naturals) :

${\displaystyle 1+2+3+\cdots +n={\frac {n(n+1)}{2}}}$ 

per a tots els nombres naturals n.

Demostració

Primerament comprovem si és veritat per n = 1. Clarament, la suma dels dos primers nombres és igual a 1*(1 + 1) / 2 = 1, com preveu la fórmula. Per tant l'expressió és certa per a n = 1.

Ara cal provar si el fet que la fórmula es verifiqui quan n = m implica que també ho farà quan n = m + 1. Es pot fer de la manera següent:

Assumim que la fórmula és certa quan n = m,

${\displaystyle 1+2+\cdots +m={\frac {m(m+1)}{2}}}$ 

Afegim m + 1 a les dues bandes i es té

${\displaystyle 1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)}$ 

Per manipulació algebraica obtenim

${\displaystyle ={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}}$ 

Així, resulta

${\displaystyle 1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}}$ 

Aquesta és la fórmula per a n = m + 1. No ha estat provat que sigui certa i hem d'assumir que P(m) és veritat i d'això derivar que P(m + 1). Simbòlicament s'ha demostrat que

${\displaystyle P(m)\Rightarrow P(m+1)}$ 

Per tant es pot concloure per inducció que la relació P(n) es compleix per a tots els nombres naturals n.