How many four-letter words w using an n-letter alphabet satisfy... This question has two parts. The first part was easy.
a) How many four-letter words w using an n-letter alphabet satisfy $w_i \neq w_{i+1}$ for $i=1,2,3$
Simple. Choose the first letter in $n$ ways. Because no consecutive letter can have the same letter as the previous, we have $n-1$ ways for the last three for a total:
$$n \times (n-1) \times (n-1) \times (n-1) = n(n-1)^3$$

b) How many of the words in (a) also satisfy $w_4 \neq w_1$?
I'm struggling here. I thought of the possibilites, but I'm having trouble counting them.
Consider when $w_3 = w_1$ and when $w_3 \neq w_1$. Obviously, if $w_3 = w_1$, $w_4$ can be chosen in $n-1$ ways. Why? Take for example the standard alphabet. If we have the incomplete word:
A E A _
$w_4$ can be every letter except "A" to satisfy $w_4 \neq w_1$. Hence, $w_4$ has $n-1$ possibilities.
If $w_3 \neq w_1$ there are $n-2$ ways to choose $w_4$ by the same reasoning. Certainly, if we have the incomplete word:
A E C _
$w_4$ can be every letter except "A" and "C." $n-2$ ways.
But how can I count this? I thought it would be:
$$n \times (n-1)^2 \times (n-2)$$
But that doesn't take into account the special cases I considered above, does it?

The answer is $n(n-1)^2 + n(n-1)(n-2)^2$. Maybe a tree chart makes this clear but a don't know how to use tikz here :(
However I describe what I mean. You already figured out that there a two different cases: Either $w_3 = w_1$ or $w_3 \neq w_1$.
Case 1:
In the first case that $w_3 = w_1$ you already know that $w_3 = w_1$ so you don't have a choice for the third latter which gives
$$n\cdot (n-1) \cdot 1 \cdot (n-1) \quad \text{Opportunities}$$
Case 2:
In the other case you know $w_3 \neq w_1$ and $w_3 \neq w_2$ so you have $(n-2)$ opportunities for $w_3$ and you also have $w_4 \neq w_3$ and $w_4 \neq w_1$ which gives altogether (in this case)
$$n\cdot (n-1) \cdot (n-2) \cdot (n-2) \quad \text{Opportunities}$$
When you sum all opportunities together you receive what I already mentioned in the beginning.
