Writing a Proof by Induction

While writing a proof by induction, there are certain fundamental terms and mathematical jargon which must be used, as well as a certain format which has to be followed. These norms can never be ignored. Some of the basic contents of a proof by induction are as follows:

• a given proposition $P_n$ (what is to be proved);
• a given domain for the proposition $($for example, for all positive integers $n);$
• a base case $($where we usually try to prove the proposition $P_n$ holds true for $n=1);$
• an induction hypothesis $($which assumes that $P_k$ is true for any $k$ in the domain of $P_n$; this is then used for the case $P_{k+1});$
• the conclusion.

Based on these, we have a rough format for a proof by Induction:

Statement: Let $P_n$ be the proposition induction hypothesis for $n$ in the domain.

Base Case: Consider the base case:
$\hspace{0.5cm}$ LHS = LHS
$\hspace{0.5cm}$ RHS = RHS.
Since LHS = RHS, the base case is true.

Induction Step: Assume $P_k$ is true for some $k$ in the domain.

Consider $P_{k+1}$:
$\hspace{0.5cm}$ LHS $P_{k+1}$ = RHS $P_{k+1}$ (using induction hypothesis).
Hence the fact that $P_k$ is true implies that $P_{k+1}$ is true.

Conclusion: By mathematical induction, since both the base case and $P_{k}$ being true implies $P_{k+1}$ is true, $P_{n}$ is true for all $n$ in the domain.

Let us elucidate this through some examples.

Show that for all positive integers $n$,

$$\sum_{i=1} ^n i^2 = \frac {n(n+1)(2n+1)} {6}.$$

---

This is a well-known statement about the sum of the first $n$ squares, and we will show this via induction.

Statement: Let $P_{n}$ be the proposition that $\displaystyle \sum_{i=1} ^n i^2 = \frac {n(n+1)(2n+1)} {6}$ for all positive integers.
(We have stated what the induction hypothesis is, and specified the domain in which the statement is true.)

Base Case: Consider $n=1$.
$\hspace{0.5cm}$ LHS = $\displaystyle \sum_{i=1} ^ 1 1^2 = 1$.
$\hspace{0.5cm}$ RHS = $\frac{ 1 \times (1+1) \times (2 + 1) } {6} = 1$.
Since LHS=RHS, the base case is true. (We have identified the base case, and shown that it is true.)

Induction Hypothesis: Assume $P_k$ is true for some positive integer $k$.

Consider $P_{k+1}$: We have
$$\begin{aligned} \mbox{LHS of } P_{k+1} & = \sum_{i=1}^{k+1} i^2 \\ & = \left( \displaystyle \sum_{i=1}^k i^2 \right) + (k+1) ^2 \\ & = \frac{ k(k+1)(2k+1) } { 6} + (k+1) ^2 \\ & = (k+1) \left( \frac{ 2k^2 + k } { 6} + \frac{ 6 (k+1) } { 6} \right) \\ & = (k+1) \frac{ 2k^2 + 7k + 6 } { 6} \\ & = \frac { (k+1) (k+2) ( 2k + 3) }{6} \\ & = \mbox{RHS of } P_{k+1}. \end{aligned}$$ Hence, the fact that $P_{k}$ is true implies that $P_{k+1}$ is true. $($We successfully used the induction hypothesis $($in the 3$^\text{rd}$ equation$)$ along with algebraic manipulation to show that the next statement is true.$)$

Conclusion: By mathematical induction, since the fact that $P_1$ is true and so is $P_{k}$ implies $P_{k+1}$ is true, $P_{n}$ is true for all positive integers $n$. $_\square$

Show that $n^3 - n$ is divisible by $3\ \forall n\in \mathbb{N}$.

---

We have to prove that $n^3-n=3\alpha$ in the given domain, where $\alpha\in \mathbb{Z}$.

Statement: Let $P_{n}$ be the proposition that $n^3-n = 3\alpha\ \forall n\in \mathbb{N}$.
(We have stated what the induction hypothesis is, and specified the domain in which the statement is true.)

Base Case: Consider $n=1$.
$\hspace{0.5cm}$ LHS = $1^3-1 = 0$.
$\hspace{0.5cm}$ RHS = $3\alpha = 0$ for $\alpha=0$.
Since LHS=RHS, the base case is true. (We have identified the base case, and shown that it is true.)

Induction Hypothesis: Assume $P_k$ is true for some $k\in \mathbb{N}$.

Consider $P_{k+1}$: We have $$\begin{aligned} \mbox{LHS of } P_{k+1} & = (k+1)^3 - (k+1) \\ & = k^3 +1 + 3k^2 +3k - k -1 \\ & = (k^3 - k) + 3k^2 + 3k\\ & = 3a + 3(k^2 +k) \qquad (\text{by the induction hypothesis } \forall a\in \mathbb{Z})\\ & = 3(a+k^2+k) \\ & = 3\alpha \\ & = \mbox{RHS of } P_{k+1}. \end{aligned}$$ Hence the fact that $P_{k}$ is true implies that $P_{k+1}$ is true. $($We successfully used the induction hypothesis $($in the 3$^\text{rd}$ equation$)$ along with algebraic manipulation to show that the next statement is true.$)$

Conclusion: By mathematical induction, since the fact that $P_1$ is true and so is $P_{k}$ implies $P_{k+1}$ is true, $P_{n}$ is true for all positive integers $n$. $_\square$