# Inducting Piles of Sand

**Take a pile of sand. ^{1}**

**Is it a pile of sand?**

**Of course.** (duh)

**Now add one grain of sand to this pile. Is it still a pile?**

**Yes, adding a single grain of sand to any pile of sand, yields a pile of sand.**

**Therefore, I claim, if you can add any number of grains of sand to a pile of sand, you get another pile of sand. It is proven.**

**It may seem like that proof is build on sand, but it’s actually quite solid. This method of proof is called mathematical induction (as distinct from philosophical induction).**

**Most mathematical statements, like “the sum of the squares of the legs of a right triangle is the square of its hypotenuse” only needs to be proven once. You prove it, and say “ta-da!” then you’re done.**

**But some problems, like the unfaithful husbands from the last blog post, don’t lend themselves well to “ta-da!”-styled proofs.**

**For instance, the sum of the first n natural numbers ^{2} is**

**How would you go about proving this? **

**You might start by trying a couple numbers:**

**So far, all of these cases work. That might be enough to convince you that this equation holds true, but it doesn’t make mathematicians happy. There is a history of conjectures being disproved with massive counterexamples, so we really shouldn’t be jumping to conclusions. **

**The goal here is to prove that this equation holds for all natural numbers. It’s impossible to test every case (as there are infinitely many), so we have to do something clever. **

**Let’s assume, just for the sake of argument, that our formula holds for case k. Here, k represents any natural number. So, by assumption…**

**Now I’ll ask what might seem like a weird question now, but will make sense later: Does this formula also hold for the number k+1? Symbolically…**

**From our assumption, the sum of the first k integers is k(k+1)/2, so we can replace the 1+2+3+...+k with k(k+1)/2:**

**On the left hand side, we can find a common denominator and simplify:**

**This last step ^{3} is clearly correct, so I’ve removed the question mark.**

**How should we interpret this result? Well, we started with an assumption, so we can’t claim this is always true (or at least not yet). What we can say is that IF the our assumption is true, then our conclusion is also true.**

**In this case, we say “If the formula holds for some natural number, k, then it also holds for the next natural number”**

**Take a second to fully digest that**

**So why is this significant?**

**We know the formula works for n = 1, as**

**“If the formula holds for some natural number, k, then it also holds for the next natural number.” **

**1 is a natural number, so say k = 1. Because we know the formula holds for 1, it also must hold for the next natural number: 2. **

**Now say that k = 2. Because we know the formula holds for 2, it must also hold for the next natural number: 3. **

**Now say that k = 3. Because we know the formula holds for 3, it must also hold for the next natural number: 4. **

**And on and on and on, each number a domino in a never-ending chain.**

**This process of mathematical induction can be split into two steps:**

**Prove the base case. (in our example, n = 1)****Assume that one case is true, and prove that the next**^{4}case is true.

**If you manage to do both these things, congratulations! You have completed a proof by mathematical induction.**

^{1} s in S, S = { x | x is a pile of sand}

^{2}Ok, yes there are some “ta-da!” proofs of this formula, but this is the “hello world” of induction, so here we are

^{3}The last step is done by factoring out a (k+1) from both terms in the numerator

^{4}One itty-bitty requirement here: the notion of “next” must always be defined.