Problema 2.
Para a inteiro positivo, defina F(a)1=1, F(a)2=a e, para n>2, F(a)n=F(a)n−1+F(a)n−2. 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=Fn−1+Fn−2).
Lema. F(a)n=Fn−1a+Fn−2.
Prova: Provaremos por indução.
Caso base: F(a)1=0⋅a+1 e F(a)2=1⋅a+0.
Suponha que F(a)k=Fk−1a+Fk−2 para todo k<n.
Daí
F(a)n=F(a)n−1+F(a)n−2=Fn−2a+Fn−3+Fn−3a+Fn−4
=a(Fn−2+Fn−3)+(Fn−3+Fn−4)=Fn−1a+Fn−2.
Portanto F(a)n≡Fn−2(modFn−1), i.e., fixando um n, apenas 1 resíduo módulo Fn−1 é 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 F3k≡0(mod2) e F3k+1≡F3k+2≡1(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 Fn−1(modFn) no conjunto {2,4,…,2N} com n congruente a 1 ou 2(mod3).
Basta então mostramos que
limN→∞∑k≥1⌊NF3k+1⌋+⌊NF3k+2⌋N<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
limN→∞1N∑k≥1(NF3k+1+NF3k+2)=∑k≥11F3k+1+1F3k+2.
Provaremos agora que Fn≥φn−2 para todo n≥2 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.
2n→2n+1.
φ2n+1≤φF2n≤F2n+1
⟺φ(φ2n−¯φ2n)√5≤(φ2n+1−¯φ2n+1)√5
⟺¯φ2n+1≤φ¯φ2n
⟺1≤φ.
2n→2n+2.
φ2n+2≤φ2F2n≤F2n+2
⟺φ2(φ2n−¯φ2n)√5≤(φ2n+2−¯φ2n+2)√5
⟺¯φ2n+2≤φ2¯φ2n
⟺¯φ4≤1,
concluindo a prova.
Voltando à expressão,
∑k≥11F3k+1+1F3k+2≤∑k≥11φ3n−1+1φ3n
=(1φ2+1φ3)(∑k≥0φ3k)=1φ⋅11−1φ3=φ2φ3−1<1.