I'm absolutely fascinated with this concept — how Fibonacci recurrence can be applied to problems such as how to climb stairs using one step or two steps at a time (the same concept can be applied towards tiling a grid of 1 x n using single or double tiles). COMBINATORIAL PROOF: Fn = Fn-1 + Fn-2 (given F1 = 1, F2 = 2) Left Hand Side: Fn = # of ways to climb a flight of stairs using only single or double steps Right Hand Side: Case 1: Fn-1 = # of ways to climb a flight of stairs with only single and double steps, given our first step is a single step (so there are n-1 stairs left to climb) Case 2: Fn-2 = # of ways to climb a flight of stairs with only single and double steps, given our first step is a double step (so there are n-2 stairs left to climb) = total # of ways to climb a flight of stairs with only single and double steps = LHS LHS = RHS // How can we visualize this? 1 stairs: only solution = 1 single step 2 stairs: 2 single steps or 1 double step 3 stairs: we can either take a double step and then using F1 to find the remaining possible permutations for 1 stair (if we take a double step, there is only 1 way to climb the last single step), or we can take a single step and use F2 to find the remaining possible permutations for 2 stairs (if we take a single step, we have 2 stairs left. We can either climb this with one double step or two single steps) 4 stairs: we can either take a double step and use F2 to calculate how many ways to climb the remaining two steps, or take a single step and use F3 to calculate the permutations in the remaining three stairs (F3 being derived from F1 and F2 b/c Fibonacci recurrence) ... and so on. This relatively simple code was converted from a short Python function I created. It's incredible how versatile Scratch is for implementing algorithms — and it's always fun to visualize the code in cute block-sized bits :)
