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?

  • 2
    $\begingroup$ 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 $\endgroup$ – Zach Boyd Sep 23 '17 at 4:27
  • $\begingroup$ @ZachBoyd got it.. I just arbitrarily misunderstand the intention of pb. thx. $\endgroup$ – Beverlie Sep 23 '17 at 4:28
  • 1
    $\begingroup$ Hm interesting. Someone with more number theory experience than me may need to look at it in that case. $\endgroup$ – Zach Boyd Sep 23 '17 at 5:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 23 '17 at 5:03
  • 1
    $\begingroup$ @ZachBoyd: that is why the problem specifies compositions instead of partitions. Compositions care about order, partitions do not. $\endgroup$ – 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.

  • $\begingroup$ For the first case not to add 1 any of the part but always add 1 to end element of each case of A (n-1) $\endgroup$ – Beverlie Sep 23 '17 at 5:38

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.