# Mathematical Induction
A great intuition to keep in mind when dealing with [mathematical induction](https://en.wikipedia.org/wiki/Mathematical_induction):
> In induction, you do not show "the staement is true for $๐=๐+1
quot;, you literally show "if the statement is true for $n=k$, then the statement is true for $n=k+1quot;[^1].
So, we are proving a **property**.
### Climbing a ladder
There are two steps to climbing a ladder[^2]:
1. Somehow, we need to get on the ladder.
2. Once on a rung of the ladder, we need to be able to get to the next rung.
Consider an example. Let us try and prove the following:
$1 + 2 + \dots + n = \frac{n(n+1)}{2} , \;\;\;\; \forall n \geq 1$
We can quickly prove it for several cases by simply let $n=1$, $n=2$, $n=3$, and so on. With that said, we can actually treat this situation rather arbitrarily. Note that we are trying to prove a property, and that property is the equality.
Instead let us consider a **property**, $P$, where $P$ depends on (is a function of) $n$, where $n$ is the positive integers. Our goal is now to prove:
$P(n), \;\;\;\; \forall n \geq 1$
So, referring back to our ladder, we can note that proving $P(n)$ takes the same format:
* To start we need to get on the first rung of the ladder. This consists of proving that $P(1)$ is true.
* Then we want to prove that if we are on any given rung, we can always get to the next one. Note that this is a *property*!
### Official Steps
Formally, we can state our steps as follows:
* Step 1: Prove that $P(1)$ is true. (**Basis Step**)
* Step 2: Assume $P(k)$ is true, then prove $P(k+1)$ is true. (**Induction Step**)
We can put that into practice as follows. We can start with our basis step.
**Basis Step**
We simply need to prove that our equality holds for $n=1$:
$P(1): \;\;\;\;\; 1 = \frac{n(n+1)}{2} = \frac{2}{2} = 1$
Great, we have proved our basis step. This is generally the easy part.
**Induction Step**
We now need to show how we get from one rung of the ladder to the next. How will we do this? We will actually *assume* that our property is true for $n=k$; in other words, we assume that $P(k)$ is true. Then, armed with this assumption, we will try and *deduce* that our property *must be true* for $n=k+1$. In other words, we want to prove the property:
> *If* $P(k)$ is true, *then* $P(k+1)$ *must be true*.
So, here is our assumption:
$P(k): \;\;\;\;\; 1 + 2 + \dots + k= \frac{k(k+1)}{2}$
Again, we are simply assuming that the first $k$ things obey this equality. We now want to prove that $P(k+1)$ is true, *in light of* this assumption! This is incredibly crucial to understand. We are in a sense providing ourselves with extra information via this assumption. On it's own, we do not know if $P(k)$ is officially true. But, we are *assuming* that it is and then working to see if, given that assumption, $P(k+1)$ must be true as well. If so, we will have proved a general property-namely the property that if you are on one rung of the ladder you can always get to the next rung! Note that this inductive assumption is often called the **induction hypothesis**.
Let us actually work to prove this:
$P(k+1): \;\;\;\;\; 1 + 2 + \dots + k+ (k+1)= \frac{(k+1)((k+1)+1)}{2}$
We can now *use our inductive assumption*, since the first $k$ terms on the left are equal to $P(k)$:
$P(k+1): \;\;\;\;\; \overbrace{1 + 2 + \dots + k}^{P(k)} + (k+1)= \frac{(k+1)((k+1)+1)}{2}$
$\frac{k(k+1)}{2} + (k+1)= \frac{(k+1)((k+1)+1)}{2}$
Now, using a bit of algebra:
$\frac{k^2 + k + 2k+ 2}{2} = \frac{k^2 + k + 2k+ 2}{2}$
Hence, we have just proved $P(k+1)$ to be true, *under the assumption* that $P(k)$ is true.
### High level
Let us now take a step back for a moment and reflect on what we have just done:
* We started by proving the *basis step*, namely that $P(1)$ is true. This allowed us to actually get onto the ladder.
* We then proved the property that *if* $P(k)$ is true, *then* $P(k+1)$ must also be true. To do this we *assumed* that $P(k)$ was true and utilized this in proving that $P(k+1)$ must then also be true.
* We then use these two properties to claim that our equality is true for all values of $n$.
### When we can't get on the ladder (prove the basis case)
A good example that helps internalize why the basis case is so important is below[^3]. It shows how there are certainly cases where we can prove the induction step, but there is no basis case where it is true.
So, suppose that we wish to prove: $n=n+1$ for all (positive) integers $n$. We will purposefully omit the base case.
Our induction hypothesis is:
$P(k): \;\;\;\; k = k+1$
Now, assuming that this is true, we now wish to show that it will also be true for $k+1$:
$P(k+1): \;\;\;\; (k+1) = (k+1)+1$
$k+1 = (k+1)+1$
Note that on the right hand side we have $(k+1)$; we can make use of our assumption (induction hypothesis) here. That stated that $k = k+1$. So, we can plug $k$ in for $k+1$:
$k+1 = (k)+1 = k+ 1$
And we have proven our induction step. The problem is that there is no base case for which it is true! This means that we have *no way of getting onto the ladder*.
### Recursion and Induction
A good example of using a recursive relation to prove a more general property is [here](https://math.stackexchange.com/questions/536404/proof-by-induction-for-a-recursive-sequence-and-a-formula).
[^1]: [Third comment on this question](https://math.stackexchange.com/questions/2738115/the-assumption-in-proof-by-induction)
[^2]: [Intro via Trefor Bazett](https://www.youtube.com/watch?v=GdM_iA1Zek4)
[^3]: [No basis case is true](https://math.stackexchange.com/questions/627969/induction-without-a-base-case/627993)