Let be the set of positive integers and be the Fibonacci sequence defined by and for . Consider the number
Prove that the binary expansion of contains more 1's than 0's.
, 2023
Solutions — 2
Solution 1
Since is monotonically increasing, it is clear that
Moreover, since , it is clear that and hence has at most 4045 binary digits. It will thus suffice to prove that the last 2023 binary digits of are 1's, in other words, that .
We have
Adding this three equations together, we get on the left hand side
and on the right hand side
Hence
is indeed a multiple of as desired.
Solution 2
For , let . As in the first proof, we want to show , or more generally . To do so, we prove the explicit representation of the sum as .
For , we have . The induction steps follows via
Thus, and, in particular, , 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.