@BernhardWerner My favorite alternative #proof strategy for #induction proofs are #combinatorial (counting) proofs.

I suppose the standard example might be the proof of the coefficients in the binomial theorem expansion, or for the sum of binomial coefficients being powers of 2. These can be proved by induction, of course, but I'm not sure that's common given how easier it is to do a counting proof. It is also much clearer and avoids tedious algebra.

One I like is proving that the sum 1 + 2 + 3 + ⋯ + 𝑛 is 𝑛 + 1 choose 2, the binomial coefficient \(\binom{n+1}{2}\). Bijection proof, counts the same thing in two ways. The thing being counted is the number of ways of choosing two things (distinct, without repetition) from the set {0, 1, ..., 𝑛}. By definition, it is the binomial coefficient we want. The other way to count is to fix the larger number 𝑘, the remaining choices are any of the 𝑘 numbers from 0 to 𝑘 - 1. Thus, across all possible larger numbers, we get the sum from 1 to n.

An alternative alternate proof of the same, slightly more geometric is as follows: arrange dots in a triangle, 1 on row 1, 2 on row 2, and so on up to row n, with n dots. Add a phantom row of n+1 dots below. We want to add up all dots in first n rows: ∑ 𝑖. If you think of all of this as a binary tree/DAG, then every dot has two children (imagine Pascal's triangle). If you pick any two dots in the phantom row, their common ancestor is unique. So counting dots is same as picking two dots in phantom row. Which is the binomial coefficient we want.

Benjamin and Quinn's book on combinatorial proofs is amazing for interpretations of this form (I learned the first proof from it). See also: https://en.wikipedia.org/wiki/Combinatorial_proof

"While critical towards the details of Llull’s proposed categories and procedures, Leibniz was taken with his overarching vision of the combinatorial art. He drew two key aspirations from Llull’s work: the idea of fundamental conceptual elements, and the idea of a method through which to combine and calculate with them."

#leibniz #combinatorial