# Mathematical Induction Fundamentals

The Mathematical Induction Fundamentals are defined for applying 3 steps, such as step 1 for showing its initial ignite, step 2 for making an assumption, and step 3 for showing it is true based on the assumption. Make sure the Mathematical Induction Fundamentals should be used only when the question asks to use it.

## Basic Mathematical Induction Fundamentals

Prove $2+4+6+\cdots+2n = n(n+1)$ by mathematical induction.

Step 1: Show it is true for $n=1$.
LHS $= 2 \times 1 = 2$
RHS $= 1 \times ( 1+1) = 2$
LHS $=$ RHS
It is true for $n = 1$.
Step 2: Assume that it is true for $n=k$.
That is, $2+4+6+\cdots+2k = k(k+1)$.
Step 3: Show it is true for $n = k+1$.
That is, $2+4+6+\cdots+2k+2(k+1) = (k+1)(k+2)$.
\begin{aligned} \displaystyle \require{color} \text{LHS } &= 2+4+6+\cdots+2k+2(k+1) \\ &= k(k+1) + 2(k+1) &\color{green} \text{replaced by the assumption in Step 2}\\ &= (k+1)(k+2) &\color{green} \text{factorise by } (k+1) \\ &= \text{ RHS} \end{aligned}
Therefore it is true for $n=k+1$.
Therefore the statement is true for $n\ge 1$.

## Mathematical Induction with Indices

Prove $1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + n \times 2^n = (n-1) \times 2^{n+1} + 2$ by mathematical induction.

Step 1: Show it is true for $n=1$.
LHS $= 1 \times 2 = 2$
RHS $= (1-1) \times 2^{1-1} + 2 = 2$
LHS $=$ RHS
Therefore it is true for $n=1$.
Step 2: Assume that it is true for $n=k$.
That is, $1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + k \times 2^k = (k-1) \times 2^{k+1} + 2$.
Step 3: Show it is true for $n=k+1$.
That is $1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + k \times 2^k + (k+1) \times 2^{k+1} = k \times 2^{k+2} + 2$
\begin{aligned} \displaystyle \require{color} \text{LHS } &= 1 \times 2 + 2 \times 2^2 + 3 \times 2^3 + \cdots + k \times 2^k + (k+1) \times 2^{k+1} \\ &= (k-1) \times 2^{k+1} + 2 + (k+1) \times 2^{k+1} &\color{green} \text{replaced by the assumption in Step 2} \\ &= [(k-1)+(k+1)] \times 2^{k+1} + 2 &\color{green} \text{factorise by } 2^{k+1} \\ &= 2k \times 2^{k+1} + 2 \\ &= k \times 2^{k+2} + 2 \\ &= \text{RHS} \end{aligned}
Therefore it is true for $n=k+1$.
Therefore the statement is true for $n \ge 1$.

## Mathematical Induction with Factorials

Prove $2 \times 1! + 5 \times 2! + 10 \times 3! + \cdots + (n^2+1)n! = n(n+1)!$ by mathematical induction.

Note that $\require{color} \color{red} (n+1)n! = (n+1)!$
Step 1: Show it is true for $n=1$.
LHS $= (1^2+1) \times 1! = 2$
RHS $= 1 \times (1+1)! = 2$
LHS $=$ RHS
It is true for $n = 1$.
Step 2: Assume that it is true for $n=k$.
That is, $2 \times 1! + 5 \times 2! + 10 \times 3! + \cdots + (k^2+1)k! = k(k+1)!$.
Step 3: Show it is true for $n=k+1$.
That is, $2 \times 1! + 5 \times 2! + 10 \times 3! + \cdots + (k^2+1)k!+ (k^2+2k+2)(k+1)! = (k+1)(k+2)!$
\begin{aligned} \displaystyle \require{color} \text{LHS } &= 2 \times 1! + 5 \times 2! + 10 \times 3! + \cdots + (k^2+1)k!+ (k^2+2k+2)(k+1)! \\ &= k(k+1)!+ (k^2+2k+2)(k+1)! &\color{green} \text{replaced by the assumption in Step 2}\\ &= [k + (k^2+2k+2)](k+1)! &\color{green} \text{factorise by } (k+1)! \\ &= (k^2 + 3k + 2)(k+1)! \\ &= (k+1)(k+2)(k+1)! \\ &= (k+1)(k+2)! &\color{green} (k+2)(k+1)! = (k+2)! \\ &= \text{RHS} \end{aligned}
Therefore it is true for $n=k+1$.
Therefore the statement is true for $n \ge 1$.

## Mathematical Induction with Sigma $\displaystyle \sum$ Notations

Prove $\displaystyle \sum_{a=1}^{n} a^2 = \frac{1}{6}n(n+1)(2n+1)$ by mathematical induction.

Note that before proving the statement in sigma notation, it is highly recommended to expand to series format to avoid silly mistakes.
$\displaystyle \sum_{a=1}^{n} a^2 = 1^2 + 2^2 + 3^2 + \cdots + n^2$
So the question becomes now as follows.
Prove $\displaystyle 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{1}{6}n(n+1)(2n+1)$ by mathematical induction.
Step 1: Show it is true for $n=1$.
LHS $= 1^2 = 1$
RHS $= \frac{1}{6} \times 1 \times (1+1) \times (2+1) = 1$
LHS $=$ RHS
It is true for $n = 1$.
Step 2: Assume that it is true for $n=k$.
That is, $\displaystyle 1^2 + 2^2 + 3^2 + \cdots + k^2 = \frac{1}{6}k(k+1)(2k+1)$.
Step 3: Show it is true for $n=k+1$.
That is, $\displaystyle 1^2 + 2^2 + 3^2 + \cdots + k^2 + (k+1)^2 = \frac{1}{6}(k+1)(k+2)(2k+3)$.
\begin{aligned} \displaystyle \require{color} \text{LHS } &= 1^2 + 2^2 + 3^2 + \cdots + k^2 + (k+1)^2 \\ &= \frac{1}{6}k(k+1)(2k+1) + (k+1)^2 &\color{green} \text{replaced by the assumption in Step 2} \\ &= (k+1)\Big[\frac{1}{6}k(2k+1) + (k+1)\Big] &\color{green} \text{factorised by (k+1)} \\ &= (k+1) \times \frac{2k^2 + k + 6k + 6}{6} \\ &= \frac{1}{6}(k+1)(2k^2 + 7k + 6) \\ &= \frac{1}{6}(k+1)(k+2)(2k+3) \\ &= \text{RHS} \\ \end{aligned}
Therefore it is true for $n=k+1$.
Therefore the statement is true for $n \ge 1$.