Overview

Induction is a strategy (rather than a theorem) that gets a reccursion on a particular cases and automatically prove the statement.

Definition

As you might know, induction has two parts: base case and inductive case. Let $P(n)$ be a statement where $n$ is a positive integer.

• The base case, where you show that $P(1)$ is true. This part is often trivial, but don't forget to write it down. I recommend you to write it in the very first of the proof.
• Now for the inductive case, assume that $P(n)$ is true, and show that $P(n+1)$ is also true. This will complete the problem.

Thus, it can be written as

showing that $P(n)$ is true in general.

Example 1: the classic

We only outline the solution, and leave it as an exercise for the readers.

problem: Show that for any positive integer $n$, the following equality holds:

We proceed via induction. The base case is trivial as $n=1$.

Now for the inductive step, assume that for $n=k$ the equality holds. Now take the difference of $P(k)$ and $P(k+1)$ on both sides, as it looks like a lot of things cancel on the RHS. We have

and the rest is an easy calculation.

Advanced induction

As some might notice, induction is not only for $n\mapsto n+1$ yet! We will state a few example.

• One of the famous one is strong induction, where you assume that all of the $P(1)$, $P(2)$, $\dots$, $P(n)$ is true, instead of $P(n)$ alone. (Actually you can assume this anytime when you induct).
• Maybe for some integer $h$ the base case is $P(1)$, $P(2)$, $\dots$, $P(h)$ and the inductive step is $P(n)\mapsto P(n+h)$.
• Induction with prime factors.
• Sometimes we induct with an interval; Let $P(I)$ be a statement where $I$ is some interval. With the base case $I=[0, M)$ and inductive step $P([kM, (k+1)M))\implies P([(k+1)M, (k+2)M))$ then you can prove over nonnegative reals that $P(I)$ is true.
• It might get a reccursion with multiple variables. This is called dynamic programming in computer science.

Example 2: Induction on NT

TODO

Example 3: Induction on integer FE

Induction is especially common in integer FE as well, as it should be not too surprising.

When should I induct?

So when to use induction? Some advice is that

• If you can get a nice reccursion when lot of things cancel then you'll have fun with induction. It makes a lot easier to work with.
• It might be useful to use induction if a lot of things preserved while the inductive case, even if doesn't actually cancel out.

More advice on induction:

• Keep in mind that induction is just a strategy. It's a basic ``idea'' rather than a theorem, and it's really useful in many problems.
• Be careful of the base case! For example, it might be possible but you proved $P(1)$ is true and $P(n)$ is true where $n\ge 3$ by induction, but missing the case $n=2$. I recommend you to confirm until about first six cases if it's easy enough.
• Think about which varients are fixed and which do you induct with. This is sometimes not so clear.

Practice Problems