Ngtjyty

Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat.

L'article o secció necessita millores quant al seu format. Pot necessitar retocs en negretes, cursives, enllaços, imatges, categories, infotaules...

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.

En una forma general mostra que les formes que poden ser avaluades són equivalents en el que es coneix com a inducció estructural.

L'any 1575 Francesco Maurolico va fer la primera demostració per inducció.

Exemple

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

1+2+3+⋯+n=n(n+1)2{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,

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

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

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

Per manipulació algebraica obtenim

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

Així, resulta

1+2+⋯+(m+1)=(m+1)((m+1)+1)2{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

P(m)⇒P(m+1){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.