Processing math: 100%

OBM 2020 - Nível 3 - P2

Problema 2.

Para a inteiro positivo, defina F(a)1=1, F(a)2=a e, para n>2, F(a)n=F(a)n1+F(a)n2. Um inteiro positivo é fibonático quando é igual a F(a)n para algum a inteiro positivo e algum n>3. Prove que existem infinitos números inteiros que não são fibonáticos.

Solução de João Ferreira.

Seja Fn o enésimo termo da sequência de Fibonacci (F0=0, F1=1 e Fn=Fn1+Fn2).

Lema. F(a)n=Fn1a+Fn2.
Prova: Provaremos por indução.

Caso base: F(a)1=0a+1 e F(a)2=1a+0.

Suponha que F(a)k=Fk1a+Fk2 para todo k<n.

Daí

F(a)n=F(a)n1+F(a)n2=Fn2a+Fn3+Fn3a+Fn4

=a(Fn2+Fn3)+(Fn3+Fn4)=Fn1a+Fn2.

Portanto F(a)nFn2(modFn1), i.e., fixando um n, apenas 1 resíduo módulo Fn1 é coberto. Além disso, todo ímpar é fibonático pois F(a)4=2a+1.

Observemos agora a paridade dos termos da sequência de Fibonacci. Temos F3k0(mod2) e F3k+1F3k+21(mod2). Assim, todos os fibonáticos cobertos por n=3k para algum k são ímpares e, portanto, já foram contados.

Isso significa que existem no máximo NFn elemontos congruentes a Fn1(modFn) no conjunto {2,4,,2N} com n congruente a 1 ou 2(mod3).

Basta então mostramos que

limNk1NF3k+1+NF3k+2N<1,

ou seja, que a fração dos números que são fibonáticos é menor que 1.

A expressão acima é menor ou igual a

limN1Nk1(NF3k+1+NF3k+2)=k11F3k+1+1F3k+2.

Provaremos agora que Fnφn2 para todo n2 por indução.

Caso base: F2=1φ0.

Suponha que é válido para todo 2k<2n+1.

Mostraremos que a afirmação para 2n implica a afirmação para 2n+1 e 2n+2.

2n2n+1.

φ2n+1φF2nF2n+1

φ(φ2n¯φ2n)5(φ2n+1¯φ2n+1)5

¯φ2n+1φ¯φ2n

1φ.

2n2n+2.

φ2n+2φ2F2nF2n+2

φ2(φ2n¯φ2n)5(φ2n+2¯φ2n+2)5

¯φ2n+2φ2¯φ2n

¯φ41,

concluindo a prova.

Voltando à expressão,

k11F3k+1+1F3k+2k11φ3n1+1φ3n

=(1φ2+1φ3)(k0φ3k)=1φ111φ3=φ2φ31<1.