*19. Demonstre que
para todos os números inteiros não negativos
, em que
é um número inteiro não negativo e
indica o
-ésimo número de Fibonacci.
Passo 1
O enunciado pede para provar que, para quaisquer inteiros não negativos
e
, vale
sendo
a sequência de Fibonacci definida por
O método mais direto é usar prova por indução em
, deixando
livre.
Passo 2
Base da indução
. Nesse caso
enquanto o lado direito é
Logo, para
a identidade vale para todo
.
Passo 3
Passo indutivo. Suponha que, para algum inteiro
, valha
Passo 4
Precisamos mostrar que então
Usando a relação de Fibonacci
e
, calculamos o lado esquerdo:
Mas pela hipótese de indução, para o mesmo
e
substituído por
, temos
Portanto
como queríamos.
Resposta
Por indução em
, mostramos que para todo inteiro
e todo
vale