Snake Oil Method

Combinatorics · Axiom Academy

A systematic technique for proving combinatorial identities using generating functions Consider a classic combinatorial identity that seems difficult to prove directly: How do we prove this? Direct combinatorial arguments can be tricky. The Snake Oil Method provides a systematic alternative. The method consists of three systematic steps: Identify the free variable - Choose a variable to sum over (usually the one that appears in the most complex way) Form the generating function - Multiply both sides by x^n and sum over all n Simplify and compare - Use known generating function identities to simplify both sides Let's see these steps in action with our example. 3. Step 1: Identify the Free Variable We have two variables: k (the summation index) and n (appears on the right side). We choose n as our free variable because it appears in a simple way on the right. 4. Step 2: Form the Generating Function Multiply both sides by x^n and sum over all n ≥ 0: Now we can interchange the order of summation on the left side: This is the key algebraic step - swapping the sum over n and k. 5. Step 3: Simplify and Compare Now we recognize the inner sum as a binomial series: The right side is already simple: Both sides equal the same generating function, so by comparing coefficients of x^n, our original identity is proved!

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