In how many ways is possible to write a number as the ordered sum of $ 1$ and $2$.

By looking at the first (positive) integers:

$1: (1) \to 1\ \text{ways}$

$2: (1,1), (2) \to 2\ \text{ways}$

$3: (1,1,1), (2,1), (1,2) \to 3\ \text{ways}$

$4: (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2) \to 5\ \text{ways}$

If $Q_n$ denotes the number we need to find the number of ordered sums of, then

$$Q_n = F_{n+1}$$

Where $F_{n+1}$ denotes the $n+1$ term of the Fibonacci Sequence.

Is there a proof of this?

It is evident that if the number $m$ 2's and $r$ 1's will give ${m +r \choose m,r}$ different sums which give $Q_n$, but I have no idea how to connect this with Fibonacci or whether there is another way to prove it.

Maybe I'm trying to reinvent the wheel.

  • 4
    $\begingroup$ Your conjecture is correct; there are proofs here. $\endgroup$ – Brian M. Scott Nov 1 '16 at 18:59

It's a relatively simple proof. We know that their is one way to add 1 and 2 up to get to 0, namely $0=0$. So $G_0 = 0$. A similar thing holds for $G_1 = 1$. Now let's assume we know $G_{n-1}$ and $G_{n-2}$. For every combination represented in $G_{n-1}$ we can add 1 to get combinations in $G_{n}$. We can similarly add 2 to each combination in $G_{n-2}$. These combinations are distinct since they add up different numbers. Therefore $G_n = G_{n-1} + G_{n-2}$, the same recurrence relation the Fibonacci numbers have. Since $G_0 = G_1 = 1$, the same initial values of the Fibonacci sequence, we know that the sequences will be identical.


We can prove this using direct proof.

Hypothesis: For Fibbonaci number $F_1=1, F_2=1, F_{n}=F_{n-1}+F_{n-2}$, $Q(k)=F_{k+1}$

We say that we have constructed every order of $Q(n)$. Then, we construct $Q(n+1)$ this way:

  1. For all orders, we add $+1$ to change $n$ to $n+1$. (There are now $Q(n)$ numbers.) Note: all numbers that are constructed here ends in $+1$.
  2. For all orders that end with $+1$, we change it to $+2$. We shall prove that the amount will be $Q(n-1)$ to complete the proof. Note: all numbers that are constructed here ends in $+2$.

It can be seen that by constructing in this way there contains all orders.

Proof of step 2: If we constructed $Q(n)$ in the way above, then all numbers ended in $+1$ will be the amount $Q(n-1)$ by step 1. above, and we are done.


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.