|
O princípio da indução finita é um dos axiomas de
Peano, os quais definem o conjunto dos números naturais.
Ele diz o seguinte:
Seja N o conjunto dos números naturais (inteiros
positivos)
Seja X um subconjunto de N com as seguintes
propriedades:
a) 1 pertence a X, e
b) se n pertence a X então n+1 pertence a
X
Neste caso, X = N.
Existe uma formulação que talvez seja mais
apropriada para a resolução de problemas:
Seja P(x) uma proposição relativa ao número natural
x.
a) Se P(1) for verdadeira, e
b) Se supondo P(n) verdadeira, pudermos provar que
P(n+1) é verdadeira
Então, P(n) será verdadeira para cada número
natural n.
O exemplo mais manjado é o seguinte:
Prove que 1 + 2 + 3 + ... + n = n(n+1)/2, para todo
natural n.
Caso Base:
n =1 ==> 1 =
1*(1+1)/2 ==> a fórmula vale para n = 1
Hipótese de Indução:
A fórmula vale para o natural n, ou
seja:
1 + 2 + ... + n = n(n+1)/2
O caso n+1:
Somando (n+1) aos dois membros da fórmula para n,
teremos:
1 + 2 + ... + n + (n+1) = n(n+1)/2
+ (n+1) = (n+1)(n/2 + 1) = (n+1)(n+2)/2
Ou seja, dado que a fórmula vale para n, foi
possível provar que ela vale para n+1.
Pelo princípio da indução finita, a fórmula vale
para todo natural n.
|