# Mathematical Induction Fundamentals

The Mathematical Induction Fundamentals are defined for applying 3 steps: 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{AMSsymbols} \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{AMSsymbols} \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{AMSsymbols} \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{AMSsymbols} \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.

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{AMSsymbols} \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 \).

Algebra Algebraic Fractions Arc Binomial Expansion Capacity Common Difference Common Ratio Differentiation Double-Angle Formula Equation Exponent Exponential Function Factorials Factorise Functions Geometric Sequence Geometric Series Index Laws Inequality Integration Kinematics Length Conversion Logarithm Logarithmic Functions Mass Conversion Mathematical Induction Measurement Perfect Square Perimeter Prime Factorisation Probability Product Rule Proof Quadratic Quadratic Factorise Ratio Rational Functions Sequence Sketching Graphs Surds Time Transformation Trigonometric Functions Trigonometric Properties Volume

## Responses