Maths Olympiad Prep

Library / /11 of 36

, 2023

Algebra Difficulty 8.1 Shortlist Prove it Baltic Way

Let Z+\mathbb{Z}^+ be the set of positive integers and (Fn)nZ+(F_n)_{n \in \mathbb{Z}^+} be the Fibonacci sequence defined by F1=F2=1F_1 = F_2 = 1 and Fn+1=Fn+Fn1F_{n+1} = F_n + F_{n-1} for n2n \ge 2. Consider the number
N=22022F202322021F2022+22020F2021++2F2+F1. N = 2^{2022}F_{2023} - 2^{2021}F_{2022} + 2^{2020}F_{2021} + \dots + 2F_2 + F_1.
Prove that the binary expansion of NN contains more 1's than 0's.

Solutions — 2

Solution 1

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

Adding this three equations together, we get on the left hand side
4N2NN=N 4N - 2N - N = N
and on the right hand side
=22024F202322023F202222023F2023+ +i=22022(2)i(Fi1+FiFi+1)2F12(F2)F1 =22024F202322023(F2022+F2023)+2(F2F1)F1 =22024F202322023F2024F1. \begin{align*} &= 2^{2024} F_{2023} - 2^{2023} F_{2022} - 2^{2023} F_{2023} + \dots \ & \quad + \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{align*}
Hence
N+1=22024F202322023F2024 N + 1 = 2^{2024} F_{2023} - 2^{2023} F_{2024}
is indeed a multiple of 220232^{2023} as desired.

Solution 2

For nZ2n \in \mathbb{Z}_{\ge 2}, let Nn:=i=0n(2)iFi+1N_n := \sum_{i=0}^{n} (-2)^i F_{i+1}. As in the first proof, we want to show 22023N2022+12^{2023} \mid N_{2022} + 1, or more generally 2n+1Nn+12^{n+1} \mid N_n + 1. To do so, we prove the explicit representation of the sum as Nn+1=(1)n2n+1Fn1N_n + 1 = (-1)^n \cdot 2^{n+1} \cdot F_{n-1}.
For n=2n=2, we have N2+1=22F32F2+F1+1=8=(1)223F1N_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
Nn+1+1=Nn+1+(2)n+1Fn+2 =(2)n+1Fn1+(2)n+1(Fn+1+Fn) =(2)n+1(Fn1+Fn+Fn1+Fn)=(2)n+2Fn. \begin{align*} 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{align*}
Thus, 2n+1Nn+12^{n+1} \mid N_n + 1 and, in particular, 22023N20222^{2023} \mid N_{2022}, which proves the claim. The desired results follows from there as in the first proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.