<p>A fair coin is tossed 10 times. Then the probability that two heads do not occur consecutively is</p>
Step-by-Step Solution
Key Concept: Use dynamic programming by tracking states: define a_n as sequences of n tosses ending in T, and b_n as sequences ending in H (where next H cannot follow). The recurrence a_n = a_{n-1} + b_{n-1} and b_n = a_{n-1} ensures no consecutive heads.
<p><strong>Step 1:</strong> Define states for n tosses: Let a_n = valid sequences ending in T, and b_n = valid sequences ending in H.</p><p><strong>Step 2:</strong> Write recurrence relations:</p><p>• a_n = a_{n-1} + b_{n-1} (can append T after either state)</p><p>• b_n = a_{n-1} (can append H only after T)</p><p><strong>Step 3:</strong> Compute iteratively from n=1 to n=10:</p><p>n=1: a_1=1(T), b_1=1(H), total=2</p><p>n=2: a_2=2, b_2=1, total=3</p><p>n=3: a_3=3, b_3=2, total=5</p><p>n=4: a_4=5, b_4=3, total=8</p><p>n=5: a_5=8, b_5=5, total=13</p><p>n=6: a_6=13, b_6=8, total=21</p><p>n=7: a_7=21, b_7=13, total=34</p><p>n=8: a_8=34, b_8=21, total=55</p><p>n=9: a_9=55, b_9=34, total=89</p><p>n=10: a_{10}=89, b_{10}=55, total=144</p><p><strong>Step 4:</strong> Calculate probability = 144/2^{10} = 144/1024 = <strong>9/64</strong></p><p>∴ Answer: D</p>
Correct Answer: D