Prove que 5 downarrow(fn+5-3 fn), forall n >= 1. Conclua a partir daí que f5, f10, f15, ldots são múltiplos de 5 .

Passo 1

O enunciado trata da sequência de Fibonacci (fn), dada por
f1 = 1, f2 = 1, fn+2 = fn+1 + fn(forall n>=1),
e pede para provar que
5 mid l(fn+5 - 3,fnr)(forall n>=1)
e, a partir disso, concluir que f5,f10,f15,dots são múltiplos de 5.
Vamos usar um argumento por indução forte sobre n.

Passo 2

Base da indução: verificamos manualmente para n=1 e n=2.
  • Para n=1:
f1+5 - 3,f1 = f6 - 3 f1 = 8 - 3cdot1 = 5,
logo 5mid(f6 - 3f1).
  • Para n=2:
f2+5 - 3,f2 = f7 - 3 f2 = 13 - 3cdot1 = 10,
logo 5mid(f7 - 3f2).
Portanto, a propriedade vale para n=1 e n=2.

Passo 3

Passo indutivo: suponha que para todo k com 1<= k<= n+1 tenhamos
5 mid l(fk+5 - 3,fkr)
Queremos mostrar
5 mid l(f(n+1)+5 - 3,fn+1r),
isto é,
fn+6 - 3,fn+1equiv0pmod5
Usando a relação de recorrência,
fn+6 = fn+5 + fn+4,
e também fn+1=fn+fn-1, obtemos
fn+6 - 3,fn+1 &= l(fn+5 + fn+4r) - 3l(fn + fn-1r) &= l(fn+5-3fnr) + l(fn+4-3fn-1r)
Pela hipótese indutiva, 5 divide cada um dos dois parênteses, logo também divide sua soma. Assim, 5mid(fn+6-3fn+1). Isso fecha a indução forte, provando que
5 mid l(fn+5-3,fnr)forall n>=1

Passo 4

Agora, para concluir que f5,f10,f15,dots são múltiplos de 5, note que, para n=5k, a propriedade dá
5 mid l(f5k+5 - 3,f5kr) Longrightarrow f5(k+1) equiv 3,f5kpmod5
Mas f5=5equiv0pmod5. Supondo ,f5kequiv0pmod5, segue f5(k+1)equiv3cdot0=0pmod5. Por indução em k, todos os termos f5,f10,f15,dots são múltiplos de 5.

Resposta

Está provado que
5midl(fn+5-3,fnr)(forall n>=1) e, portanto, f5,f10,f15,dots são mú<iplos de 5 ãú

Exercícios de Livros Relacionados