Possible winning sequence Find number of words of length n that contain an even quantity of letters G and don't start with G ,also k denotes number of letters.
Example: n= 1 k=4   Ans is: 3
I know this is a permutation/combination question and want to formulate the logic for different values of n and k.Help me to formulate the logic behind this?
 A: You want the number of words of length $n$ that contain an even quantity of letters $G$ and don't start with $G$
This is the same as $k-1$ multiplied by the number of words of length $n-1$ that  contain an even number of letters $G$.
denote by $e(m)$ the number of words of length $m$ that contain an even number of letters $G$ and by $o(m)$ the number of words of length $m$ that contain an odd number of letters $G$.
Then $e(m+1)=(k-1)e(m)+o(m)$.This is because there are $e(m)$ words of length $m+1$ ending with every word different than $G$ and $o(m)$ words of length $m+1$ ending in $G$.
Since $e(m)+o(m)=k^m$ we get $e(m+1)=(k-2)e(m)+k^m$
We shall prove $e(m)=\dfrac{k^m+(k-2)^m}{2}$ by induction on $m$.
It is clear $e(1)=k-1=\frac{k+k-2}{2}$
Suppose $e(m)=\dfrac{k^m+(k-2)^m}{2}$ then using our recursion we get $e(m+1)=(k-2)\dfrac{k^m+(k-2)^m}{2}+k^m=\dfrac{k^{m+1}+(k-2)^{m+1}}{2}$ as desired.
Therefore the final answer to your question is $(k-1)e(n-1)=(k-1)\dfrac{k^{n-1}+(k-2)^{n-1}}{2}$
A: The not winning the first year is a pointless little complication. For $n\gt 1$, the answer is  $k-1$ times the number of ways G can win an even number of times in $m=n-1$ games. We find an expression for that. 
Perhaps G wins $0$ games. That can happen in $\binom{m}{0}(k-1)^m$ ways. 
Perhaps G wins $2$ games. That can happen in $\binom{m}{2}(k-1)^{m-2}$ ways.
Perhaps $G$ wins $4$ games. That can happen in $\binom{m}{4}(k-1)^{m-4}$ ways.
And so on. We need to add together all of these.
Now comes the trick. Note that by the Binomial Theorem we have
$$(x+1)^m=\binom{m}{0}x^m +\binom{m}{1}x^{m-1}+\binom{m}{2}x^{m-2}+\binom{m}{3}x^{m-3}+\binom{m}{4}x^{m-4}+\cdots.\tag{1}$$ 
Note also that
$$(x-1)^m=\binom{m}{0}x^m -\binom{m}{1}x^{m-1}+\binom{m}{2}x^{m-2}-\binom{m}{3}x^{m-3}+\binom{m}{4}x^{m-4}-\cdots.\tag{2}$$
Add (1) and (2), and divide by $2$. We get
$$\frac{(x+1)^m+(x-1)^m}{2}=\binom{m}{0}x^m+\binom{m}{2}x^{m-2}+\binom{x}{4}x^{m-4}+\cdots.$$
Finally, set $x=k-1$. 
A: There is a mechanical way of solving such problems on patterns (by making use of a computer, would be tedious to do by hand). 
Describe a directed graph:
\begin{align*}
  A &= \begin{bmatrix}
 & \mathrm{I} & \mathrm{S} & \mathrm{O} & \mathrm{E} \\
\mathrm{I} & 0 & k-1 & 0 & 0 \\
\mathrm{S} & 0 & 0 & 1 & k-1 \\
\mathrm{O} & 0 & 0 & k-1 & 1 \\
\mathrm{E} & 0 & 0 & 1 & k-1 \\
\end{bmatrix}
\end{align*}
where the states are 
I : The initial state
S : The state on entering first alphabet, having no G.
O : The state on entering odd number of G's.
E : The state on entering even number of G's.
and the number of ways of entering that state are the entries in the matrix $A$.
We can now deduce the generating functions for all the entries in the matrix by computing $\left(I-x\, A\right)^{-1}$, and the entry of our interest is
fourth column in the first row. Hence, the required generating function:
\begin{align*}
  G(x) &= \left(I-x\, A\right)^{-1}[0,3] \\
  \implies G(x) &= \frac{1}{2}\left(\frac{1-x}{1-k\, x}+\frac{1+x}{1-(k-2)\, x}\right)-1
\end{align*}
Extracting $[x^n]$ gives:
\begin{align*}
  f_n &= \frac{1}{2}\left(k^n-k^{n-1}+(k-2)^n+(k-2)^{n-1}\right) \\
  &= \frac{1}{2} (k-1)\left(k^{n-1}+(k-2)^{n-1}\right)
\end{align*}
A: You could build a recursion.  Let $E(n)$ be the number of ways to have $G$ win an even number of times, and $O(n)$ the number of ways to have $G$ win an odd number of times.
Start off with $E(1)=k-1$ and $O(1)=0$.
Then can you find a formula for $E(n)$ in terms of $E(n-1)$ and $O(n-1)$?
That is a start, but there is still the question of solving the recursion.
