The Recursive Staircase

f(n) = f(n-1) + f(n-2) with f(1)=1, f(2)=2. Values: 1, 2, 3, 5, 8, 13 for n=1 through 6. This is the Fibonacci sequence. The recurrence arises because every step n can only be reached from step n-1 or n-2.

Define f(n) as the number of distinct climbing sequences for n steps. The child's last move was either a 1-step (coming from step n-1) or a 2-step (coming from step n-2). This gives a recurrence identical to Fibonacci numbers. Step 1: Base cases: f(1) = 1 (only one way: take 1 step). f(2) = 2 (either 1+1 or 2 in one jump). Step 2: Recurrence: f(n) = f(n-1) + f(n-2) for n ≥ 3. This comes from: ways to arrive from n-1 (1-step) + ways to arrive from n-2 (2-step). Step 3: f(3) = f(2) + f(1) = 2 + 1 = 3. Sequences: {1,1,1}, {1,2}, {2,1}. Step 4: f(4) = f(3) + f(2) = 3 + 2 = 5. f(5) = 5 + 3 = 8. f(6) = 8 + 5 = 13. Step 5: Closed-form (Binet's formula): f(n) = (φ^n − ψ^n) / √5, where φ = (1+√5)/2 ≈ 1.618 (golden ratio) and ψ = (1−√5)/2. Step 6: This structure appears in: tree branching patterns, DNA molecule geometry, spiral arrangements in sunflowers and pinecones, financial market analysis, and recursive algorithms in computer science. Key Insight: The staircase problem is the Fibonacci sequence with a shifted index. The key structural insight — 'to know how many ways to get here, add the ways to get to the two places you could have come from' — is a template for dynamic programming that appears in dozens of interview problems.