Question

Let S(n) be the number of subsets of {1,2,...,n} having the following property: there are no three elements in the subset that are consecutive integers. Find a recurrence for S(n) and explain in words why S(n) satisfies this recurrence

Answer 1

S_n is the number of subsets of {1,2,...,n} with the property that there are no three elements that are consecutive integers.

Then there are two types of subsets of S_n:

CASE 1: S_n contain n, then there are 2 cases for this:

A) : The subset contains n but not n-1. In this, the subset is subset of {1,2,...,n-2} having the property that no three elenent in the subset are consecutive integers including n.

Hence, number of sets in this case is S_n-2.

B) The subset contain n and n-1. Then in this case subset will nkt contain n-2 as it cannot contain 3 consecutive integers.

Then subset can be subset of {1,2,...,n-3} having property that no three elements are consecutive integers together with n and n-2.Therefore the number of subsets that fall into this category are S_n-3

_{CASE 2:} thesubsetdoes not contain n. Then subset can be subset of {1,2,...,n-1} having property that no 3 elements are consecutive integers. Therefore tge number of subsets in this case is S_n-1.

Then the reccurence is,

S_n=S_n-1+S_n-2⁺S_n-3

We can check this recurrence as follows:

For n=0,we have one subset, a null set. S₀=1

For n=1,we have {1} and null subset S₁=2

For n=2,we have 3 subset, null subset+²C₁+²C₂=4i.e.,S₂=4

For n=3,S₃=null+³C₁+³C₂=7 as it cannot contain ³C_{3 ^{by the given property.}}

For n=4,S₄=null+⁴C₁+⁴C₂+⁴C₃-2 as {1,2,3} and {2,3,4} cannot be subset with the given property. So, S₄=13

So by reccurence relation,

S₄=S₃+S₂+S₁=>13=7+4+2

S₃=S₂+S₁+S₀=>7=4+2+1

So, it is clear that Sn satisfies this reccurence.