Determine the number of subsets of size k of the set {1, 2, . . . , n} which do not contain consecutive integers.
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
Solution:
Let call N(n)
N(n) to the number of subsets of {1,2,…,n} with no two successive numbers included.
N(0)=1, as the only subset of the empty set is the empty set itself and it hasn’t two consecutive numbers in it.
The number of subsets of {1} is 2, the empty set and the set {1} . Obviously, none of them include two successive number, then N(1)=2.
If we ask for N(n+1), we have that any subset of is a valid subset of too. On the other hand, there are subsets that include n+1 but they cannot include n too. Therefore, we have
N(n+1)=N(n)+N(n-1)
where the first term count those subsets which doesn't include n+1, and the second those which include it.
Therefore, the sequence N(n) is a close relative of the sequence of Fibonacci numbers, which starts with different initial values. As and , we can easily deduce that
where