Frog-Hop Recurrence
A frog sits on step 1 of a staircase with steps numbered 1, 2, 3, … Each minute it either hops up one step or, with probability 0.3, hops up two steps. It never moves down. Let aₙ be the number of distinct sequences of hops that land the frog exactly on step n, counting only hops of size 1 and 2. Separately, a game-show contestant starts with $0 and each round either wins $1 (probability 0.7) or wins $2 (probability 0.3), independently each round. The contestant wants to reach exactly $n.
1. Write a recurrence relation for aₙ, state suitable initial conditions, and compute aₙ for n = 1 to 6. Explain why the recurrence has this form.
Read the worked answer
A sequence of hops landing on step n ends with either a 1-hop (from step n−1) or a 2-hop (from step n−2). These cases are disjoint, so aₙ = aₙ₋₁ + aₙ₋₂.\n\nInitial conditions: a₁ = 1 (one 1-hop), a₂ = 2 (1+1 or 2).\n\nCompute: a₃ = 2 + 1 = 3; a₄ = 3 + 2 = 5; a₅ = 5 + 3 = 8; a₆ = 8 + 5 = 13.\n\nSo a₁…a₆ = 1, 2, 3, 5, 8, 13 (Fibonacci-like, shifted).\n\nWhy this form: the last hop is either size 1 or size 2, and every valid sequence has exactly one of these as its final hop. The two sets of sequences are disjoint (different last hop) and together cover all sequences, so their counts add. This is the standard first-order decomposition argument for counting paths.
2. The contestant's winnings after k rounds follow a random process. Find the probability that the contestant reaches exactly $5 at some point within the first 4 rounds, and compare it with the deterministic count a₅.
Read the worked answer
Reaching exactly $5 within 4 rounds means a sequence of wins summing to 5 in at most 4 rounds. Possible compositions using 1s and 2s: 1+1+1+1+1 (5 rounds - too many), 2+1+1+1 in any order (4 rounds), 2+2+1 in any order (3 rounds).\n\nCount 4-round sequences summing to 5: exactly one 2 and three 1s → 4 arrangements. Each has probability 0.3 × 0.7³ = 0.3 × 0.343 = 0.1029. Contribution: 4 × 0.1029 = 0.4116.\n\nCount 3-round sequences summing to 5: two 2s and one 1 → 3 arrangements. Each has probability 0.3² × 0.7 = 0.09 × 0.7 = 0.063. Contribution: 3 × 0.063 = 0.189.\n\nTotal probability of reaching exactly $5 within 4 rounds ≈ 0.4116 + 0.189 = 0.6006, about 60%.\n\nComparison with a₅ = 8: the deterministic count 8 equals the number of compositions of 5 into 1s and 2s (4 compositions of length 4 plus 3 of length 3 plus 1 of length 5 = 8). The probability calculation weights each composition by its probability, so the count alone does not give the probability - the lengths matter because longer sequences are less likely under the 0.7/0.3 split. The judgement point: aₙ counts possibilities, not probabilities.
3. The contestant needs exactly $6 to buy a prize and stops as soon as they reach $6 or exceed it. Explain how the recurrence must be modified to count only sequences that hit exactly $6 without passing it, and compute that count.
Read the worked answer
If the contestant stops on reaching or exceeding $6, then sequences that overshoot are excluded. A sequence hits exactly $6 without passing it only if every partial sum stays at or below 6. Since hops are positive, the only way to pass 6 is to be at 5 and take a 2-hop, or at 4 and take a 2-hop to 6 (fine), etc. Overshooting happens from 5 with a 2-hop (to 7) or from 6 - but the process stops at 6.\n\nSo count sequences summing to 6 that never exceed 6 before the end. Since all hops are positive, any sequence summing to 6 automatically has all partial sums ≤ 6 (partial sums are strictly increasing and the final sum is 6). Therefore no sequence summing to 6 can overshoot before the end - overshooting only occurs if a hop takes the total above 6, which cannot happen in a sequence whose total is exactly 6.\n\nSo the count is simply a₆ = 13.\n\nHowever, the stopping rule affects the probability of reaching 6, not the count: some sequences that would reach 6 are never played because the contestant stopped earlier after overshooting. The count of 13 is the number of winning compositions; the probability of hitting 6 is a sum over these 13 compositions of p^(number of 2s) × 0.7^(number of 1s), and sequences that overshoot are simply failures. The recurrence for the probability P(n) of hitting n is P(n) = 0.7 P(n−1) + 0.3 P(n−2) with P(0) = 1, P(negative) = 0 - a different recurrence from the counting one.