Proof: Probability using Induction

Question

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!

Answer 1

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.