I am currently reading my Discrete Math book and I am confused by this particular examples explanation. Can someone help me understand what this part means?
Question:
Let S = {1,2,3,4,….,n} and a_n denote the number of subsets of S that contain no consecutive integers. Find and solve a recurrence relation for a_n.
For n>= 2, if A is a subset of S and A is to be counted in a_n, there are two possibilities.
a) n is an element of A: When this happens (n-1) isn't an element of A and A-{n} would be counted in a_n-2.
I understand this part, but I included it anyways..
b) n isn't an element of A: For this case A would be counted in a_n-1.
Can someone explain to me why we are subtracting {n} from A in part a)? If A = {1, 4} and n = 4. Does it mean {1,4} – {4} = {1}? If so, wouldn't {1} also be included in a_n-1? I am confused with the subtracting part..
Best Answer
We write down, almost exactly, the argument you quoted, changing the wording a little bit in the hope things will become clearer.
Let $S_n=\{1,2,3,\dots,n\}$. We say that a subset $A$ of $S_n$ is good if $A$ does not contain any two consecutive integers. For any $k$, let $a_k$ be the number of good subsets of $S_k$.
There are two types of good subsets of $S_n$. Type 1 good subsets of $S_n$ contain the element $n$, and Type 2 good subsets of $S_n$ do not contain $n$.
We first get an expression for the number of Type 1 good subsets of $S_n$, where $n\ge 2$. Such a subset cannot contain $n-1$. So any Type 1 good subset of $S_n$ is obtainable by adding $n$ to a good subset of $S_{n-2}$. Also, if we add $n$ to a good subset of $S_{n-2}$, we always obtain a Type 1 good subset of $S_n$. So there are exactly as many good Type 1 subsets of $S_n$ as there are good subsets of $S_{n-2}$. By definition there are $a_{n-2}$ good subsets of $S_{n-2}$.
Now we obtain an expression for the number of good Type 2 subsets of $S_n$. Such a subset is a good subset of $S_{n-1}$, and any good subset of $S_{n-1}$ is a good Type 2 subset of $S_n$. So by definition there are $a_{n-1}$ good Type 2 subsets of $S_n$.
A good subset of $S_n$ is either of Type 1 or of Type 2. So the number of good subsets of $S_n$ is $a_{n-2}+a_{n-1}$. We have therefore shown that $a_n=a_{n-2}+a_{n-1}$.