Number of subsets such that no subset contains any two consecutive terms

Question

A set $S={1,2,3,......20}$ in how many ways can a subset of set $S$ be made such that no subset contains any two consecutive terms. e.g ${1,5,4}$ is invalid.

Could someone give me hint as how to approach this question?

Answer 1

Let us do a general problem. Let $A=\{1,2,3, \ldots ,n\}$. We want subsets of $A$ such that they do not contain consecutive integers. Let $a_n$ be the number of such GOOD subsets. Now consider two scenarios.

1. GOOD subsets that contain $n$.
2. GOOD subsets that do not contain $n$.

If $n$ is there in a GOOD subset then by the condition given $n-1$ cannot be in that subset. Hence if we start with any good subset of $\{1,2, \ldots ,n-2\}$ and then tag along $n$ to it, we can obtain a GOOD subset that contains $n$. This can be done in $a_{n-2}$ ways.

If a GOOD subset does not contain $n$, then it must be a good subset of the set $\{1,2,3, \ldots, n-1\}$. The number of such GOOD subsets is $a_{n-1}$.

Thus we get a Fibonacci recurrence, $$a_{n}=a_{n-1}+a_{n-2}.$$ with $a_1=2$ and $a_2=3$.

For your particular problem you want $a_{20}$.