Solution to Determine the number of subsets of size k of the set {1, 2, . . … - Sikademy
Author Image

Archangel Macsika

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 \{1,2, \ldots, n\} is a valid subset of \{1,2, \ldots, n, n+1\} 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 F_{2}=1 and F_{3}=2 , we can easily deduce that

N(n)=F_{n+1}=\frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt{5}}

where

\begin{aligned} &\varphi=\frac{1+\sqrt{5}}{2} \\ &\psi=\frac{1-\sqrt{5}}{2} \end{aligned}

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-1310-qpid-1048