I was doing exercises from my discrete mathematics class when I stumbled upon this one:
Show that equality holds for all $n\in\Bbb{N}$:
$\sum_{k=0}^{n}(-1)^{k}$${n-k}\choose{k}$$2^{n-2k}=n+1$.
I've managed to prove it using induction, but when I looked at the back of the book to check for a nicer proof I've only found a hint:
"Count in two ways all binary sequences length $n$ such that a $1$ is never followed by $0$".
So basically all sequences like $000111,11111,00000$.
It obvious where the $n+1$ part came from - it counts all possible positions of the change from a block of $0$'s to a block of $1$'s.
By the look of this problem, it's obvious it's one where the solution utilizes the inclusion-exclusion principle, but I have trouble coming up with a way to use it.
For example, I've tried considering a family of sets:
$A_k=\{(x_1,...,x_n)\in\{0,1\}^{n}:\forall_{i<k}\space x_i=0\}$, but that didn't yield any nice results.
Any thoughts?
We want to count binary words of length $n$ that avoid the subsequence $10$. Note the first few terms of the series ... \begin{eqnarray*} \sum_{k=0}^{n}(-1)^{k} \binom{n-k}{k} =2^n-\binom{n-1}{1}2^{n-2} +\binom{n-2}{2}2^{n-4}-\cdots. \end{eqnarray*} There are $2^n$ binary words, but these include words with $10$'s in them.
There are $\binom{n-1}{1}$ places where we could have $10$ and the other elements could be chosen in $2^{n-2}$ ways. So subtract $\binom{n-1}{1}2^{n-2}$ from $2^n$. But this has subtracted words where $10$ ocurred twice.
So add $\binom{n-2}{2} 2^{n-4}$ ... but this has added extra for those words that had $10$ thrice ... etc ...