<s>[INST] Probability of an even number of sixes 
We throw a fair die $n$ times, show that the probability that there are an even number of sixes is $\frac{1}{2}[1+(\frac{2}{3})^n]$. For the purpose of this question, 0 is even.

I tried doing this problem with induction, but I have problem with induction so I was wondering if my solution was correct:


*

*The base case: For $n=0$, our formula gives us $\frac{1}{2}[1+(\frac{2}{3})^0] =1$. This is true, because if we throw the die zero times, we always get zero sixes. 

*Suppose it's true for $n=k$. Then the odds of an even number of sixes is $\frac{1}{2}[1+(\frac{2}{3})^n]$, and thus the odds of an odd number of sixes is $1 - \frac{1}{2}[1+(\frac{2}{3})^n]$. 
For $n=k+1$, there are two ways the number of sixes are even:
a. The number of sixes for $n=k$ was even, and we do not throw a six for $n=k+1$: $ \frac{5}{6} \cdot  \frac{1}{2}[1+(\frac{2}{3})^n]$
b. The number of sixes for $n=k$ was odd, and we throw a six for $n=k+1$: $\frac{1}{6}(1 - \frac{1}{2}[1+(\frac{2}{3})^n])$
So the probability $p$ for an even number of sixes at $n=k+1$ is $ \frac{5}{6} \cdot  \frac{1}{2}[1+(\frac{2}{3})^n] + \frac{1}{6}(1 - \frac{1}{2}[1+(\frac{2}{3})^n])$
I have two questions


*

*How do I get from $ \frac{5}{6} \cdot  \frac{1}{2}[1+(\frac{2}{3})^n] + \frac{1}{6}(1 - \frac{1}{2}[1+(\frac{2}{3})^n])$ to $\frac{1}{2}[1+(\frac{2}{3})^n]$? I seem to have done something wrong, I can't get the algebra correct, I get $p = \frac{1}{3}[1+(\frac{2}{3})^n] + \dfrac{1}{6}$

*Other than that, is my use of induction correct? Is it rigorous enough to prove the formula? 
 [/INST] Let $E_n$ be the event that there are an even number of sixes rolled in $n$ rolls, and $O_n$ be the event that there are an odd number of sixes rolled in $n$ rolls.  Let $X_i = 1$ if roll $i$ is a $6$, otherwise $X_i = 0$.  Clearly, $$\Pr[E_n] + \Pr[O_n] = 1$$ for all $n$.  Now, observe that $$\begin{align*} \Pr[E_n] &= \Pr[E_{n-1} \cap X_n = 0] + \Pr[O_{n-1} \cap X_n = 1] \\ &= \frac{5\Pr[E_{n-1}] + \Pr[O_{n-1}]}{6} \\ &= \frac{4 \Pr[E_{n-1}] + 1}{6}.\end{align*}$$  This establishes a recursion relationship with $a_n = \Pr[E_n]$, namely $$a_n = \frac{2}{3} a_{n-1} + \frac{1}{6}, \quad a_1 = \frac{5}{6},$$ since in $n = 1$ roll, the chance of an even number of sixes is equal to the chance that no six is rolled.  Now consider a constant $c$ so that $$a_n - c = \frac{2}{3}(a_{n-1} - c).$$  If this equation is to be equivalent to the desired recursion, we must have $$c - \frac{2}{3}c = \frac{1}{6},$$ or $c = 1/2$.  Therefore, letting $b_n = a_n - 1/2$, we obtain the auxiliary recursion $$b_n = \frac{2}{3} b_{n-1}, \quad b_1 = \frac{1}{3},$$ which has the obvious geometric sequence solution $$b_n = \left(\frac{2}{3}\right)^{n-1} b_1 = \left(\frac{2}{3}\right)^{n-1} \frac{1}{3} = \frac{2^{n-1}}{3^n}.$$  Consequently, $$\Pr[E_n] = a_n = b_n + \frac{1}{2} = \frac{2^{n-1}}{3^n} + \frac{1}{2} = \frac{1}{2}\left(1 + \left(\frac{2}{3}\right)^n\right),$$ as claimed.
</s>