Question

A player tosses a coin and is to score one point for every head turned up and two for every tail. He is to play on until his score reaches or passes $n$ . If ${{P}_{n}}$ is the chance for attaining exactly $n$ , then ${{P}_{n}}=$\[\]
A.$\dfrac{1}{2}\left( {{P}_{n-1}}+{{P}_{n-2}} \right)$\[\]
B. $\dfrac{1}{2}\left( 2{{P}_{n-1}}+{{P}_{n-2}} \right)$\[\]
C. $\dfrac{1}{2}\left( {{P}_{n-1}}-{{P}_{n-2}} \right)$\[\]
D. None of these \[\]

Answer 1

Hint:The player can attain $n$ by tossing $n$ heads we find its probability $P\left( n\text{ Heads} \right)$. The player can also attain $n$ by tossing $n-2$ heads and 1 tail We find its probability $P\left( n-1\text{ heads, 1 Tails} \right)$ . Similarly we find $P\left( n-4\text{ heads, 2 Tails} \right)$. $P(n-6\text{ Heads,3 Tails})...$. The required probability ${{P}_{n}}$ is the sum total of these probabilities. So we add and get an expression in $n$ of ${{P}_{n}}$. We replace $n$ with $n-1,n-2$ to get ${{P}_{n-1}},{{P}_{n-2}}$. We add them to find a relationship among ${{P}_{n}},{{P}_{n-1}},{{P}_{n-2}}.$\[\]

Complete step by step answer:
A player tosses a coin and is to score 1 point or every head(H) turned up and 2 for every tail(T). He is to play on until his score reaches or passes $n$ and we are asked to find the probability of attaining exactly $n$ denoted as ${{P}_{n}}$.\[\]
Let assume that he attains with $n$ number of heads with the outcome of the tosses as H, H,H,...($n$ number of times). The probability of getting ahead in one coin toss is $\dfrac{1}{2}$. So in this case we have the probability $P(n\text{ Heads})$
\[P(n\text{ Heads})=\dfrac{1}{2}\times \dfrac{1}{2}\times ...\left( n\text{ times} \right)=\dfrac{1}{{{2}^{n}}}\]

The player can also attain $n$ with $\left( n-2 \right)$ number of heads and 1 Tail where we can write the outcomes H, H ,H ...($n-2$ number of times), T. The outcomes can happen with any combination where the tail outcome T can be placed within $n-2-1=n-3$ gaps between heads tosses, in the beginning at the first toss and at the end at the last toss. So number of such possible places for T is $n-3+1+1=n-1$. We can chose any 1 place out of $n-1$ places in $^{n-1}{{C}_{1}}$ way. So the probability here is
\[P(n-2\text{ Heads,1 Tail})=\dfrac{1}{2}\times \dfrac{1}{2}\times ...\left( n-2\text{ heads} \right)\times \dfrac{1}{2}\left( 1\text{ tail} \right)\times \left( ^{n-1}{{C}_{1}} \right)=\dfrac{^{n-1}{{C}_{1}}}{{{2}^{n-1}}}\]

We can similarly find the probability of attaining $n$ with $n-4$ heads and 2 tails with outcomes H,H,H,...( $n-4$ times ),T,T.

\[P(n - 4{\text{ Heads,2 Tails}}) = \dfrac{1}{2} \times \dfrac{1}{2} \times ...\left( {n - 4{\text{ heads}}} \right) \times \dfrac{1}{2} \times \dfrac{1}{2}\left( {{\text{2 tails}}} \right) \times \left( {^{n - 1}{C_2}} \right) = \dfrac{{^{n - 1}{C_2}}}{{{2^{n - 2}}}}\]

We can go on to find the probabilities of $P(n-6\text{ Heads,3 Tails}),P(n-8\text{ Heads,4 Tails})$, $,P(n-10\text{ Heads,5 Tails})...$. So we have ${{P}_{n}}$ as the sum of probability of $P\left( n\text{ Heads} \right)$, $P\left( n-1\text{ heads, 1 Tail} \right)$ , $P\left( n-4\text{ heads, 2 Tails} \right)$. $P(n-6\text{ Heads,3 Tails})...$. So we have,

\[\begin{align}
  & {{P}_{n}}=\dfrac{1}{{{2}^{n}}}+\left( ^{n-1}{{C}_{1}} \right)\dfrac{1}{{{2}^{n-1}}}+\left( ^{n-2}{{C}_{2}} \right)\dfrac{1}{{{2}^{n-2}}}+... \\
 & \Rightarrow {{P}_{n}}=\dfrac{1}{{{2}^{n}}}\left( 1{{+}^{n-1}}{{C}_{1}}\cdot 2{{+}^{n-2}}{{C}_{2}}\cdot {{2}^{2}}+... \right)...(1) \\
\end{align}\]
We replace $n$ with $n-1$ and then $n-2$ to get
\[\begin{align}
  & {{P}_{n-1}}=\dfrac{1}{{{2}^{n-1}}}\left( 1{{+}^{n-2}}{{C}_{1}}\cdot 2{{+}^{n-3}}{{C}_{2}}\cdot {{2}^{2}}+... \right) \\
 & \Rightarrow {{P}_{n-1}}=\dfrac{1}{{{2}^{n}}}\left( 2{{+}^{n-2}}{{C}_{1}}\cdot {{2}^{2}}{{+}^{n-3}}{{C}_{2}}\cdot {{2}^{3}}+... \right)...(2) \\
 & {{P}_{n-2}}=\dfrac{1}{{{2}^{n-2}}}\left( 1{{+}^{n-3}}{{C}_{1}}\cdot 2{{+}^{n-4}}{{C}_{2}}\cdot {{2}^{2}}+... \right) \\
 & \Rightarrow {{P}_{n-2}}=\dfrac{1}{{{2}^{n}}}\left( 4{{+}^{n-3}}{{C}_{1}}\cdot {{2}^{3}}{{+}^{n-4}}{{C}_{2}}\cdot {{2}^{4}}+... \right)...(3) \\
\end{align}\]
We add equation (1) and (2) to get,
\[\begin{align}
  & {{P}_{n-1}}+{{P}_{n-2}} \\
 & =\dfrac{1}{{{2}^{n}}}\left( 6{{+}^{n-2}}{{C}_{1}}\cdot {{2}^{2}}{{+}^{n-3}}{{C}_{2}}\cdot {{2}^{3}}{{+}^{n-3}}{{C}_{1}}\cdot {{2}^{3}}{{+}^{n-4}}{{C}_{3}}\cdot {{2}^{4}}{{+}^{n-4}}{{C}_{2}}\cdot {{2}^{4}}... \right) \\
 & =\dfrac{2}{{{2}^{n}}}\left( 3{{+}^{n-2}}{{C}_{1}}\cdot 2{{+}^{n-3}}{{C}_{2}}\cdot {{2}^{2}}{{+}^{n-3}}{{C}_{1}}\cdot {{2}^{2}}{{+}^{n-4}}{{C}_{3}}\cdot {{2}^{3}}{{+}^{n-4}}{{C}_{2}}\cdot {{2}^{3}}... \right) \\
 & =\dfrac{2}{{{2}^{n}}}\left( 3{{+}^{n-2}}{{C}_{1}}\cdot 2+\left( ^{n-3}{{C}_{2}}{{+}^{n-3}}{{C}_{1}} \right){{2}^{2}}+\left( ^{n-4}{{C}_{3}}{{+}^{n-4}}{{C}_{2}} \right)\cdot {{2}^{3}}... \right) \\
\end{align}\]
We know the formula that $^{n}{{C}_{k}}{{=}^{n-1}}{{C}_{k}}{{+}^{n-1}}{{C}_{k-1}}$.We use it and proceed to get,
\[\begin{align}
  & =\dfrac{2}{{{2}^{n}}}\left( 3{{+}^{n-2}}{{C}_{1}}\cdot 2+\left( ^{n-2}{{C}_{2}} \right){{2}^{2}}+\left( ^{n-3}{{C}_{3}} \right){{2}^{3}}... \right) \\
 & =\dfrac{2}{{{2}^{n}}}\left( 1+2{{+}^{n-2}}{{C}_{1}}\cdot 2+\left( ^{n-2}{{C}_{2}} \right){{2}^{2}}+\left( ^{n-3}{{C}_{3}} \right){{2}^{3}}... \right) \\
\end{align}\]
We use $^{n-2}{{C}_{0}}=1$ and get ,
\[\begin{align}
  & =\dfrac{2}{{{2}^{n}}}\left( 1{{+}^{n-2}}{{C}_{0}}\cdot 2{{+}^{n-2}}{{C}_{1}}\cdot 2+\left( ^{n-2}{{C}_{2}} \right){{2}^{2}}+\left( ^{n-3}{{C}_{3}} \right){{2}^{3}}... \right) \\
 & =\dfrac{2}{{{2}^{n}}}\left( 1+\left( ^{n-2}{{C}_{0}}{{+}^{n-2}}{{C}_{1}} \right)\cdot 2+\left( ^{n-2}{{C}_{2}} \right){{2}^{2}}+\left( ^{n-3}{{C}_{3}} \right){{2}^{3}}... \right) \\
 & =\dfrac{2}{{{2}^{n}}}\left( 1+\left( ^{n-1}{{C}_{1}} \right)2+\left( ^{n-2}{{C}_{2}} \right){{2}^{2}}+\left( ^{n-3}{{C}_{3}} \right){{2}^{3}}... \right) \\
 & =2{{P}_{n}} \\
\end{align}\]
So we have ${{P}_{n}}=\dfrac{1}{2}\left( {{P}_{n-1}}+{{P}_{n-2}} \right)$ and the correct option is A. \[\]

Note:
 We note that we could add up the probabilities because these cases are mutually exclusive events means they cannot happen at the same time. We can alternatively find the recurrence formula considering the last toss the player has to make to attain $n$. We get two possible cases here. His last score was $n-1$ after which he tossed ahead making the score $n-1+1=n$ or the last score was $n-2$ after which he tossed a tail making the score $n-2+2=n$. We add up the probabilities in both cases to get the result.