Prova per inducció
De Viquipèdia
La prova d'inducció en matemàtica 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 inducció estructural.
L'any 1575 Francesco Maurolico va fer la primera prova per inducció.
[edita] Exemple
Suposem que volem provar la relació (fórmula de la suma dels n primers nombres naturals) :
per a tots els nombres naturals n.
[edita] Prova
Comprovar si és veritat per n = 0. Clarament, la suma dels primers 0 nombres naturals és 0, i 0(0 + 1) / 2 = 0. Per tant l'expressió és certa per a n = 0.
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:
Assumir que la fórmula és certa quan n = m,
Afegint m + 1 a les dues bandes es té
Per manipulació algebraica s'obté
Així, resulta
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
Per tant es pot concloure per inducció que la relació P(n) es compleix per a tots els nombres naturals n.