There is also a nice generating function for this problem. Fix $p$ and let $S(n,m)$ be the number of words of length $n$ using at most $p$ distinct letters, with no repetition of $m$ identical letters in a row, as defined by leonbloy. Then $ \sum_{n = 0}^\infty S(n,m) x^n = \frac{1 - x^m}{1 - px - (1-p)x^m}.$
If you're not familiar with generating functions, this means that you can get the number you're looking for pretty easily by extracting the coefficient of $x^n$ in the Taylor series for the above expression using mathematical software such as Sage, Mathematica etc. Since it's rational, i.e., a fraction of polynomials, this also allows to find another recursive formula.
Added - more details:
In general a rational generating function
$\sum_{n=0}^\infty f(n) x^n = \frac{p(x)}{1 + a_1x + \ldots + a_mx^m}$
will, for large n, obey a recurrence relation
$f(n) + a_1f(n-1) + \ldots + a_nf(n-m) = 0.$
Amazing, isn't it? See Richard Stanley - Enumerative Combinatorics Vol 1 Ch. 4, or just Google it. In this case we have the denominator
$1 - px - (1-p)x^m$
so we get the recurrence
$S(n,m) - pS(n-1,m) - (1-p)S(n-m) = 0.$
$S(n,m) = pS(n-1,m) + (1-p)S(n-m,m).$ A little checking shows this holds for $n > m$, and we have the initial values $S(n,m) = p^n$ for $n< m$, and $S(m,m) = p^m - p$.