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 suma de nombres naturals) :
per 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 veritat per n = 0.
Ara hem de veure si la fórmula funciona quan n = m, aleshores també ho farà quan n = m + 1. Es pot fer així:
Assumir que la fórmula és veritat per n = m,
Afegint m + 1 a les dues bandes tenim
Per manipulació algebraica tenim
Així queda
Aquesta és la fórmula per n = m + 1. No ha estat provat que sigui veritat i hem d'assumir que P(m) és veritat i d'això derivar que P(m + 1). Simbolicament s'ha demostrat que:
Per tant podem concloure per inducció que la relació P(n) es compleix per tots els nombres naturals n:
