# Fibonacci Number Equals to The number of compositions of n+2 using integers $\ge2$

My textbook provides following task -

Prove combinatorially following statement :

The number of compositions of $n+2$ using integers $\ge2$ is a Fibonacci number

So I had tried first several few numbers :

(1) if $n = 0$, $n+2 =2$ and it only gives $1$ cases such as $\{2\}$

(2) if $n =1$, $n+2 = 3$ and it only gives $1$ cases such as $\{2,1\}$

(3) if $n =2$, $n+2 = 4$ and it gives $2$ cases such as $\{2,2\}$ and $\{4\}$

(4) if $n =3$, $n+2 = 5$ and it gives 2 cases such as $\{5\}$ , $\{3,2\}$

so till now the sequence I got is $1, 1, 2, 2$ which is obviously deviated from Fibonacci Sequence.

Is there anything I missed or the problem set wrong or any modification required to make the problem set complete?

• 1 and 2 are Fibonacci number, so it seems fine. It does not say that the numbers are not repeated or skipped. That would be a different assertion – Zach Boyd Sep 23 '17 at 4:27
• @ZachBoyd got it.. I just arbitrarily misunderstand the intention of pb. thx. – Beverlie Sep 23 '17 at 4:28
• Hm interesting. Someone with more number theory experience than me may need to look at it in that case. – Zach Boyd Sep 23 '17 at 5:02
• For $(2)$ the composition of $3$ is $3$, not $2,1$ because $1$ is not allowed, but there is still $1$ of them. For $(4)$ you are missing the point that compositions depend on order, so $(2,3)$ is different from $(3,2)$ and there are $3$ of them, which is a Fibonacci number. Then for $n=5$ there are $8$ of them if you count order. – Ross Millikan Sep 23 '17 at 5:03
• @ZachBoyd: that is why the problem specifies compositions instead of partitions. Compositions care about order, partitions do not. – Ross Millikan Sep 23 '17 at 5:07

Let $A(n)$ be the number of compositions of $n$ with parts at least $2$. To find a composition of $n$ into parts of at least $2$ you can either start with a composition of $n-1$ and add $1$ to the last part or you can start with a composition of $n-2$ and append a new part of $2$ at the end. You have to convince yourself that you have not double counted any compositions. This gives $A(n)=A(n-1)+A(n-2)$ which is the Fibonacci recurrence. Once you have two terms that match the Fibonacci sequence, all the rest will. We have enough hand calculation for the first few terms.