Problema 2.
Para a inteiro positivo, defina $$F_1 ^{(a)}=1$$, $$F_2 ^{(a)}=a$$ e, para $$n>2$$, $$F_n ^{(a)}=F_{n-1} ^{(a)}+F_{n-2} ^{(a)}$$. 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 $$F_n$$ o enésimo termo da sequência de Fibonacci ($$F_0 = 0$$, $$F_1 = 1$$ e $$F_n = F_{n-1} + F_{n-2}$$).
Lema. $$F^{(a)}_n = F_{n-1}a + F_{n-2}$$.
Prova: Provaremos por indução.
Caso base: $$F^{(a)}_1 = 0 \cdot a + 1$$ e $$F^{(a)}_2 = 1\cdot a + 0$$.
Suponha que $$F^{(a)}_k = F_{k – 1} a + F_{k – 2}$$ para todo $$k < n$$.
Daí \[F^{(a)}_n = F^{(a)}_{n-1} + F^{(a)}_{n-2} = F_{n – 2} a + F_{n – 3} + F_{n – 3} a + F_{n – 4}\]
\[= a(F_{n-2} + F_{n-3}) + (F_{n-3} + F_{n-4}) = F_{n-1}a + F_{n-2}.\]
Portanto $$F^{(a)}_n \equiv F_{n-2} \pmod {F_{n-1}}$$, i.e., fixando um $$n$$, apenas $$1$$ resíduo módulo $$F_{n – 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 $$F_{3k} \equiv 0 \pmod 2$$ e $$F_{3k+1} \equiv F_{3k+2} \equiv 1 \pmod 2$$. 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 $$\left \lfloor \frac{N}{F_n}\right \rfloor$$ elemontos congruentes a $$F_{n-1} \pmod {F_n}$$ no conjunto $$\{2, 4, \dots, 2N\}$$ com $$n$$ congruente a $$1$$ ou $$2 \pmod 3$$.
Basta então mostramos que
\[\lim_{N\rightarrow \infty} \frac{\sum_{k\geq 1} \left \lfloor\frac{N}{F_{3k+1}}\right \rfloor + \left \lfloor\frac{N}{F_{3k+2}}\right \rfloor }{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
\[\lim_{N\rightarrow \infty} \frac{1}{N} \sum_{k\geq 1} \left(\frac{N}{F_{3k+1}} + \frac{N}{F_{3k+2}} \right) = \sum_{k\geq 1} \frac{1}{F_{3k+1}}+ \frac{1}{F_{3k+2}} .\]
Provaremos agora que $$F_n \geq \varphi^{n-2}$$ para todo $$n\geq 2$$ por indução.
Caso base: $$F_2 = 1 \geq \varphi^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 \rightarrow 2n + 1$$.
\[\varphi^{2n + 1} \leq \varphi F_{2n} \leq F_{2n+1}\]
\[\iff \dfrac{\varphi(\varphi^{2n} – \overline{\varphi}^{2n})}{\sqrt{5}} \leq \dfrac{(\varphi^{2n+1} – \overline{\varphi}^{2n+1})}{\sqrt{5}} \]
\[\iff \overline{\varphi}^{2n+1} \leq \varphi \overline{\varphi}^{2n}\]
\[\iff 1 \leq \varphi.\]
$$2n \rightarrow 2n + 2$$.
\[\varphi^{2n + 2} \leq \varphi^2F_{2n} \leq F_{2n+2}\]
\[\iff \dfrac{\varphi^2(\varphi^{2n} – \overline{\varphi}^{2n})}{\sqrt{5}} \leq \dfrac{(\varphi^{2n+2} – \overline{\varphi}^{2n+2})}{\sqrt{5}} \]
\[\iff \overline{\varphi}^{2n+2} \leq \varphi^2\overline{\varphi}^{2n}\]
\[\iff \overline{\varphi}^4 \leq 1,\]
concluindo a prova.
Voltando à expressão,
\[\sum_{k\geq 1} \frac{1}{F_{3k+1}}+ \frac{1}{F_{3k+2}} \leq \sum_{k\geq 1} \frac{1}{\varphi^{3n-1}}+ \frac{1}{\varphi^{3n}}\]
\[= \left(\frac{1}{\varphi^2} + \frac{1}{\varphi^3}\right)\left( \sum_{k\geq 0} \varphi^{3k}\right) = \frac{1}{\varphi}\cdot \frac{1}{1-\frac{1}{\varphi^3}} = \frac{\varphi^2}{\varphi^3 – 1} < 1. \]