Induction is a new proof outline, closely related to recursive definition in programming languages. It's used to prove that a property holds for all integers starting at some lowest value.
Suppose that our claim looks like:
Claim: For all integers n >= b, P(n).
In our proof by induction, we show two things:
It also works to prove this:
The choice is mostly a matter of personal preference. Our course materials are a mix of the two styles.
Our proof outline
Proof: By induction on n.
Base case: [prove that P(b) is true]
Inductive hypothesis (IH): Suppose that P(n) is true for n=b, ..., k.
Rest of the inductive step:
... [work using the fact the IH is true] ...
So P(k+1).
Or
Proof: By induction on n.
Base case: [prove that P(b) is true]
Inductive hypothesis (IH): Suppose that P(n) is true for n=b, ..., k-1.
Rest of the inductive step:
... [work using the fact the IH is true] ...
So P(k).
Claim: for all integers \(n \ge 2\), \(\sum_{i=2}^n i 2^i = (n-1)2^{n+1}\).
This claim gives a "closed form" for this summation, i.e. a formula that doesn't rely on a summation.
Key parts of this claim
Notice that P(n) needs to be a statement that's true or false. Said another way, it needs to contain a verb.
Main outline of the proof:
Proof: By induction on n.Base case: At n = 2, \(\sum_{i=2}^n i 2^i = \sum_{i=2}^2 i 2^i = 2 \cdot 2^2 = 8\).
Also \((n-1)2^{n+1} = (2-1)2^{2+1} = 2^3 = 8 \).
So \(\sum_{i=2}^n i 2^i = (n-1)2^{n+1}\).
Inductive hypothesis (IH): Suppose that \(\sum_{i=2}^n i 2^i = (n-1)2^{n+1}\) is true for n= 2 , ..., k.
Rest of the inductive step:
... [work using the fact the IH is true] ...
So \(\sum_{i=2}^{k+1} i 2^i = k 2^{k+2}\) which is what we needed to prove.
Full proof:
Proof: By induction on n.Base case: At n = 2, \(\sum_{i=2}^n i 2^i = \sum_{i=2}^2 i 2^i = 2 \cdot 2^2 = 8\).
Also \((n-1)2^{n+1} = (2-1)2^{2+1} = 2^3 = 8 \).
So \(\sum_{i=2}^n i 2^i = (n-1)2^{n+1}\).
Inductive hypothesis (IH): Suppose that \(\sum_{i=2}^n i 2^i = (n-1)2^{n+1}\) is true for n= 2 , ..., k.
Rest of the inductive step:
By the inductive hypothesis, \(\sum_{i=2}^k i 2^i = (k-1)2^{k+1}\).
So \(\sum_{i=2}^{k+1} i 2^i = (k+1) 2^{k+1} + \sum_{i=2}^k i 2^i = (k+1) 2^{k+1} + (k-1)2^{k+1} = (2k)\cdot 2^{k+1} = k 2^{k+2}\).
So \(\sum_{i=2}^{k+1} i 2^i = k 2^{k+2}\) which is what we needed to prove.
Many inductive proofs do not require solid intuitions about how the closed form was found. It's fine if I got it from some random LLM, because the induction proof will confirm whether it's correct.
Suppose that we've proved the following lemma:
Lemma: for any integers $a$, $b$, $c$, and $d$ and any positive integer $p$, if $a \equiv b \pmod{p}$ and $c \equiv d \pmod{p}$, then $ac \equiv bd \pmod{p}$.
Let's use induction to prove the following claim:
Claim: for any integers $a$ and $b$ and any positive integers $n$ and $p$, if $a \equiv b \pmod{p}$, then $a^n \equiv b^n \pmod{p}$.
The proof might look like this:
Proof: Let $a$ and $b$ be integers, and let $n$ and $p$ be positive integers. Suppose that $a \equiv b \pmod{p}$. We'll prove that $a^n \equiv b^n \pmod{p}$ by induction on $n$.
Base case: $n=1$. Then $a^n \equiv b^n \pmod{p}$ is equivalent to $a \equiv b \pmod{p}$, which we assumed to be true.
Inductive hypothesis: Suppose that $a^n \equiv b^n \pmod{p}$ for $n=1, \ldots, k-1$.
By the inductive hypothesis, we know that $a^{k-1} \equiv b^{k-1} \pmod{p}$. We assumed that $a \equiv b \pmod{p}$. By the lemma, we can combine these two equations to get $a\cdot a^{k-1} \equiv b\cdot b^{k-1} \pmod{p}$. Simplifying gives us $a^k \equiv b^k \pmod{p}$, which is what we needed to show.
Suppose we have a chocolate bar that's divided into little squares that you can snap apart. Each snap breaks the bar along a line, which may divide several sets of squares. For example, if we have a $4 \times 3$ bar, we can reduce it to individual squares as follows:
This requires 11 breaks total.
Some experiments suggest the following claim:
Claim: To divide a $m \times n$ bar into individual squares requires $mn -1$ breaks.
A good choice for a single induction variable is the number of squares in the bar: $a=mn$. Since $a$ isn't defined in the claim, the start of the proof needs to explain how $a$ is related to the items in the claim.
Proof: by induction on $a$, which is the number of squares in the chocolate bar.Base case: $a=1$. In this case, the chocolate bar is already divided into individual squares. So no breaks are required. This squares with the fact that $mn-1 = 0$.
Induction hypothesis: Suppose that any chocolate bar with $a$ squares requires $a-1$ breaks to divide it into individual squares, for $a = 1, \ldots, k-1$.
Rest of inductive step: Suppose that we have a chocolate bar with $k$ squares, where $k > 1$. Breaking it once divides it into two pieces. Let's the first piece contains $p$ squares. Then the second piece has $k-p$ squares.
$p$ has to be between $1$ and $k-1$. So, by the inductive hypothesis, the first piece can be divided into individual squares using $p-1$ breaks.
Similarly $k-p$ has to be between $1$ and $k-1$. So, by the inductive hypothesis, the second piece can be divided into individual squares using $(k-p)-1$ breaks.
Adding these up, we've divided the original chocolate bar into individual squares using $1 + (p-1) + ((k-p)-1)$ breaks. Simplifying this expression gives us $p + (k-p)-1 = k-1$ breaks.
So a chocolate bar with $k$ squares can be divided into individual squares using $k-1$ breaks, which is what we needed to show.