# number of subsets that has no two consecutive elements

I have this question in my combinatorics course. Find the number of subsets of the set $$\{1,2,...,n\}$$ such that it doesn't contain any two consecutive elements. Using Principle of Inclusion-Exclusion.

I tried doing it by subtracting all subsets that have 2 or more consecutive elements but the solution is not taking care of repetitions and It is very confusing. Can someone suggest a way to do this by PIE?

Attempt: Going by the suggestion given by @Wuestenfux and this thought also crossed my mind that takes $$A_i$$ to be the set of subsets containing $$i$$ and $$i+1$$. But to calculate $$\sum_{I\subseteq[n],I\ne\phi}(-1)^{|I|}|\bigcap_{i\in I}A_i|$$ let for $$|I|=k$$, where $$k$$ is an integer in $$1,2,...,n$$. to calculate $$|\bigcap_{i\in I}A_i|$$ for this, we have to take cases on the $$k$$ integers we choose because all will give different values.

Example: If $$k=2$$, $$I$$ could be $$\{1,2\}$$ or $$\{1,3\}$$ giving $$|A_1\bigcap A_2|=2^{n-3}$$ whereas ,$$|A_1\bigcap A_3|=2^{n-4}$$.

So my question now is how to find a general $$|\bigcap_{i\in I}A_i|$$ if $$|I|=k$$

• PIE will handle the repetitions, for example let $E(z)$ denotes the counting of a consecutive $z$ observed and $n=3$, then $E(\{1,2\})+E(\{2,3\})-E(\{1,2\}\land\{2,3\})$ will appears in PIE and count $\{1,2,3\}$ exactly once($1+1-1=1$). Notice that $E(\{1,2\}\land\{2,3\})=E(\{1,2,3\})$, which is your consideration of "have 2 or more consecutive elements". And my $E(\{1,2\})$ is exactly $|A_1|$ in @Wuestenfux's answer. Oct 7 '18 at 7:24
• @MarkoRiedel The question in the link is asking permutations of the e$n+1$ digits, but this question is about the total number of subsets, ie. all digits need not be present in the subset.
– sonu
Oct 7 '18 at 12:28

Hint: Take $$A=\{1,\ldots,n\}$$ and define $$A_i$$ as the set of subsets of $$A$$ which contain $$i$$ and $$i+1$$, where $$1\leq i\leq n-1$$. Using inclusion-exclusion, you will find the cardinality of $$P(A)\setminus (\bigcup_{i=1}^{n-1} A_i)$$.
Added hint: You have to consider the cardinality of $$\bigcap_{j\in I} A_j$$ for each nonzero index set $$I\subseteq\{1,\ldots,n-1\}$$.