A die is thrown $n$ times. What is the probability that $6$ appears even number of times? A die is thrown $n$ times. What is the probability that $6$ appears even number of times (for the purpose of task $0$ is even number)?
The solution from my textbook is:
We have two hypotheses $H_1$ that the array starts with 6 and $H_2$ array does not start with 6; $p_n$ is the probability. $p_n=P(H_1)(1-p_{n-1})+P(H_2)p_{n-1}=\frac{1}{6}+\frac{2}{3}p_{n-1}$. $p_1=\frac{5}{6}$
After solving this recursive relation we get $p_n=\frac{1}{2}(1+(\frac{2}{3})^n)$.
I know how to solve recursion I just don't understand how they got it (I know probabilities of hypothesis). Also, is there any other way to approach this task?
 A: Hint: Make use of Binomial Expansion.
Assuming n to be even
$(a + b)^n = {n \choose 0}a^n + {n \choose 1}a^{n-1}b + {n \choose 2}a^{n-2}b^{2} + {n \choose 3}a^{n-3}b^{3} ... + {n \choose n}b^{n}$
and,
$(a - b)^n = {n \choose 0}a^n - {n \choose 1}a^{n-1}b + {n \choose 2}a^{n-2}b^{2} - {n \choose 3}a^{n-3}b^{3} ... + {n \choose n}b^{n}$
Adding these two, we get:
$(a + b)^n + (a - b)^n = 2({n \choose 0}a^n + {n \choose 2}a^{n-2}b^{2}...)$,
thus the quantity on the right of the above equation represents the probability of getting an even number of events $a$. Bring the $2$ from RHS to LHS,
$\frac{1}{2}((a + b)^n + (a - b)^n) = ({n \choose 0}a^n + {n \choose 2}a^{n-2}b^{2}...)$
We know from a fair, unbiased die, we have P(Die Value = 6) = 1/6 and P(Die Value != 6) = 5/6. Then, substitute $a$ for 1/6 and $b$ for 5/6 and solve.
A: The recurrence is derived as follows. Suppose that the sequence begins with a $6$. Then we must roll a $6$ an odd number of times in the remaining $n-1$ rolls (which has probability $1-p_{n-1}$) to get $6$ an even number of times in $n$ rolls. 
Similarly if the sequence does not begin with a $6$ then we need to roll a $6$ an even number of times in the remaining $n-1$ rolls (which has probability $p_{n-1}$) in order to get get $6$ an even number of times in $n$ rolls.
Together, you get the recurrence 
$$
p_n=P(H_1)(1-p_{n-1})+P(H_2)p_{n-1}
$$
Here is a another way to proceed. Let $N$ be the number of times that $6$ appears in the $n$ dice rolls. Then
$$
P(N=k)=\binom{n}{k}\left(\frac{1}{6}\right)^k\left(\frac{5}{6}\right)^{n-k}\quad (0\leq k\leq n)
$$
by way of the binomial distribution. In particular the probability generating function of $N$ is given by 
$$
G_{N}(t)=\sum_{k=0}^nP(N=k)t^k=\left(\frac{1}{6}t+\frac{5}{6}\right)^n.
$$
by the binomial theorem. Now we note that
$$
\sum_{k=0,\, k\;\text{even}}^nP(N=k)=\frac{G_{N}(1)+G_{N}(-1)}{2}=\frac{1}{2}\left(1+(2/3)^n\right)
$$
