2
$\begingroup$

The Fibonacci sequence $f_1, f_2, f_3, \ldots$ is defined by $f_1 = 1, f_2 = 2$, and $f_m = f_{m−1} + f_{m−2}$ for each integer $m \ge 3$. Prove that every $n \in \mathbb{N}$ can be expressed as the sum of distinct integers from the Fibonacci sequence.

Note: You may use without proof that the Fibonacci sequence is an increasing sequence

I am stuck in this question. Are we supposed to use strong induction here? I am trying it but get stuck. Any help would be appreciated!

$\endgroup$
1
$\begingroup$

HINT

Use strong induction, assuming this is true up to some $n-1 \in \mathbb{N}$. Then, for $n$, find the largest Fibonacci member $f$ below $n$ and apply strong induction to $n - f$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.