Given n and a letter C,how many possible words of length n can be formed that are with no two consecutive C in the word.
For example,if n=3, C='b',then the word bcb,ccc,aab do not have any consecutive occurrence of 'b'.
But bbc,abb,bbb have consecutive occurrence of 'b'.
We can use only letters 'a' to 'z' to form this sort of word and can consider only lowercase letters.I have solved this problem in this way,but I'm not sure.For n=4,C='b',ans=(26^4)-C(2,1).25-C(3,1).25^2-C(4,1).25^3.
Let $w_n$ be the number of $n$ letter words where the letter $C$ doesn't occur consecutively. Then $w_n$ satisfies the recurrence relation
$$w_n = 25w_{n-1}+25w_{n-2}$$
To see with, when creating a valid word, you can either choose the first letter to be anything but $C$ (25 way to do this) and then create the rest of the word ($w_{n-1}$ ways), or choose the first letter to be $C$, which forces the next letter to be not $C$ (25 ways), then fill out the remaining $n-2$ letters ($w_{n-2}$ ways).
This, combined with the bases cases $w_1=26$ and $w_2=26^2 - 1$ is enough to solve for $w_n$. Wikipedia shows the method for solving such equations. In your case, the solution will be of the form $$ w_n = c_1(r_1)^n + c_2(r_2)^n $$ where $r_1$ and $r_2$ are the roots of the equation $x^2=25x+25$, and $c_1,c_2$ are constants.To solve for $c_1,c_2$, set $n=1$ and $n=2$ in the above equation.
