Baltic Way 2023 Shortlist

Since $F_n$ is monotonically increasing, it is clear that $$0<N<2^{2022}{F}_{2023}.$$ Moreover, since $F_{n+1}\le 2F_n$, it is clear that $F_{2023}<2^{2023}$ and hence $N$ has at most 4045 binary digits. It will thus suffice to prove that the last 2023 binary digits of $N$ are 1's, in other words, that $2^{2023}\mid N+1$. We have

Adding this three equations together, we get on the left hand side $$4N-2N-N=N$$ and on the right hand side $$\begin{array}{rlrlr}& =2^{2024}{F}_{2023}-2^{2023}{F}_{2022}-2^{2023}{F}_{2023}+\dots & +\sum _{i=2}^{2022}(-2{)}^i(F_{i-1}+F_i-F_{i+1})-2F_1-2(-F_2)-F_1& =2^{2024}{F}_{2023}-2^{2023}(F_{2022}+F_{2023})+2(F_2-F_1)-F_1& =2^{2024}{F}_{2023}-2^{2023}{F}_{2024}-F_1.\end{array}$$ Hence $$N+1=2^{2024}{F}_{2023}-2^{2023}{F}_{2024}$$ is indeed a multiple of $2^{2023}$ as desired.

---

Alternative solution.

For $n\in {\mathbb{Z}}_{\ge 2}$, let $N_n:={\sum }_{i=0}^n(-2{)}^i{F}_{i+1}$. As in the first proof, we want to show $2^{2023}\mid N_{2022}+1$, or more generally $2^{n+1}\mid N_n+1$. To do so, we prove the explicit representation of the sum as $N_n+1=(-1{)}^n\cdot 2^{n+1}\cdot F_{n-1}$. For $n=2$, we have $N_2+1=2^2{F}_3-2F_2+F_1+1=8=(-1{)}^2\cdot 2^3\cdot F_1$. The induction steps follows via $$\begin{array}{rlrl}{N}_{n+1}+1& =N_n+1+(-2{)}^{n+1}{F}_{n+2}& =-(-2{)}^{n+1}\cdot F_{n-1}+(-2{)}^{n+1}\cdot (F_{n+1}+F_n)& =(-2{)}^{n+1}\cdot (-F_{n-1}+F_n+F_{n-1}+F_n)=-(-2{)}^{n+2}\cdot F_n.\end{array}$$ Thus, $2^{n+1}\mid N_n+1$ and, in particular, $2^{2023}\mid N_{2022}$, which proves the claim. The desired results follows from there as in the first proof.