Maths Olympiad Prep

Library / /145 of 155

Algebra Difficulty 7.3 National olympiad, round 2 Prove it Saudi Arabia

Fibonacci sequences is defined as
{f1=1, f2=2fn+1=fn+fn1, n2 \left\{\begin{array}{l} f_{1}=1,\ f_{2}=2 \\ f_{n+1}=f_{n}+f_{n-1},\ n \geq 2 \end{array}\right.
1. Prove that every positive integer can be represented as sum of several distinct Fibonacci number.
2. A positive integer is called Fib-unique if the way to represent it as sum of several distinct Fibonacci number is unique.
Example: 13 is not Fib-unique because 13=13=8+5=8+3+213=13=8+5=8+3+2. Find all Fib-unique.

Solution

1. We will prove by induction that every positive integer kk can be written as sum of several distinct Fibonacci numbers.
The case k=1k=1 is obvious, we have 1=f11=f_{1}.
Assume that every positive integer less than nn can be written as sum of several distinct Fibonacci numbers, consider k=nk=n.
We can find fif_{i} is the greatest Fibonacci number which is less than nn, we have
n=fi+(nfi). n=f_{i}+\left(n-f_{i}\right) .
According to the induction hypothesis, nfin-f_{i} is a positive integer less than nn, therefore it can be written as
nfi=fj1+fj2++fjt, j1<j2<<jt. n-f_{i}=f_{j_{1}}+f_{j_{2}}+\cdots+f_{j_{t}},\ j_{1}<j_{2}<\ldots<j_{t} .
We must have i>jti>j_{t} because otherwise, n=fi+fjt+>fi+fi1=fi+1n=f_{i}+f_{j_{t}}+\cdots>f_{i}+f_{i-1}=f_{i+1}, contradiction to the choice of ii.
So, n=fj1+fj2++fjt+fin=f_{j_{1}}+f_{j_{2}}+\cdots+f_{j_{t}}+f_{i}, which is a representation of nn as sum of distinct Fibonacci numbers, we are done.

2. According to the part 1., an integer nn can be written as
n=fi1+fi2++fik, i1<i2<<ik. n=f_{i_{1}}+f_{i_{2}}+\cdots+f_{i_{k}},\ i_{1}<i_{2}<\cdots<i_{k} .
We need to find all nn of which representation is unique.
First, if i13i_{1} \geq 3, then we can replace fi1f_{i_{1}} by fi11+fi12f_{i_{1}-1}+f_{i_{1}-2} and get another representation of nn. So if nn is a "Fib-unique", i1{1,2}i_{1} \in\{1,2\}.
Second, if there is some tt such that it+1it3i_{t+1}-i_{t} \geq 3, then we can replace fit+1f_{i_{t+1}} by fit+11+fit+12f_{i_{t+1}-1}+f_{i_{t+1}-2} and get another representation of nn.
Hence, for a "Fib-unique" integer nn, we have it+1it2i_{t+1}-i_{t} \leq 2 for every 0tk10 \leq t \leq k-1.
Third, if we have some tt such that it+1it=1i_{t+1}-i_{t}=1, chose that tt which is the largest. Then we can replace fit+1+fitf_{i_{t+1}}+f_{i_{t}} by fit+1+1f_{i_{t+1}+1}, and get another representation of nn. So for a "fib-unique" nn we must have it+1it=2i_{t+1}-i_{t}=2 for every 0tk10 \leq t \leq k-1.
So, every possible "Fib-unique" positive nn are f1,f2f_{1}, f_{2} and those in these forms:
 i . n=f1+f3++f2k1=f2k1 ii . n=f2+f4++f2k=f2k+11 \begin{aligned} & \text{ i . } n=f_{1}+f_{3}+\cdots+f_{2k-1}=f_{2k}-1 \\ & \text{ ii . } n=f_{2}+f_{4}+\cdots+f_{2k}=f_{2k+1}-1 \end{aligned}
In conclusion, every Fib-unique is f1,f2f_{1}, f_{2} and fk1f_{k}-1 with k3k \geq 3. \square

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.