Demostració per inducció

La demostració per inducció en matemàtica és un tipus de demostració que s'aplica quan un cas base és provat i una regla d'inducció és usada per provar una sèrie d'altres casos que normalment és infinita. 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.

Es pot il·lustrar informalment la inducció matemàtica fent referència a l'efecte seqüencial de la caiguda de fitxes de dòmino.

Exemple

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

$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,

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

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

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

Per manipulació algebraica obtenim

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

Així, resulta

$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

$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.