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? 
 A: You should be trying to 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})^{\bf{n+1}}]$ because that is the formula applied to $n+1$  
$$\frac{5}{6} \cdot  \frac{1}{2}[1+(\frac{2}{3})^n] + \frac{1}{6}(1 - \frac{1}{2}[1+(\frac{2}{3})^n])=\frac 12+\frac 56\cdot \frac 12(\frac 23)^n-\frac 16\cdot \frac 12(\frac 23)^n=\frac 12[1+(\frac 23)^{n+1}]$$
Yes, you were approaching it the right way.
A: Your method is correct but the induction hypothesis should be
$$\text{Probabaility of an even number of sixes when you roll } k \text{ dice} = \frac{1}{2}\left[1+\left(\frac{2}{3}\right)^k\right]$$
(you have $n$ instead of $k$) and the thing you want to prove is 
$$\text{Probabaility of an even number of sixes when you roll } k+1 \text{ dice} = \frac{1}{2}\left[1+\left(\frac{2}{3}\right)^{k+1}\right]$$
and so, using your reasoning, you want to prove that
$$\frac{5}{6}\cdot \frac{1}{2}\left[1+\left(\frac{2}{3}\right)^k\right] + 
\frac{1}{6}\left(1- \frac{1}{2}\left[1+\left(\frac{2}{3}\right)^{k}\right]\right) = \frac{1}{2}\left[1+\left(\frac{2}{3}\right)^{k+1}\right]$$
[Also, two footnotes: odds isn't the same as probability, so the words shouldn't really be used interchangeably. And $0$ is even! Whoever wrote the question is probably a bit shaky in number theory...]
A: 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.
