probability of multiple of $3$ tosses are head in $n$ tosses 
$p_n=$ probability of multiple of $3$ tosses are head in $n$ tosses ($n\geq 0$). Find generating function of $p_n$. Also find the value of $p_n$ as $n$ tends to infinity. (Take probability of occurring head in a toss is $p$. $q= 1-p$)

I found the recurrence relation of $p_n$:
$$p_n = q^n + \Big(\frac{p}{q}\Big)^3 \sum_{k=3}^{n}\binom{k}{3}q^k\space p_{n-k}, \space n\geq 3\\ p_0 = 1, p_1=q, p_2 = q^2$$
I don't know how to find generating function for this. Thanks for any help.
 A: So, assume our coin is not fair, so that $0\leq q\leq1$ is the probability of 'Head' for a single toss. 
Let's start by writing the probability of having a "multiple of 3" number of heads in N tosses. This will be the sum of the probabilities of all different multiples of 3, from $0$ to $[\frac{n}{3}]$:
$$p_n = \sum_{k=0}^{[\frac{n}{3}]} P(\#heads = 3k) = \sum_{k=0}^{[\frac{n}{3}]} {n\choose3k}q^{3k}(1-q)^{n-3k} $$
Now, we can write the generating function by setting each of these $p_n$ to be the coefficient in an infinite power expansion:
$$\mathcal F(s) = \sum_n p_n s^n = \sum_n s^n \sum_{k=0}^{[\frac{n}{3}]} {n\choose3k}q^{3k}(1-q)^{n-3k}$$ 
Now, I don't know if there's some clever, more meaningful way of rewriting this; but in principle, it's correct!
Also, be careful: if you accept $0$ as a multiple of 3 (and it seems you do, since you set $p_0=1$), your results $p_1=0$, $p_2=0$ cannot be true, since it is always possible to end up with 0 heads!
Btw I'd be curious to see how you found that recurrence! :)
