Maths Olympiad Prep

Library / /258 of 520

Number theory Difficulty 5.5 AIME, harder Prove it

Fibonacci numeral system. Prove that any natural number nn, not exceeding FmF_{\mathrm{m}}, can be uniquely represented in the form

n=k=2mbkFk, n=\sum_{k=2}^{m} b_{k} F_{k},

where all numbers b2,,bmb_{2}, \ldots, b_{\mathrm{m}} are either 0 or 1, and among these numbers there are no two consecutive ones, that is, bkbk+1b_{\mathrm{k}} b_{\mathrm{k}}+1 =0(2km1)=0(2 \leqslant k \leqslant m-1). For representing a number in the Fibonacci numeral system, the notation used is:

n=(bkb2)F n=\left(b_{\mathrm{k}} \ldots b_{2}\right)_{\mathrm{F}}

Solution

To decompose a number nn in the Fibonacci numeral system, one should use the "greedy" algorithm: subtract from nn the largest number FmF_{\mathrm{m}} that does not exceed nn.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.