For $n \geq 2$, let $S_n$ denote the set of all subsets of $\{1, 2, \ldots, n\}$ with no two consecutive numbers. For example, $\{1, 3, 5\} \in S_6$, but $\{1, 2, 4\} \notin S_6$. Then $n(S_5)$ is equal to _____

Step 1: Define the problem and notation

We are asked to find the number of such subsets for $n=5$. Let $a_n = n(S_n)$ be the number of such subsets for a set of size $n$. We need to find $a_5$.

Step 2: Calculate initial values for $a_n$

Let's start by finding the number of such subsets for small values of $n$. For $n=0$, there is one subset (the empty set). For $n=1$, the subsets are $\emptyset$ and $\{1\}$. For $n=2$, the subsets are $\emptyset$, $\{1\}$, $\{2\}$. Note that $\{1{,}2\}$ is not allowed as 1 and 2 are consecutive.

Step 3: Derive a recurrence relation

Consider a subset $A \in S_n$. There are two cases: \\ Case 1: $n \notin A$. Then $A$ must be a subset of $\{1, 2, \ldots, n-1\}$ with no consecutive numbers. There are $a_{n-1}$ such subsets. \\ Case 2: $n \in A$. Then $n-1 \notin A$ (since $n$ and $n-1$ are consecutive). So $A$ must be of the form $A' \cup \{n\}$, where $A'$ is a subset of $\{1, 2, \ldots, n-2\}$ with no consecutive numbers. There are $a_{n-2}$ such subsets. \\ Thus, $a_n = a_{n-1} + a_{n-2}$. This is the Fibonacci sequence.

Step 4: Calculate $a_3, a_4, a_5$

Using the recurrence relation $a_n = a_{n-1} + a_{n-2}$ and the initial values $a_1=2$ and $a_2=3$, we can calculate the subsequent terms. \\ $a_3 = a_2 + a_1 = 3 + 2 = 5$. The subsets are $\emptyset, \{1\}, \{2\}, \{3\}, \{1{,}3\}$. \\ $a_4 = a_3 + a_2 = 5 + 3 = 8$. \\ $a_5 = a_4 + a_3 = 8 + 5 = 13$.

More from this chapter

• Find the probability that in a random arrangement of the letters of the word MATHEMATICS, the two A's are not together.
• 36. Find the number of ways in which six people can ride a toboggan if one of a subset of three must drive. 37. (a) Find the number of ways in which five person
• In how many ways can 4 red, 3 yellow and 2 green discs be arranged in a row if the discs of the same colour are indistinguishable?
• How many numbers lying between 100 and 1000 can be formed with the digits 0, 1, 2, 3, 4, 5, if the repetition of the digits is not allowed?
• How many ways can a 2×n rectangle be tiled using 1×2 dominoes?
• The largest n N such that 3^n divides 50! is:
• How many 4-digit numbers can be formed by using the digits 1 to 9 if repetition of digits is not allowed?
• The number of 3-digit numbers, that are divisible by 2 and 3, but not divisible by 4 and 9, is

All Permutations and Combinations solutions →