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{align} \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{align} \] 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{align} \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{align} \] 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\)