# 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 cannot ever be ignored. . Some of the basic contents of a Proof by Induction are as follows:\[\]

\(\text{A given }\textbf{proposition}\) \(P_n\) \(\color{SeaGreen}{\text{(what is to be proved)}}\)

\(\text{A given }\textbf{domain}\text{ for the proposition}\) (for example: \(\forall\) \(\color{SeaGreen}{\text{positive integers }}\)\(n\))

\(\text{A }\textbf{Base Case}\) \(\color{SeaGreen}{\text{(where we usually try to prove the proposition }}\)\(P_n\) \(\color{SeaGreen}{\text{holds true for n=1)}}\)

\(\text{An }\textbf{Induction Hypothesis}\) \(\color{SeaGreen}{\text{(which assumes that }}\)\( P_k\)\(\color{SeaGreen}{\text{ is true for any }}\) \(k\) \(\color{SeaGreen}{\text{in the domain of }}\)\(P_n\)\(\color{SeaGreen}{\text{ - this is then used for the case}}\)\(P_{k+1}\)\(\color{SeaGreen}{\text{)}}\)

\(\text{The }\textbf{Conclusion}\)\[\]

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

Statement: Let \(P_n\) be the \(\text{proposition}\) Induction Hypothesis, for \(n\) in \(\text{Domain}\).\[\] Let us elucidate this through some examples.\[\]\(\text{Base Case}\): Consider Base Case.\[\] LHS = LHS\[\] RHS = RHS\[\] Since LHS = RHS, thus Base Case is true.\[\]Induction step: Assume \(P_k\) is true for some \(k\) in Domain.

Consider \(P_{k+1}\):

\[\]LHS \(P_{k+1}\) =RHS \(P_{k+1}\) [ using \(\text{Induction Hypothesis}\) ] \[\]

Hence \(P_k\) is true implies that \(P_{k+1}\) is true. \(\text{Conclusion}\): By Mathematical Induction, since \(\text{Base Case}\) is true and is true implies is true, thus is true for all in \(\text{Domain}\).

## Example Question 1

Show that for all positive integers \(n\),

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

Solution: 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.\[\] \[\color{SeaGreen}{\text{We have stated what the Induction Hypothesis is,} \\ \text{ and specified the domain in which the statement is true}}.\] \[\] Base Case: Consider \(n=1\). LHS= \( \displaystyle \sum_{i=1} ^ 1 1^2 = 1 \). RHS= \( \frac{ 1 \times (1+1) \times (2 + 1) } {6} = 1 \). Since LHS=RHS, thus the Base Case is true. \[\] \[\color{SeaGreen}{\text{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} \).\[\] \(\begin{align} \mbox{LHS } 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 } P_{k+1} \\ \end{align} \) Hence \(P_{k}\) is true implies that \(P_{k+1}\) is true. \[\] \[\color{SeaGreen}{\text{We successfully used the induction hypothesis (in the 3rd equation) along} \\ \text{ with algebraic manipulation to show that the next statement is true}}.\] \[\] Conclusion: By Mathematical Induction, since \(P_1\) is true and \(P_{k}\) is true implies \(P_{k+1}\) is true, thus \(P_{n}\) is true for all positive integer \(n\). \( \square\)\[\]

## Example Question 2

Show that \(\forall n\in N, n^3 - n \) is divisible by 3.

Solution: 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}\)\[\]

\[\color{SeaGreen}{\text{We have stated what the Induction Hypothesis is,} \\ \text{ and specified the domain in which the statement is true}}.\] \[\] Base Case: Consider \(n=1\).\[\] LHS= \( 1^3-1 = 0 \).\[\] RHS= \( \text{for }\alpha=0, 3\alpha = 0 \).\[\] Since LHS=RHS, thus the Base Case is true. \[\] \[\color{SeaGreen}{\text{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} \).\[\] \(\begin{align} \mbox{LHS } 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) \color{SeaGreen}{\text{ by the Induction Hypothesis }}\forall a\in \mathbb{Z}.\\ & = 3(a+k^2+k) \\ & = 3\alpha \\ & = \mbox{RHS } P_{k+1} \\ \end{align} \) \[\] Hence \(P_{k}\) is true implies that \(P_{k+1}\) is true. \[\] \[\color{SeaGreen}{\text{We successfully used the induction hypothesis (in the 3rd equation) along} \\ \text{ with algebraic manipulation to show that the next statement is true}}.\] \[\] Conclusion: By Mathematical Induction, since \(P_1\) is true and \(P_{k}\) is true implies \(P_{k+1}\) is true, thus \(P_{n}\) is true for all positive integer \(n\). \( \square\)\[\]

**Cite as:**Writing a Proof by Induction.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/writing-a-proof-by-induction/