Counting Recursively

Combinatorics · Axiom Academy

Discover how to solve complex counting problems by building on simpler cases. Imagine you're building a staircase with blocks. Use the slider to change how many steps high your staircase is. You're climbing stairs, but you can take either 1 step or 2 steps at a time. How many different ways can you reach the top? Come from step (n-1) and take 1 step, OR Come from step (n-2) and take 2 steps Click on the nodes below to see how the problem breaks down into smaller sub-problems. Click the button to watch the sequence unfold and discover the pattern. Instead of solving a problem all at once, we express the answer in terms of smaller instances of the same problem. This creates a chain of dependencies that eventually reaches simple base cases we can solve directly. Many counting problems have natural recursive structure: tiling patterns, paths in grids, sequences of choices, partitions of numbers. By identifying how a problem relates to smaller versions of itself, we can build efficient solutions. 1. Base cases: Simple situations you can solve directly 2. Recursive relation: How to express larger cases using smaller ones 3. Direction: Making sure each step moves toward a base case

This is the written version of the interactive lesson above. See the full Combinatorics course.