 # Introduction to Linear Algebra and Calculus III – Mathematical Induction

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

### 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

# Exercise:

### 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

### 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)}$$