1

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?

Beverlie
  • 2,645
  • 2
    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 04:27
  • @ZachBoyd got it.. I just arbitrarily misunderstand the intention of pb. thx. – Beverlie Sep 23 '17 at 04:28
  • @ZachBoyd but in case of n = 5 which n+2 = 7, there exist four - {7} {5,2} {3,2,2} {3,4}- which is not Fibonacci number. – Beverlie Sep 23 '17 at 04:53
  • 1
    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 05:02
  • @ZachBoyd Thx for your valuable consideration! – Beverlie Sep 23 '17 at 05:02
  • 1
    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 05:03
  • @RossMillikan now it makes sense the order matters then it comprises the Fibo-nums – Beverlie Sep 23 '17 at 05:04
  • @RossMillikan Any hint to prove this, how are the Fibonacci Numbers are characterized? – Beverlie Sep 23 '17 at 05:05
  • Actually on reflecting further, isn't it the case that 5,2 and 2,5 should be counted separately in this context, i.e. Order dies matter? In that case you get 8 ways, which is a Fibonacci number. – Zach Boyd Sep 23 '17 at 05:06
  • 1
    @ZachBoyd: that is why the problem specifies compositions instead of partitions. Compositions care about order, partitions do not. – Ross Millikan Sep 23 '17 at 05:07

1 Answers1

0

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.

Ross Millikan
  • 374,822
  • 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) – Beverlie Sep 23 '17 at 05:38