# Proof: Probability using Induction

You have $n$ coins $C_1$, $C_2$, ..., $C_n$ for $n \in \mathbb{N}$. Each coin is weighted differently so that the probability that coin $C_i$ comes up heads is $\frac{1}{2i + 1}$. Prove by induction that if the $n$ coins are tossed, then the probability of getting an odd number of heads is $\frac{n}{2n + 1}$.

So what I have done first is prove the basecase:
Let $C_i=1$. Thus, we have the probability of coin $C_i$coming up heads as $\frac{1}{2+1}= \frac 13$.

Now let $n=1$. Then we see that $n_1= \frac 1{2+1}= \frac 13$.
Therefore the result holds when $C_i=1$ and when $n=1$.

Induction Step
Assume that when $n = k$ for $k\in \mathbb{N}$, the result is true. Thus, $n= \frac{k}{2k+1}$. We wish to show the result is true for $k+1$.

Now from here, I am unsure how to proceed. Any help is greatly appreciated!

HINT: In order to get an odd number of heads when you toss $n+1$ coins, exactly one of two things must occur:
1. You get an odd number of heads in the first $n$ coins and a tail on the $(n+1)$-st coin.
2. You get an even number of heads in the first $n$ coins and a head on the $(n+1)$-st coin.
The induction hypothesis tells you the probability of getting an odd number of heads in the first $n$ coins, and hence also the probability of getting an even number.
• @PaperThin88: No, the probability that the first $n$ include an even number of heads is $1-\frac{n}{2n+1}=\frac{n+1}{2n+1}$. Then the probability of a head with the final coin is $\frac1{2n+3}$ so the probability of this case is $\frac{n+1}{2n+1}\cdot\frac1{2n+3}$. Calculate the probability of the other case similarly, and add them to get the probability of an odd number of heads with $n+1$ coins. – Brian M. Scott Oct 17 '14 at 4:22