Counting / Permutation & Combination

Question

Given two positive integers n and k with the same parity, count the number of sets S = { 0< s1 < s2 < ... < sk = n }, such that s1, s3, ... are odd numbers and s2, s4, ... are even numbers

Answer 1

My proof is a little weak, maybe another tutor can add to it.   

 

n=2:  {0,1,2}   —>  F(2) = 1

 

n=3:  {0,1,2,3}

         {0,3}      —>  F(3) = 2

 

n=4:  {0,1,2,3,4}

         {0,1,4}

         {0,3,4}   —>   F(4) = 3

 

n=5:  {0,1,2,3,4,5}

          {0,1,2,5}

          {0,1,4,5}

          {0,3,4,5}

          {0,5}     —>   F(5) = 5

 

n=6:  {0,1,2,3,4,5,6}

         {0,1,2,3,6}

         {0,1,2,5,6}

         {0,1,4,5,6}

         {0,3,4,5,6}

         {0,1,6}

         {0,3,6}

         {0,5,6}            —>  F(6) = 8

 

 

This is a Fibonacci pattern.  

Assert F(n) = F(n-1)+F(n-2)  for n≥4

 

Inductive proof:

Assume  F(k) = F(k-1)+F(k-2)   for n=k,  k≥4

Need to show F(k+1) = F(k) + F(k-1) to complete the proof.

 

Consider n=k+1:

 

The number of sets consists of two components:  (1) those from the sets n=k  where we simply append k+1 to the end of each set (see bolded items below for n=6 case as an example).   In terms of k+1, there is a contribution of  F[k-1] + F[k-2] by the induction hypothesis.

 

 

 n=6: {0,1,2,3,4,5,6}
{0,1,2,3,6}
{0,1,2,5,6}
{0,1,4,5,6}
{0,3,4,5,6}
{0,1,6}
{0,3,6}
{0,5,6} 

 

The other component of sets for n=k+1 come from  n=k-1:  Here we replace k+1 for k-1 in those sets.  See bolded items below for the case n=6 as an example.  In terms of k+1 sets, there is a contribution of  F[k-2] + F[k-3] from the induction hypothesis.

 

n=6: {0,1,2,3,4,5,6}
{0,1,2,3,6}
{0,1,2,5,6}
{0,1,4,5,6}
{0,3,4,5,6}
{0,1,6}
{0,3,6}
{0,5,6} 

 

 

[ If one goes back to n=k-2, there is no contribution, since that parity is the same as same as n=k and those sets have already been counted in subsets for n=k.  ]

 

So that means  F(k+1) = [ F(k-1) + F[k-2 ] + [ F(k-2) + F(k-3) ] 

the first bracket is F(k), the 2nd is F(k-1):

 

                       F(k+1) = F(k)    +  F(k-1)     

 

Therefore,  F(n) = F(n-1) + F(n-2),   n≥4,   F(2)=1, F(3)=2