[HOME PAGE] [STORES] [CLASSICISTRANIERI.COM] [FOTO] [YOUTUBE CHANNEL]

Prova per inducció - Viquipèdia

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) :

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

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,

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

Afegint m + 1 a les dues bandes es té

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

Per manipulació algebraica s'obté

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

Així, resulta

0 + 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.