O princípio da indução finita ou simplesmente indução é um método matemático que pode ser utilizado para demonstrar proposições feitas no domínio dos números naturais. O método consiste em seguir os seguintes passos, para uma dada proposição:
- Passo inicial: provar que a proposição é válida para o menor valor de n.
- Passo indutivo: assumido que a proposição é válida para um certo e provar, a partir disso, que a proposição seria válida para o próximo termo, ou seja, o termo .
Vejamos um exemplo para entender melhor:
Exemplo do Princípio de Indução Finita
Demonstre que
Passo Inicial:
Vamos testar para :
(ok)
Passo indutivo:
Suponha que, para um certo k:
Vamos analisar a soma .
Utilizando a hipótese de indução finita, temos que
Desse modo:
, o que prova nossa hipótese de indução e também a proposição.
Esse método é válido para provar uma proposição pois o passo indutivo prova que se o enunciado é válido para um número qualquer, então é válido para o próximo. A isso, associa-se o passo inicial, que provou que a proposição é válida para o menor número possível. Desse modo, é possível chegar em qualquer outro número a partir daí.