0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, but still unsure. I get the idea of having both probabilities of even and odd because since odd is given as k/(2k+1), then even probability would be k/(2k). But am I trying to prove that k+1=(k+1/(2(k+1)+1)? (k+1) = (k/2k+1) + (k+1). Then get it into a single fraction, thus: (2k^2+4k+1)/(2k+1). Then solve until it matches up with the hypothesis? $\endgroup$ – PaperThin88 Oct 17 '14 at 1:51
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 17 '14 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.