Such a mathematical process of deducing the general result is called induction. However, the validity of the above identity is questionable since it has not been tested for all positive integers. To resolve such a difficulty, a mathematical procedure known as Mathematical Induction (M.I.) is introduced.

# Example

### 1. Base Step: Show P(1) is true

P(n): 1+3+5+7+ … + (2n-1) = \(n^{2}\)

P(1): LHS: 2(1)-1 =1

RHS: \((1)^{2}\) = 1

LHS=RHS for P(1)

### 2. Inductive Step: Assume P(k) is true.

P(k) = 1+3+5+7+…+(2k-1) = \(k^{2}\)

We need to show P(k+1) is true, i.e.: LHS = RHS for P(k+1)

### Let’s see.

P(k+1) LHS: 1+3+5+7+…+(2K-1) + (2(k+1)-1)

RHS: \((k+1)^{2}\)

We are going to show LHS= RHS

LHS: 1+3+5+7+….+(2k-1)+(2(k+1)-1)

= \(k^{2}\) +(2(k+1)-1)

= \(k^{2}\) +2k+2-1

= \(k^{2}\) +2k+1

= \((k+1)^{2}\) = RHS

### By M.I., P(n) is true for all n \(\geq\) 1

### 1. Basic step: Show P(1) is true

P(n): 1×2 + 2×3 + \(2^{2}\)x4 + …+ \(2^{n-1}\)(n+1) = \(2^{n}\)(n)

When n=1,

LHS: \(2^{1-1}\)(1+1) = \(2^{0}\)(2) = 2

RHS: \(2^{1}\)(1) =2

LHS=RHS for P(1).

### 2. Inductive step: Assume P(k) is true

P(k) = 1×2 + 2×3 + \(2^{2}\) x4 + … + \(2^{k-1}\)(k+1) = \(2^{k}\)(k)

We need to show P(k+1) is true.

### Let’s prove.

P(k+1):

LHS = 1×2 + 2×3 + \(2^{2}\)x4 + … + \(2^{k-1}\)(k+1) + \(2^{(k+1)-1}\)((k+1) +1)

RHS = \(2^{(k+1)}\)(k+1)

By assumption, *1×2 + 2×3 + \(2^{2}\)x4 + … + \(2^{k-1}\)(k+1) = \(2^{k}\)(k)*

1×2 + 2×3 + \(2^{2}\)x4 + … + \(2^{k-1}\)(k+1) + \(2^{(k+1)-1}\)((k+1) +1)

= *\(2^{k}\)(k)* + \(2^{(k+1)-1}\)((k+1) +1)

= \(2^{k}\) (k) + \(2^{k}\)(k+2)

= \(2^{k}\)(k+k+2)

= \(2^{k}\)(2k+2)

= \(2^{k}\)2{k+1}

=\(2^{k+1}\)(k+1)

=RHS

# Start with Base k then inductive step.

# Idea behind Inductive step: Assume P(k) is true, prove (k+1) step.

# Exercise:

#### Q17

### 1. Basic step: Show P(1) is true.

P(n) = \(\frac{1}{1×2} + \frac{1}{2×3} + … + \frac{1}{n(n+1)} = \frac{n}{n+1}\)

When n=1,

LHS: \(\frac{1}{1×2} + \frac{1}{2×3} + … + \frac{1}{1(1+1)} = \frac{1}{1+1}\)

= \(\frac{1}{2}\)

= RHS = \(\frac{1}{2}\)

### 2. Inductive step: Assume P(k) is true

P(k) = \(\frac{1}{1×2} + \frac{1}{2×3} + … + \frac{1}{k(k+1)} = \frac{k}{k+1}\)

We need to show P(k+1) is true.

### Let’s prove

P(k+1):

RHS = \( \frac{(k+1)}{(k+1)+1} \)

= \( \frac{(k+1)}{(k+2)} \)

LHS = \(\frac{1}{1×2} + \frac{1}{2×3} + … + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+1+1)} \)

= \( \frac{k}{k+1} + \frac{1}{(k+1)(k+1+1)} \)

= \( \frac{k(k+1+1)+1}{(𝑘+1)(𝑘+1+1)} \)

= \( \frac{k(k+2)+1}{(k+1)(k+2)} \)

= \( \frac{k^{2}+2k+1}{(k+1)(k+2)} \)

= \( \frac{(k+1)^{2}}{(k+1)(k+2)} \)

= \( \frac{(k+1)}{(k+2)} \)

= RHS

#### Q18

### 1. Basic Step: Show P(1) is true.

\( P(n) = \frac{2×3}{1×4} + \frac{5×6}{4×7} + … + \frac{(3n-1)(3n)}{(3n-2)(3n+1)} = \frac{3n(n+1)}{3n+1} \)

###### When n=1,

LHS: \( \frac{2×3}{1×4} + \frac{5×6}{4×7} + … + \frac{(3(1)-1)(3(1))}{(3(1)-2)(3(1)+1)} \)