Proof by induction. Domino, motherfuckers!

Damn right I’m coming at you with another method of proof. This time we’re talking about proof by induction. Induction is probably the least intuitive of the basic methods of proof – at least it was for me. Don’t worry, fam. We out here to make this shit easy peasy lemon squeezy.

At it’s core, proof by induction is meant to prove something is true for all natural numbers. Natural numbers, btw, are all of the non-negative integers (0, 1, 2, 3, etc.) – sometimes referred to with a fancy-ass letter $\mathbb{N}$. So if we ever have something to prove that can be expressed as a function of the natural numbers, you best believe we’ll be looking at induction. The proof only has three steps:

1. Prove your shit is true for 0
2. Prove that if your shit is true for some number $x$, then it’s also true for $x+1$
3. Drop the mic

It’s helpful to picture these proofs with falling dominoes. When dominoes are lined up, you know that if one is knocked over, the next one is going to be knocked over as well – assuming your silly ass lined them up right. So since we know that, all we have to do is knock the first one over for every one of them to fall. The thing is, you need both elements to be in place for them all to fall. You need to knock the first one over and you need to ensure that one falling over means the next one falls over as well. If both of those things are true, then the whole row will fall and you have to spend half an hour setting it all up again GODDAMMIT IT KAREN.

Let’s look at an example.

Statement

Let $n$ be a natural number. Then

$0+1+2+…+n=\dfrac{n(n+1)}{2}$

Proof

Alright so the fact that $n$ is a natural number should send you straight into induction mode. So then we know what to do. First prove the above for $n=0$. Then prove that if the above is true for $x$, then it’s true for $x+1$. Then watch the dominoes fall, baby!

For let’s say $n=0$. If that’s true, then the equation is

$0=\dfrac{0(0+1)}{2}$

That shit’s true and I’m not going to bother proving it. Don’t @ me.

So step 1 is fucking done! Now for step 2, aka the inductive step. For the sake of argument let’s just assume that the formula is true for $x$.

And just so we know what the hell we’re looking for… we want to show that the equation is true when $x+1$ is plug in for $n$, which would look like this:

$0+1+2+…+x+(x+1)=\dfrac{(x+1)((x+1)+1)}{2}$

All good?

Ok we’re assuming the following

$0+1+2+…+x=\dfrac{x(x+1)}{2}$

We know that that equation is true and both sides are equal. That’s a good base to build on. Now we pull some old school algebra shit and just add $x+1$ to both sides. Still equal. Thanks, algebra.

$0+1+2+…+x+(x+1)=\dfrac{x(x+1)}{2}+(x+1)$

Let’s clean up that dirty ass right hand side by multiplying the $(x+1)$ by $\frac{2}{2}$ and making it one big fraction.

$0+1+2+…+x+(x+1)=\dfrac{x(x+1)}{2}+\dfrac{2(x+1)}{2}$

$0+1+2+…+x+(x+1)=\dfrac{x(x+1)+2(x+1)}{2}$

Both of those terms in the numerator are just multiples of , so we just just smash em up.

$0+1+2+…+x+(x+1)=\dfrac{(x+1)(x+2)}{2}$

And believe it or not we’re fucking there. One more step to make it super obvious.

$0+1+2+…+x+(x+1)=\dfrac{(x+1)((x+1)+1)}{2}$

There you have it. That’s the shit we’ve been looking for. All we did was start with the assumption that the equation is true for $x$, and we were able to show that if it’s true for $x$ then it must be true for $x+1$.

So we’ve shown that the statement is true when $n=0$, and we’ve shown that if it’s true for $n=x$ then it’s true for $n=x+1$. So it’s true for 0, therefore it’s true for 1, and 2, and 3, and so on.

Done.

There you have it. Proof by induction is hard to wrap your mind around at first but it’s pretty damn cool to be able to prove something for the infinite set of natural numbers in just two steps. Just remember, if you see the naturals, think induction. Just another trick of the trade.