JEE Advanced 2000

LEVELJEE Advanced

Animated Solution for Mathematics - Probability: A coin has probability $p$ of showing head when tossed. It is tossed $n$ times. Let $p_{n}$ denote the probability that no two (or more) consecutive heads occur. Prove that $p_{1} = 1, p_{2} = 1 - p^{2}$ and $p_{n} = (1 - p) p_{n - 1} + p (1 - p) p_{n - 2}$ for all $n \geq 3$ . Prove by induction on $n$ , that $p_{n} = A α^{n} + B β^{n}$ for all $n \geq 1$ , where $α$ and $β$ are the roots of quadratic equation $x^{2} - (1 - p) x - p (1 - p) = 0$ and $A = \frac{p ^{2} + β - 1}{α β - α ^{2}}, B = \frac{p ^{2} + α - 1}{α β - β ^{2}}$ .

Q: Wait, why does the recurrence go back to $n-2$? Why can't we just use $n-1$?

That is a brilliant question! If we only looked at $n-1$, we wouldn't know if the last toss was a Head or a Tail. If the last toss was a Head, we are restricted (we cannot add another Head). If it was a Tail, we are free. By going back to $n-2$, we account for the 'Head-Tail' block, which is the only way to safely extend a sequence ending in a Head. It is the only way to capture the full history required to make a valid decision.

Progressive Hints

Hint 1

Hint 1 (The Spark): Visualize the sequence of

n

tosses as a growing chain. The constraint 'no consecutive heads' is a local constraint. If you are at the

n

-th toss, the validity of your sequence depends entirely on whether the

(n - 1)

-th toss was a Head or a Tail. Focus on the state of the last two tosses to determine if you can safely add another.

Hint 2

Hint 2 (The Arsenal): You are dealing with a linear homogeneous recurrence relation. When you see a problem where the state at step

n

depends on steps

n - 1

and

n - 2

, your toolkit must include the 'Characteristic Equation' method. Assume a solution of the form

p_{n} = x^{n}

and derive the quadratic equation that governs the system.

Hint 3

Hint 3 (The Execution): To break the mental block, write down the two mutually exclusive scenarios for the start of your sequence: either it starts with a Tail (probability

1 - p

) or it starts with a Head-Tail (probability

p (1 - p)

). This leads directly to the recurrence:

p_{n} = (1 - p) p_{n - 1} + p (1 - p) p_{n - 2}

. Use this to set up your characteristic equation.

Visualized Solution

Defining the Probability $p_{n}$

Let $p_{n}$ be the probability of having no consecutive heads in $n$ tosses.
Probability of Head: $P (H) = p$
Probability of Tail: $P (T) = 1 - p$
Goal: Find a recurrence relation for $p_{n}$ and solve it.

Base Case: $n = 1$

For $n = 1$ , the possible outcomes are ${H, T}$ .
Since there is only one toss, consecutive heads are impossible.
Therefore, any outcome is valid.
$p_{1} = P (H) + P (T) = p + (1 - p) = 1$

Base Case: $n = 2$

For $n = 2$ , the outcomes are ${H H, H T, T H, T T}$ .
The only invalid outcome is $H H$ (consecutive heads).
Probability of $H H$ is $P (H) \times P (H) = p^{2}$ .
$p_{2} = 1 - P (H H) = 1 - p^{2}$

Recurrence: Case 1 (First toss is Tail)

Assume we are making $n$ tosses.
Case 1: The first toss is a Tail ( $T$ ).
The probability of this happening is $(1 - p)$ .
We now have $n - 1$ tosses left, and we still need to avoid consecutive heads.
The probability of success for the remaining tosses is $p_{n - 1}$ .
Contribution to $p_{n} = (1 - p) p_{n - 1}$ .

Recurrence: Case 2 (First toss is Head)

Case 2: The first toss is a Head ( $H$ ).
The probability of this is $p$ .
To avoid $H H$ , the second toss MUST be a Tail ( $T$ ).
The probability of the sequence $H T$ is $p (1 - p)$ .
We now have $n - 2$ tosses left, with probability of success $p_{n - 2}$ .
Contribution to $p_{n} = p (1 - p) p_{n - 2}$ .

The Master Recurrence Relation

Since Case 1 and Case 2 are mutually exclusive and cover all valid starting sequences:
$p_{n} = P (Starts with T) + P (Starts with H T)$
$p_{n} = (1 - p) p_{n - 1} + p (1 - p) p_{n - 2}$
This is a second-order linear homogeneous recurrence relation, valid for $n \geq 3$ .

The Characteristic Equation

To solve $p_{n} = (1 - p) p_{n - 1} + p (1 - p) p_{n - 2}$ , we assume a solution of the form $p_{n} = x^{n}$ .
Substitute into the recurrence:
$x^{n} = (1 - p) x^{n - 1} + p (1 - p) x^{n - 2}$
Divide the entire equation by $x^{n - 2}$ (assuming $x \neq = 0$ ):
$x^{2} = (1 - p) x + p (1 - p)$
Rearranging gives the characteristic equation: $x^{2} - (1 - p) x - p (1 - p) = 0$

General Solution Form

Let the roots of the characteristic equation $x^{2} - (1 - p) x - p (1 - p) = 0$ be $α$ and $β$ .
Since it's a second-order linear recurrence, the general solution is a linear combination of the roots.
$p_{n} = A α^{n} + B β^{n}$
Here, $A$ and $B$ are constants that depend on the initial conditions ( $p_{1}$ and $p_{2}$ ).

Solving for Constants $A$ and $B$

Substitute $n = 1$ : $p_{1} = A α + B β = 1$
Substitute $n = 2$ : $p_{2} = A α^{2} + B β^{2} = 1 - p^{2}$
We have a system of two linear equations in variables $A$ and $B$ .
From the first equation, we can express $B$ as: $B = \frac{1 - A α}{β}$

Finalizing Constants $A$ and $B$

Substitute $B$ into the second equation:
$A α^{2} + (\frac{1 - A α}{β}) β^{2} = 1 - p^{2}$
$A α^{2} + β - A α β = 1 - p^{2}$
$A (α^{2} - α β) = 1 - p^{2} - β$
$A = \frac{1 - p ^{2} - β}{α ^{2} - α β} = \frac{p ^{2} + β - 1}{α β - α ^{2}}$
By symmetry, $B = \frac{p ^{2} + α - 1}{α β - β ^{2}}$

00:00 / 00:00

The Sigma Insight: Total Probability Theorem

Solution Diagram

Analyzing the Setup

We are tossing a coin

n

times, where the probability of getting a Head is

p

and a Tail is

1 - p

. We seek the probability

p_{n}

that no two heads appear consecutively.

For

n = 1

, the possible outcomes are

H

and

T

. Since neither contains

H H

, the probability is:

p_{1} = p + (1 - p) = 1

For

n = 2

, the outcomes are

H H, H T, T H, T T

. The only forbidden sequence is

H H

, which occurs with probability

p^{2}

. Thus, the probability of success is:

p_{2} = 1 - p^{2}

The Recurrence Logic

To find

p_{n}

, we partition the valid sequences based on the first toss.

If the first toss is a Tail (probability

1 - p

), we are left with

n - 1

tosses that must contain no consecutive heads. This contributes:

(1 - p) p_{n - 1}

If the first toss is a Head (probability

p

), the second toss must be a Tail (probability

1 - p

) to avoid

H H

. We are then left with

n - 2

tosses that must contain no consecutive heads. This contributes:

p (1 - p) p_{n - 2}

Summing these mutually exclusive cases, we obtain the master recurrence relation:

p_{n} = (1 - p) p_{n - 1} + p (1 - p) p_{n - 2}

The Algebraic Elegance

This is a second-order linear homogeneous recurrence relation. We assume a solution of the form

p_{n} = x^{n}

, which leads to the characteristic equation:

x^{2} - (1 - p) x - p (1 - p) = 0

Let the roots of this quadratic equation be

α

and

β

. The general solution is expressed as:

p_{n} = A α^{n} + B β^{n}

To determine the constants

A

and

B

, we apply our base cases

p_{1} = 1

and

p_{2} = 1 - p^{2}

. This yields a system of linear equations:

A α + B β = 1

A α^{2} + B β^{2} = 1 - p^{2}

Solving this system, we find the constants:

A = \frac{p ^{2} + β - 1}{α β - α ^{2}}

B = \frac{p ^{2} + α - 1}{α β - β ^{2}}

By solving this system, you have successfully navigated the logic of constraints, the beauty of recurrence, and the power of algebraic substitution to determine the probability of avoiding consecutive heads.

Common Traps & FAQs

Wait, why does the recurrence go back to

n - 2

? Why can't we just use

n - 1

That is a brilliant question! If we only looked at

n - 1

, we wouldn't know if the last toss was a Head or a Tail. If the last toss was a Head, we are restricted (we cannot add another Head). If it was a Tail, we are free. By going back to

n - 2

, we account for the 'Head-Tail' block, which is the only way to safely extend a sequence ending in a Head. It is the only way to capture the full history required to make a valid decision.

Can't I just use the Binomial Theorem to count the valid sequences?

The Binomial Theorem is powerful, but it counts total occurrences of Heads, not the *order*. Here, order is everything! The constraint 'no consecutive heads' is a structural constraint, not a counting one. Recurrence relations are the natural language for structural constraints where the past dictates the future possibilities.

Why do we assume

p_{n} = x^{n}

for the characteristic equation?

This is a standard technique for solving linear homogeneous recurrence relations with constant coefficients. Just as we assume

y = e^{m x}

for linear differential equations, we assume

p_{n} = x^{n}

for recurrences. It transforms a recursive relationship into an algebraic one, allowing us to find the 'roots' that define the growth of the probability sequence.

Visualized Solution

Defining the Probability $p_{n}$

Base Case: $n = 1$

Base Case: $n = 2$

Recurrence: Case 1 (First toss is Tail)

Recurrence: Case 2 (First toss is Head)

The Master Recurrence Relation

The Characteristic Equation

General Solution Form

Solving for Constants $A$ and $B$

Finalizing Constants $A$ and $B$

The Sigma Insight: Total Probability Theorem

Analyzing the Setup

The Recurrence Logic

The Algebraic Elegance

Similar Questions

A coin has probability $p$ of showing head when tossed. It is tossed $n$ times. Let $p_{n}$ denote the probability that no two (or more) consecutive heads occur. Prove that $p_{1} = 1, p_{2} = 1 - p^{2}$ and $p_{n} = (1 - p) p_{n - 1} + p (1 - p) p_{n - 2}$ for all $n \geq 3$ .

A box contains 12 red and 6 white balls. Balls are drawn from the box one at a time without replacement. If in 6 draws there are at least 4 white balls, find the probability that exactly one white is drawn in the next two draws. (binomial coefficients can be left as such)

An urn contains $m$ white and $n$ black balls. A ball is drawn at random and is put back into the urn along with $k$ additional balls of the same colour as that of the ball drawn. A ball is again drawn at random. What is the probability that the ball drawn now is white?

Two balls are selected at random one by one without replacement from a bag containing 4 white and 6 black balls. If the probability that the first selected ball is black, given that the second selected ball is also black, is $\frac{m}{n}$ where $g cd (m, n) = 1$ , then $m + n$ is equal to:

Bag 1 contains 4 white balls and 5 black balls, and Bag 2 contains n white balls and 3 black balls. One ball is drawn randomly from Bag 1 and transferred to Bag 2. A ball is then drawn randomly from Bag 2. If the probability, that the ball drawn is white, is $29/45$ then n is equal to:

A bag contains 6 white and 4 black balls. A die is rolled once and the number of balls equal to the number obtained on the die are drawn from the bag at random. The probability that all the balls drawn are white is

Visualized Solution

Defining the Probability .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } pn​

Base Case: .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } n=1

Base Case: .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } n=2

Recurrence: Case 1 (First toss is Tail)

Recurrence: Case 2 (First toss is Head)

The Master Recurrence Relation

The Characteristic Equation

General Solution Form

Solving for Constants .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } A and .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } B

Finalizing Constants .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } A and .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } B

The Sigma Insight: Total Probability Theorem

Analyzing the Setup

The Recurrence Logic

The Algebraic Elegance

Similar Questions

A box contains 12 red and 6 white balls. Balls are drawn from the box one at a time without replacement. If in 6 draws there are at least 4 white balls, find the probability that exactly one white is drawn in the next two draws. (binomial coefficients can be left as such)

A bag contains 6 white and 4 black balls. A die is rolled once and the number of balls equal to the number obtained on the die are drawn from the bag at random. The probability that all the balls drawn are white is

Defining the Probability $p_{n}$

Base Case: $n = 1$

Base Case: $n = 2$

Solving for Constants $A$ and $B$

Finalizing Constants $A$ and $B$