Arranging a $30$ character word with letters $x, y, z$ A word of length $30$ needs to be formed from the letters $x, y, z$ (repeatable) with the following conditions:


*

*$y$ cannot occur more than once consecutively

*$z$ cannot occur more than twice consecutively.
The question is how many such words are possible. 
Thanks,
Kiran
 A: Let us denote by $X_n$ the number of possible words of length $n$ ending with the letter $X$, and similarly $Y_n, Z_n$. Then the reccurence applies:
$$X_{n+1} = X_n + Y_n + Z_n$$
$$Y_{n+1} = X_n + Z_n$$
$$Z_{n+1} = X_n + Y_n$$
$$X_1 = Y_1 = Z_1 = 1$$
This can be easily programmed to obtain the requested number of possibilities:
$$X_{30} + Y_{30} + Z_{30} = X_{31} = 367'296'043'199$$
The recurrence can be further simplified by using $Y_n = Z_n$ (see the comment by @Gerry):
$$X_n = 2 X_{n-1} + X_{n-2}$$
We notice that the number of sequences of the length $n$ is $X_{n+1}$. The sequence $X_n, n \ge 1$, is $\{1, 3, 7, 17, 41, 99, 239, 577, ...\}$. This are numerators of continued fraction convergents to sqrt(2). This page gives also the explicit solution:
$$X_n = \frac{1}{2}[(1-\sqrt{2})^n + (1+\sqrt{2})^n]$$
 The sequence $Y_n$ (and $Z_n$) is $\{1, 2, 5, 12, 29, 70, 169, ...\}$ which are the Pell numbers. 
Since you are also interested in a program for generating the words, I posted a running C++ program to Ideone. The program represents a string $XYZ...$ by the integer in the base 3, $a = 012..$, which is stored as an array of integers $[0,1,2...]$. A new combination is generated by adding $1$ to $a$ in base 3 system and ignoring the forbidden combinations $..11..22..$.  
EDIT. I included the explicit reccurence for $X_n$ based on the comment by @Gerry. He mentions also the method for finding the explicit solution.
A: Consider num[L][l1][l2] = the number of words of length L starting with the two letters l1 and l2. 
Your problem is to find the sum of all num[30][l1][l2] for all possible choices of l1 and l2.
There is an induction formula to express num[L][l1][l2] in terms of num[L-1][m1][m2]
A: I suggest that you define sequences for your words of length $n$ that end with x, y, one z or two zs and find recurrences for them. The computer won't mind simultaneous linear recurrences for four sequences and then summing them.
So, for example, $azz(n)=az(n-1)$ because you can only get an ending zz from a sequence ending in z.
A: Carrying on from Jiri's 3 equations, we can eliminate $z$ to get $$x_{n+1}=x_n+x_{n-1}+y_n+y_{n-1},\qquad y_{n+1}=x_n+x_{n-1}+y_{n-1}$$ Subtracting gives $$x_{n+1}=y_{n+1}+y_n$$ Putting that into the equation for $y_{n+1}$ gives $$y_{n+1}=y_n+3y_{n-1}+y_{n-2}$$ Similar fiddling gets a recurrence for $x_n$ and a recurrence for $z_n$. 
