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$
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\}$.