$Project Greater Ed Logo$

Weak Induction

Principle of Math Induction

In lessons past, we said that, in order to prove universal statements like:

“For all $n\in\mathbb{N},\ 1+2+3+4+…+n=\frac{n\cdot(n+1)}{2}$”

(where $1+2+3+…+n$ is a way of representing the sum of all numbers up to some given $n$), we CANNOT show that the equation $1+2+3+4+…+n=\frac{n\cdot(n+1)}{2}$ is true for $n=1,2,3,4,5$ and therefore conclude that, no matter what $n$ I pick, the equation is true; that would only prove that the equation is true for the first few natural numbers, not all of them.

However, since I know (or can easily verify) that the equation $1+2+3+4+…+n=\frac{n\cdot(n+1)}{2}$ is true for $n=1,2,3,4$ and $5$, if I wanted to prove the equation for $n=6$ as well, I could notice (since we know that $1+2+3+4+5=\frac{5(5+1)}{2}$;see second line below.)

$$\begin{align} 1+2+3+4+5+6&=(1+2+3+4+5)+6& \\&=\frac{5\cdot(5+1)}{2}+6& \\&=15+6 & \\&=21& & \end{align}$$

Then, letting $n=6$ in the expression $\frac{n\cdot(n+1)}{2}$, you get $\frac{6\cdot(7)}{2}=21$, which thus, by the above equation, proves that $1+2+3+4+…+n=\frac{n\cdot(n+1)}{2}$ for $n=6$.

Note that the key step in the above was the fact that we used the fact that $1+2+3+4+…+n=\frac{n\cdot(n+1)}{2}$ for $n=5$ in order to prove that the equation was true for $n=6$.

Now, since we have proved that the equation is true for $n=6$, we could prove the equation for $n=7$ in the same exact way, leveraging the fact that $1+2+3+4+…+n=\frac{n\cdot(n+1)}{2}$ is true for $n=6$ (because we just proved it). Then, we can use the truth of the statement for $n=7$ to prove it for $n=8$, and use the $n=8$ equation to prove the $n=9$ equation, and so on. So, if I could prove that this relationship is true for all $n$ (i.e. that I can use the truth of the $n$th equation to prove the $(n+1)$th equation (i.e. use the previous equation to prove the next equation)), then this would validate that the statement is true for no matter what $n$ one chooses.

This is the key idea behind the principle of (weak) mathematical induction.

Principle of (Weak) Mathematical Induction

Let $P(n)$ be a predicate and let $\mathbb{N}$ be the domain of $n$. If

1. $P(1)$ is true, and

2. $P(k)\rightarrow P(k+1)$ for every $k\geq 1$,

then the statement “For all natural numbers $n$, $P(n)$ holds” is true.

In other words, if we want to show some statement of the form “$\forall n\in \mathbb{N}, P(n)$” is true then all we need to do is show that it is true for $n=1$, and show that $P(k)$ implies that $P(k+1)$ holds for each $k\geq 1$. Then because $P$ is true at the starting $n$-value, $n=1$, and because the previous statement $P(k)$ implies (or, in a sense, helps prove) the next one, $P(k+1)$ no matter what $k$ is, we can then conclude that the statement $P$ is true for any natural number. This is often visualized by dominoes.

If I knock down the first domino, and I know that, no matter what pair of dominoes I choose, the previous domino (is close enough to) knock down the next domino, then (because the first domino was knocked down) it follows that all dominoes must get knocked down.

Proving Statements by Induction

How To Prove a Statement by Induction

Suppose you want to prove a statement of the form “For all $n\in \mathbb{N}$ where $n\geq 1$, $P(n)$ holds.” Do the following:

1. (Base Case): Prove that $P(1)$ is true.

2. (Inductive Case): Prove that for all $k\geq 1$, $P(k)\rightarrow P(k+1)$. That is, assume that $P(k)$ is true, and use it to show that $P(k+1)$ is also true.

Then, conclude, by the principle of mathematical induction, that $P(n)$ holds for all $n\geq 1$ (as was to be proved).

Proof (Induction):

Base case: Let $n=1$. Then note $\sum_{i=1}^n i=\sum_{i=1}^1 i = 1$. Also, notice $\frac{n\cdot(n+1)}{2}=\frac{1\cdot(2)}{2}=1$. So, when $n=1$ the equation $\sum^n_{i=1} i=\frac{n\cdot (n+1)}{2}$ is true, satisfying the base case.

Inductive Case: Let $k\in \mathbb{N}$ and suppose that $\sum^k_{i=1} i=\frac{k\cdot (k+1)}{2}$ is true (this is called the inductive hypothesis). We want to show that $\sum^{k+1}_{i=1} i=\frac{(k+1)\cdot ((k+1)+1)}{2}$ (which equals $\frac{(k+1)\cdot (k+2)}{2}$ ) (Note: I just replaced the $n$’s with $(k+1)$ because we want to show that the “previous equation” $\sum^k_{i=1} i=\frac{n\cdot (k+1)}{2}$ implies the next one). Now, notice that

$$\begin{align} \sum^{k+1}_{i=1} i &=1+2+3+…+(k-1)+k+(k+1)& & \text{unpacking the summation}\\&=(1+2+3+…+(k-1)+k)+(k+1)& & \text{putting parentheses around the first} k \text{terms}\\&=\left(\sum^k_{i=1} i\right)+(k+1)& &\text{replaced} (1+2+3+…+(k-1)+k) \text{with its sigma form}\\&=\frac{k\cdot (k+1)}{2}+(k+1)& & \text{using the inductive hypothesis}\\&=\frac{k\cdot (k+1)}{2}+\frac{2(k+1)}{2}& & \text{found a common denominator}\\&=\frac{k(k+1)+2(k+1)}{2}& & \\&=\frac{(k+1)(k+2)}{2}& &\text{factored out a} (k+1) \text{in the top of the fraction}\end{align}$$

Thus, the above shows that $\sum^{k+1}_{i=1} i=\frac{(k+1)(k+2)}{2}=\frac{(k+1)\cdot ((k+1)+1)}{2}$ for all $k\geq 1$. Therefore, by both the base case and the inductive case we can conclude that the statement “For all $n\in \mathbb{N}$, $\sum^n_{i=1} i=\frac{n\cdot (n+1)}{2}$” is true by principle of mathematical induction. QED

A Few Notes on Induction

Induction can be used for statements that don’t start at $n=1$, like “$\forall n\in \mathbb{N}$ where $n\geq 31$, P(n).” All that changes in our approach when using induction is the base case, which changes from proving $P(1)$ to $P(31)$ instead. Everything else remains the same.

Technically, we can generalize the notion of induction to include a negative number starting point as well. That is, we could prove statements like “$\forall n\in \mathbb{N}$ where $n\geq -100$, P(n).”

Induction is very commonly used to prove statements involving sums or products (i.e. statements with $\sum$ and $\Pi$).

Proof:

Base case: Let $n=0$. Note that $\sum_{i=0}^n 2^i=\sum_{i=0}^0 2^i =2^0=1$. Note also that $2^{1+0}-1=1$. So, when $n=0$, we have $\sum_{i=0}^n 2^i=2^{n+1}-1$, satisfying the base case.

Inductive Case: Suppose $\sum_{i=0}^k 2^i=2^{k+1}-1$. (We want to show that $\sum_{i=0}^{k+1} 2^i=(2^{(k+1)+1}-1)=(2^{k+2}-1)$). Note that

$$\begin{align}\sum_{i=0}^{k+1} 2^i &=1+2+4+…+2^k+2^{(k+1)}\\&=(1+2+4+…+2^k)+2^{(k+1)}\\&=\left(\sum_{i=0}^k 2^i \right) +2^{(k+1)}\\&=(2^{k+1}-1)+2^{(k+1)}\\&=2\cdot 2^{(k+1)}-1\\&=2^{(k+1)+1}-1\end{align}$$

Therefore, the above shows that for any natural number $k$, $\sum_{i=0}^{k+1} 2^i=(2^{(k+1)+1}-1)$, verifying the inductive case.

By the base case and inductive case, it follows by induction that “For all $n\geq 0$, $\sum_{i=0}^n 2^i={(2^{n+1}-1)}$.”

Proof:

Base Case: Let $n=1$. Then note that $\sum_{i=1}^1 i^3=\sum_{i=1}^1 i^3=1^3=1$. Note also that $\left[\frac{n\cdot(n+1)}{2}\right]^2=\left[\frac{1\cdot (1+1)}{2}\right]^2=1^2=1.$ Therefore we have that $\sum_{i=1}^n i^3=\left[\frac{n\cdot(n+1)}{2}\right]^2$ in the case where $n=1$ (i.e. the base case).

Inductive Case: Let $k\in \mathbb{N}$ and suppose that $\sum_{i=1}^k i^3=\left[\frac{k\cdot(k+1)}{2}\right]^2$. We want to show $\sum_{i=1}^{k+1} i^3=\left[\frac{(k+1)\cdot(k+2)}{2}\right]^2$. Now, notice that

$$\begin{align} \sum_{i=1}^{k+1} i^3&=1+2+3+…+(k-1)^3+(k)^3+(k+1)^3& & \\&=(1+2+3+…+(k-1)^3+(k)^3)+(k+1)^3& &\text{grouped the first } k \text{ terms}\\&=\left[\frac{k\cdot(k+1)}{2}\right]^2+(k+1)^3& & \text{because we assumed } \sum_{i=1}^k i^3=\left[\frac{k\cdot(k+1)}{2}\right]^2\\&=\frac{k^2(k+1)^2}{4}+\frac{4(k+1)^3}{4}& &\text{found common denominator, and distributed the power}\\&=\frac{(k+1)^2\cdot [k^2+4(k+1)]}{4}& &\text{factored out a } (k+2)^2\\&=\frac{(k+1)^2\cdot [k^2+4k+4]}{4}& &\\&=\frac{(k+1)^2(k+2)^2}{4}& & \text{factored the } [k^2+4k+4] \\&=\left[\frac{(k+1)(k+2)}{2}\right]^2& & \text{putting power on outside}\end{align}$$

Thus the inductive case holds. Therefore, by the base case and inductive case, we can conclude by induction that “For all natural numbers $n\geq 1$, $\sum_{i=1}^n i^3=\left[\frac{n\cdot(n+1)}{2}\right]^2$.” QED.

Proof:

Base Case: Let $n=1$. Then note $\sum_{i=1}^1 \frac{1}{i(i+1)}=\frac{1}{1\cdot(1+1)}=\frac{1}{2}$. Note also that $\frac{n}{n+1}=\frac{1}{1+1}=\frac{1}{2}$. Therefore, $\sum_{i=1}^n \frac{1}{i\cdot(i+1)}=\frac{n}{n+1}$ when $n=1$, proving the base case.

Inductive Case: Let $k$ be a natural number greater than $1$, and assume $\sum_{i=1}^k \frac{1}{i\cdot(i+1)}=\frac{k}{k+1}$. We want to show that $\sum_{i=1}^{k+1} \frac{1}{i\cdot(i+1)}=\frac{k+1}{k+2}$. To this end, note that

$$\begin{align}\sum_{i=1}^{k+1} \frac{1}{i\cdot(i+1)}&=\frac{1}{1\cdot (2)}+\frac{1}{2\cdot (3)}+\frac{1}{3\cdot (4)}+…+\frac{1}{k\cdot (k+1)}+\frac{1}{(k+1)\cdot (k+2)}& & \\&=\left(\frac{1}{1\cdot (2)}+\frac{1}{2\cdot (3)}+\frac{1}{3\cdot (4)}+…+\frac{1}{k\cdot (k+1)}\right)+\frac{1}{(k+1)\cdot (k+2)}& & \\&=\frac{k}{k+1}+\frac{1}{(k+1)\cdot (k+2)}& & \text{by assumption that} \sum_{i=1}^k \frac{1}{i\cdot(i+1)}=\frac{k}{k+1}\\&=\frac{k\cdot(k+2)}{(k+1)(k+2)}+\frac{1}{(k+1)\cdot (k+2)}& & \\&=\frac{k^2+2k+1}{(k+1)(k+2)}& & \text{distributed the } k \text{ and added across the top of the fractions}\\&=\frac{(k+1)^2}{(k+1)(k+2)}& & \text{factored the numerator}\\&=\frac{k+1}{k+2}& & \end{align}$$

Thus, we have shown above that for any natural number $k$, $\sum_{i=1}^{k+1} \frac{1}{i\cdot(i+1)}=\frac{k+1}{k+2}$, proving the inductive case.

Therefore, we can conclude from the base case and inductive case above that the statement “For all $n\geq 1$, $\sum_{i=1}^n \frac{1}{i\cdot(i+1)}=\frac{n}{n+1}$” holds.

Proof:

Base Case: Let $n=1$. Then note that $4^1-1=3$ which is clearly divisible by $3$. Thus the base case holds.

Inductive Case: Let $k$ be a natural number greater than or equal to $1$. Then suppose that $3\vert 4^k-1$. We want to show that $3\vert 4^{k+1}-1$. Now, since $3\vert 4^k-1$, there is an integer $m$ such that $4^k-1=3m$. Multiplying both sides of this equation by $4$ gives us (after a little distribution) $4^{k+1}-4=4\cdot 3m$. Algebra gives us the following sequence of implications:

$$\begin{align} 4^{k+1}-4&=4\cdot 3m& &\text{just rewriting the last statement}\\ \Rightarrow\ \ \ 4^{k+1}-1-3&=4\cdot 3m& & \text{broke apart the } -4\\ \Rightarrow\ \ \ 4^{k+1}-1&=4\cdot 3m+3& &\text{added } 3 \text{ to both sides}\\ \Rightarrow\ \ \ 4^{k+1}-1&=3(4m+1)& &\text{factored out } 3\end{align}$$

Since $4m+1$ is an integer, the above equation implies that $3\vert 4^{k+1}-1$, validating the inductive case.

Therefore by the base case and inductive case, we have proved “For all natural numbers $n\geq 1$, $3\vert (4^n-1)$” by induction.

Proof:

Base case: Let $n=3$. Notice that $2n=6$ and $2^3=8$. Obviously, $2n<2^n$ holds in the case where $n=3$, thereby satisfying the base case.

Inductive Case: Let $k$ be a natural number greater than or equal to $3$, and suppose $2k<2^k$. We want to show that $2(k+1)<2^{(k+1)}$. Now notice that

$$\begin{align}2(k+1)&=2k+2& &\\&<2^k+2& &\text{by our assumption that }2k<2^k\\&<2^k+2^k& & \text{since, for any }k\geq 3,\ 2<2^k\end{align}$$

Since $2^k+2^k=2\cdot 2^k=2^{k+1}$, we have by the above inequality that $2(k+1)<2^{k+1}$, which is exactly what we are after here.

Therefore, by the base case and inductive case above, the statement “For all natural numbers $n\geq 3$, $2n<2^n$” holds by induction. QED.

Recall that $n!=n\cdot(n-1)\cdot (n-2)\cdot … \cdot 3\cdot 2\cdot 1$, i.e. $n!$ is the product of all numbers up to and including $n$. So $(n+1)!=(n+1)\cdot (n)\cdot (n-1)\cdot… \cdot 3\cdot 2\cdot 1$.

Proof:

Base case: Let $n=3$. Note that $2^n=2^3=8$. Note also that $(n+1)!=4!=24$ which is clearly larger than $8$. Therefore, $2^n\leq (n+1)!$ is true when $n=3$, satisfying the base case.

Inductive Case: Let $k$ be a natural number no less than $3$, and assume that $2^k\leq (k+1)!$. We want to show that $2^{k+1}\leq (k+2)!$. So note that

$$\begin{align} 2^{k+1}&=2\cdot 2^k& &\\&<2\cdot (k+1)!& &\text{by induction hypothesis}\\&\leq(k+2)(k+1)!& &\text{since } 2\leq(k+2) \text{ when } k \text{ is 3 or greater}\\&=(k+2)!& & \text{by how factorials work}\end{align}$$

Thus, we have shown that $2^{k+1}\leq (k+2)!$ follows from $2^k\leq (k+1)!$, for any natural number $k\geq 3$, implying that the inductive case holds.

Therefore, by the inductive case and the base case as demonstrated above, we have shown that “For all integers $n\geq 3$, $2^n\leq (n+1)!$.”

Previous Lesson

Back to Course

Next Lesson

Discrete Mathematics

Weak Induction

Principle of Math Induction

Principle of (Weak) Mathematical Induction

Proving Statements by Induction

How To Prove a Statement by Induction

A Few Notes on Induction