Principle of Mathematical Induction

Mathematical induction Solved Examples:

Question 1
Given n belongs to the set of Natural Numbers. Prove that using principle of Mathematical induction
$1 +2 +3 +4 + .....+ n=\frac {n(n+1)}{2}$
Solution:
Let us assume this statement as P(n)
Step 1 Basis of Induction
for P(0), we have LHS side as 0
RHS= 0(0+1)/2=0
So LHS=RHS

Step 2 inductive hypothesis
Let us assume P(n) is true,then
$1 +2 +3 +4 + .....+ n=\frac {n(n+1)}{2}$
Step 3 inductive step
Now we have to prove for P(n+1)
$1+2+......(n)+(n+1)=\frac{(n+1)[(n+1)+1]}{2}$

Now lets us take LHS
= [1+2+......(n)] +(n+1)
=$\frac{n(n+1)}{2}+(n+1)$ as P(n) is assumed to be true
=$\frac{(n+1)[(n+1)+1]}{2}$

So P(n+1) is true if P(n) is true. Now Since P(0) is true, we can say P(n) is good for all natural numbers

Question 2

To prove by mathematical induction that
6 ⁽ⁿ⁺²⁾ + 7⁽²ⁿ⁺¹⁾
is divisible by 43 for each positive integer n.

Solution
Let P(n) be the statement
Step 1 Basis of Induction
P(1) =6 ⁽¹⁺¹⁾ + 7⁽²⁺¹⁾
= 559 = 43 X 13,
the formula is true for n = 1.

Step 2 inductive hypothesis
Assume that P(n) is true for n = k, that is
P(k)=6 ^(k+2) + 7^(2k+1)=43x
for some integer x.

Step 3 inductive step
Now show that the formula is true for n = k + 1.

Observe that
P(k+1)=6 ^(k+1+2) + 7^(2k+2+1)

= 6^(k+3) + 7^(2k+3)
=6^(k+2) + 7²7^(2k+1)
=6X6^(k+2) + (43+6)X7^(2k+1)
=6X6^(k+2) + 6X7^(2k+1)+43X7^(2k+1)
= 6 X ( P(k) ) + 43 X 7^(2k+1)

Since each component of this sum is divisible by 43 so is the entire sum and the formula holds for k + 1

Question 3

Prove using Mathematical induction for $n \geq 1$
$1+4+7+......(3n-2)=\frac{n(3n-1)}{2}$
Solution
Let us assume this statement as P(n)
Step 1 Basis of Induction
Then P(1)
$1=\frac{1(3-1)}{2}$
Step 2 inductive hypothesis
Assume that P(n) is true for n = k, that is
$1+4+7+......(3k-2)=\frac{k(3k-1)}{2}$
Step 3 inductive step
Now show that the formula is true for n = k + 1.

Observe that

$1+4+7+.....[3(k+1)-2]=\frac{(k+1)[3(k+1)-1])}{2}$
Let us take the LHS
$1+4+7+.....[3(k+1)-2]=1+4+7+......+(3k-2)+(3k+1)$
$=\frac{k(3-1)}{2}+(3k+1)$
$=\frac{3k^{2}+5k+2}{2}$
$=\frac{(k+1)[3(k+1)+1]}{2}$
Question 4

Prove by the Principle of Mathematical Induction that
$1 \times 1! + 2 \times 2! + 3 \times 3! + ... + n \times n! = (n + 1)! - 1$ for all natural numbers n.
Solution
Let P(n) be the given statement
P(n) : $1 \times 1! + 2 \times 2! + 3 \times 3! + ... + n \times n! = (n + 1)!-� 1$ for all natural numbers n.
Note that P (1) is true, since
P (1) :$ 1 \times 1! = 1 = 2 - 1 = 2! - 1$.
Assume that P(n) is true for some natural number k, i.e.,
P(k) :$ 1 \times 1! + 2 \times 2! + 3 \times 3! + ... + k \times k! = (k + 1)! � 1$
To prove P (k + 1) is true, we have
P (k + 1) :$ 1 \times 1! + 2 \times 2! + 3 \times 3! + ... + k \times k! + (k + 1) \times (k + 1)!$
$= (k + 1)! - 1 + (k + 1)! \times (k + 1)$
$= (k + 1 + 1) (k + 1)! - 1$
$= (k + 2) (k + 1)! - 1 = ((k + 2)! - 1$
Hence Provded by Mathematical Induction