Suppose that $n$independent trials are performed, with trial $i$being a success with probability $1/(2i+1)$. Let $P_n$denote the probability that the total number of successes that result is an odd number.

(a) Find $P_n$for $n=1,2,3,4,5$.

(b) Conjecture a general formula for $P_n$.

(c) Derive a formula for $P_n$in terms of $P_n-1$.

(d) Verify that your conjecture in part (b) satisfies the recursive formula in part (c). Because the recursive formula has a unique solution, this then proves that your conjecture is correct.

Given:

Bernoulli trials are done in a specific order.

$S_n$-event that the $n$-th experiment is successful

$P_n$is the probability of achieving an odd number of successes in n trials.

The sum of probability of mutually exclusive occurrences described by $S_1,S_1^c,S_2,S_2^c,S_3,\dots$is pi, $i=1,2,3,4,5,...$

$P_1=P\left(S_1\right)=\frac{1}{2\times 1+1}$

In the second equality, use independence.

$P_2=P\left(S_1{S}_2^c\right)+P\left(S_1^c{S}_2\right)$

$=P\left(S_1\right)P\left(S_2^c\right)+P\left(S_1^c\right)P\left(S_2\right)$

$=\frac{1}{3}\times \left(1-\frac{1}{2\times 2+1}\right)+\left(1-\frac{1}{3}\right)\times \frac{1}{2\times 2+1}$

$=\frac{1}{3}\times \frac{4}{5}+\frac{2}{3}\times \frac{1}{5}$

$=\frac{2}{5}$

If we separate this event based on whether or not $S_3$occurred, $S_3\to$is an odd number of successes in the first two experiments, whereas $S_3^c\to$is an even number of successes in the first two experiments.

$P_3=P\left(S_1{S}_2^c{S}_3^c\right)+P\left(S_1^c{S}_2{S}_3^c\right)+P\left(S_1{S}_2{S}_3\right)+P\left(S_1^c{S}_2^c{S}_3\right)$

$=P\left(S_1\right)P\left(S_2^c\right)P\left(S_3^c\right)+P\left(S_1^c\right)P\left(S_2\right)P\left(S_3^c\right)+P\left(S_1\right)P\left(S_2\right)P\left(S_3\right)+P\left(S_1^c\right)P\left(S_2^c\right)P\left(S_3\right)$

$=\left[P\left(S_1\right)P\left(S_2^c\right)+P\left(S_1^c\right)P\left(S_2\right)\right]P\left(S_3^c\right)+\left[P\left(S_1\right)P\left(S_2\right)+P\left(S_1^c\right)P\left(S_2^c\right)\right]P\left(S_3\right)$

$=\frac{2}{5}\times \left(1-\frac{1}{2\times 3+1}\right)+\left(1-\frac{2}{5}\right)\times \frac{1}{2\times 3+1}$

$=\frac{2}{5}\times \frac{6}{7}+\frac{3}{5}\times \frac{1}{7}$

$=\frac{3}{7}$

$P_4$and $P_5$in a smaller package

$P_4=P$( odd number of successes in the first $3$experiments $\cap S_4^c$) $+$$P$(odd number of successes in the first $3$experiments $\cap S_4^{}$)

$=\frac{3}{7}\times \left(1-\frac{1}{2\times 4+1}\right)+\left(1-\frac{3}{7}\right)\times \frac{1}{2\times 4+1}$

$=\frac{3}{7}\times \frac{8}{9}+\frac{4}{7}\times \frac{1}{9}$

$=\frac{4}{9}$

$P_5=P$(odd number of successes in the first 4 experiments $\cap S_5^c$) $+P$(odd number of successes in the first $4$experiments $\cap S_5^{}$)

$=\frac{4}{9}\times \left(1-\frac{1}{2\times 5+1}\right)+\left(1-\frac{4}{9}\right)\times \frac{1}{2\times 5+1}$

$=\frac{4}{9}\times \frac{10}{11}+\frac{5}{9}\times \frac{1}{11}$

$=\frac{5}{11}$

a formula is true for the above probability is

$P_n=\frac{n}{2n+1}$

$P_{n+1}=P_n\left(1-P\left(S_{n+1}\right)\right)+\left(1-P_n\right)P\left(S_{n+1}\right)$

This is demonstrated by separating the event of an odd number of successes from the event $S_{n+1}$.

The first n attempts in an odd number of successes ($P_n$) are called $S_{n+1}$.

$S_{n+1}^c$in the first $n$attempts with an even number of successes $1-P_n$.

Substitute $P_{n+1}=\frac{n}{2n+1}$into recursion

$P_{n+1}=\frac{n}{2n+1}\times \left(1-\frac{1}{2(n+1)+1}\right)+\left(1-\frac{n}{2n+1}\right)\times \frac{1}{2(n+1)+1}$

$=\frac{n}{2n+1}\times \frac{2(n+1)}{2(n+1)+1}+\frac{n+1}{2n+1}\times \frac{1}{2(n+1)+1}$

$=\frac{n\times 2(n+1)+(n+1)}{(2n+1)\left[2\right(n+1)+1]}$

$=\frac{n+1}{2(n+1)+1}$

Because $P_{n+1}$meet the formula, this explicit formula is a recursive formula solution.

This is the only recursive formula solution.