Number of vectors whose start is different from its end Consider all $n$-dimensional vectors $v$ with elements from $\{0,1\}$.  We say that if there exists a $n > j \geq 1$ such that $v_{1,\dots,j} = v_{n-j+1,\dots, n}$ then the vector is "bad". Otherwise the vector is "good". For example $v^{T} = (0,1,0,0,1)$ is bad and $(0,1,1,1)$ is good.

How many good vectors are there of length $n$?

 A: This is a problem that utilizes the principle of inclusion exclusion (see page 223 of Stanley's EC1, available for free on his website).  Let $f_=(0)$ denote the number of good vectors of length $n$, and let $f_\geq(j)$ denote the number of vectors whose first $j$ elements match its last $j$ elements.  Then by the Principle of Inclusion Exclusion: $$f_=(0) = \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j f_\geq(j).$$
We thus need only find the $f_{\geq}(j)$.  If the first $j$ match the last $j$ elements, then we have $2^j$ options for the matching elements, and $2^{n - 2j}$ for the middle elements.  We thus have $f_{\geq}(j) = 2^{n - j}$. Putting this together, we have \begin{align*} 
f_=(0) &= \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j f_\geq(j) \\
&= \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} (-1)^j 2^{n - j} \\
&= 2^n \sum\limits_{j = 0}^{\lfloor n/2 \rfloor} \left(-\frac{1}{2} \right)^j \\
&= 2^n \frac{1 - \left(-\frac{1}{2}\right)^{\lfloor n/2 \rfloor + 1} }{1 - \left(-\frac{1}{2}\right)} \\
&= \frac{2}{3}\cdot 2^{n}\left(1 + \left(-\frac{1}{2}\right)^{\lfloor n/2 \rfloor} \right).
\end{align*}
As $n$ gets large, we have roughly $\frac{2}{3} 2^n$ good vectors.
