<p>A coin is tossed <em>(m + n)</em> times, <em>m > n</em>. Show that the probability of getting (at least) <em>m</em> consecutive heads is <em>(n + 2)/2<sup>m+1</sup></em>.</p>
Step-by-Step Solution
Key Concept: Use complementary counting: find the probability that m consecutive heads do NOT occur in (m+n) tosses by tracking the 'state' of how many consecutive heads we currently have, then use a recurrence relation or direct counting of 'bad' sequences where the longest run of heads is < m.
<p><strong>Step 1: Set up using complementary probability.</strong> Let P(at least m consecutive heads) = 1 − P(no run of m consecutive heads in (m+n) tosses).</p><p><strong>Step 2: Count sequences with no m consecutive heads.</strong> Let a(k) = number of binary sequences of length k with no run of m consecutive heads. These satisfy: a(k) = a(k-1) + a(k-2) + ... + a(k-m) for k ≥ m, with initial conditions a(0)=1, a(1)=2, ..., a(m-1)=2^(m-1).</p><p><strong>Step 3: Solve the recurrence.</strong> For the range k = m to m+n, the key observation is that sequences without m consecutive heads follow: a(m+n) = 2·a(m+n-1) − a(m+n-m-1) = 2·a(m+n-1) − a(n-1).</p><p><strong>Step 4: Evaluate counts.</strong> Through careful computation or induction: a(m+n) = 2^(m+n) − (n+2)·2^(n-1).</p><p><strong>Step 5: Calculate probability.</strong> P(at least m consecutive heads) = [2^(m+n) − a(m+n)] / 2^(m+n) = [(n+2)·2^(n-1)] / 2^(m+n) = <strong>(n+2)/2^(m+1)</strong></p>
Correct Answer: (n+2)/2^(m+1)