OBM 2020 – Nível 3 – P2

Problema 2.

Para a inteiro positivo, defina $F_1 ^{(a)}=1$, $F_2 ^{(a)}=a$ e, para $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 $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.$$