Se
, define-se sucessor de
por
. Prove que (
sempre):
.
Passo 1
O enunciado define o sucessor de
por
e pede para provar que, para todo
,
Vamos usar a definição recursiva da multiplicação em
(fixando
e recursão em
) e o princípio da indução finita.
Passo 2
Caso base (
). Nesse caso
. Pela definição de multiplicação recursiva:
Logo
que é exatamente a fórmula desejada para
.
Passo 3
Passo indutivo. Suponha que, para um certo
, valha
Precisamos mostrar que então também vale para
, isto é,
Mas essa igualdade é exatamente a cláusula de definição recursiva da multiplicação: para qualquer argumento
define-se
Basta aplicar-la com
, obtendo
que conclui o passo indutivo.
Resposta
Pelo princípio da indução, fica provado que, para todos
,