Mostrar que para os números de Fibonacci, definidos no problema anterior, satisfazem
Passo 1
Estamos com os números de Fibonacci definidos por F₁=F₂=1 e Fₙ=F_{n-1}+F_{n-2}, e queremos mostrar que o máximo divisor comum de Fₙ e F_{n+1} é 1. Para isso vamos usar propriedade do Algoritmo de Euclides e indução.
Passo 2
A relação de recorrência dos Fibonacci e a propriedade do Algoritmo de Euclides que vamos usar são:
e
Passo 3
Aplicando o Algoritmo de Euclides em
, temos:
Como
, o resto de
na divisão por
é precisamente
. Logo
Passo 4
Repetindo esse mesmo passo sucessivamente, vamos reduzindo o par de argumentos do mdc até chegarmos em
Passo 5
Como
e
, temos
Portanto, por indução reversa pelo Algoritmo de Euclides, obtemos
para todo
.