Mathematical Induction

Mathematical Induction

The principle of mathematical induction is used to prove that a given proposition (formula, equality, inequality…) is true for all positive integer numbers greater than or equal to some integer N.

Let us denote the proposition in question by P (n), where n is a positive integer. The proof involves two steps: 

Step 1: We first establish that the proposition P (n) is true for the lowest possible value of the positive integer n.

Step 2: We assume that P (k) is true and establish that P (k+1) is also true

 

Problem 1

Use mathematical induction to prove that
1 + 2 + 3 + ... + n = n (n + 1) / 2
for all positive integers n.
Let the statement P (n) be
1 + 2 + 3 + ... + n = n (n + 1) / 2
STEP 1: We first show that p (1) is true.
Left Side = 1
Right Side = 1 (1 + 1) / 2 = 1
Both sides of the statement are equal hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 + 2 + 3 + ... + k = k (k + 1) / 2
and show that p (k + 1) is true by adding k + 1 to both sides of the above statement
1 + 2 + 3 + ... + k + (k + 1) = k (k + 1) / 2 + (k + 1)
= (k + 1)(k / 2 + 1)
= (k + 1)(k + 2) / 2
The last statement may be written as
1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2) / 2
Which is the statement p(k + 1).

 

Problem 2

Prove that
1 ² + 2 ² + 3 ² + ... + n ² = n (n + 1) (2n + 1)/ 6
For all positive integers n.
Statement P (n) is defined by
1 ² + 2 ² + 3 ² + ... + n ² = n (n + 1) (2n + 1)/ 2
STEP 1: We first show that p (1) is true.
Left Side = 1 ² = 1
Right Side = 1 (1 + 1) (2*1 + 1)/ 6 = 1
Both sides of the statement are equal hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 ² + 2 ² + 3 ² + ... + k ² = k (k + 1) (2k + 1)/ 6
and show that p (k + 1) is true by adding (k + 1) ² to both sides of the above statement
1 ² + 2 ² + 3 ² + ... + k ² + (k + 1) ² = k (k + 1) (2k + 1)/ 6 + (k + 1) ²
Set common denominator and factor k + 1 on the right side
= (k + 1) [ k (2k + 1)+ 6 (k + 1) ] /6
Expand k (2k + 1)+ 6 (k + 1)
= (k + 1) [ 2k ² + 7k + 6 ] /6
Now factor 2k ² + 7k + 6.
= (k + 1) [ (k + 2) (2k + 3) ] /6
We have started from the statement P(k) and have shown that
1 ² + 2 ² + 3 ² + ... + k ² + (k + 1) ² = (k + 1) [ (k + 2) (2k + 3) ] /6
Which is the statement P(k + 1).

Problem 3

Use mathematical induction to prove that
1 ³ + 2 ³ + 3 ³ + ... + n ³ = n ² (n + 1) ² / 4
for all positive integers n.

Statement P (n) is defined by 

1 ³ + 2 ³+ 3 ³ + ... + n ³ = n ² (n + 1) ² / 4

STEP 1: We first show that p (1) is true.
Left Side = 1 ³ = 1
Right Side = 1 ² (1 + 1) ² / 4 = 1
hence p (1) is true.
STEP 2: We now assume that p (k) is true
1 ³ + 2 ³ + 3 ³ + ... + k ³ = k ² (k + 1) ² / 4
add (k + 1) ³ to both sides
1 ³ + 2 ³ + 3 ³ + ... + k ³ + (k + 1) ³ = k ² (k + 1) ² / 4 + (k + 1) ³
factor (k + 1) ² on the right side
= (k + 1) ² [ k ² / 4 + (k + 1) ]
set to common denominator and group
= (k + 1) ² [ k ² + 4 k + 4 ] / 4
= (k + 1) ² [ (k + 2) ² ] / 4
We have started from the statement P(k) and have shown that
1 ³ + 2 ³ + 3 ³ + ... + k ³ + (k + 1) ³ = (k + 1) ² [ (k + 2) ² ] / 4
Which is the statement P(k + 1).

 

Problem 4

Prove that for any positive integer number n , n ³ + 2 n is divisible by 3 

Statement P (n) is defined by 

n ³ + 2 n is divisible by 3
STEP 1: We first show that p (1) is true. Let n = 1 and calculate n ³ + 2n
1 ³ + 2(1) = 3
3 is divisible by 3
hence p (1) is true.
STEP 2: We now assume that p (k) is true
k ³ + 2 k is divisible by 3
is equivalent to
k ³ + 2 k = 3 M , where M is a positive integer.
We now consider the algebraic expression (k + 1) ³ + 2 (k + 1); expand it and group like terms
(k + 1) ³ + 2 (k + 1) = k ³ + 3 k ² + 5 k + 3
= [ k ³ + 2 k] + [3 k ² + 3 k + 3]
= 3 M + 3 [ k ² + k + 1 ] = 3 [ M + k ² + k + 1 ]
Hence (k + 1) ³ + 2 (k + 1) is also divisible by 3 and therefore statement P(k + 1) is true.

 

Problem 5

Prove that 3 ⁿ > n ² for n = 1, n = 2 and use the mathematical induction to prove that 3 ⁿ > n ² for n a positive integer greater than 2.
Statement P (n) is defined by 3 ⁿ > n ²

STEP 1: We first show that p (1) is true. Let n = 1 and calculate 3 ¹ and 1 ² and compare them
3 ¹ = 3
1 ² = 1
3 is greater than 1 and hence p (1) is true.
Let us also show that P(2) is true.
3 ² = 9
2 ² = 4
Hence P(2) is also true.
STEP 2: We now assume that p (k) is true
3 ^k > k ²
Multiply both sides of the above inequality by 3
3 * 3 ^k > 3 * k ²
The left side is equal to 3 ^{k + 1}. For k >, 2, we can write
k ² > 2 k and k ² > 1
We now combine the above inequalities by adding the left hand sides and the right hand sides of the two inequalities
2 k ² > 2 k + 1
We now add k ² to both sides of the above inequality to obtain the inequality
3 k ² > k ² + 2 k + 1
Factor the right side we can write
3 * k ² > (k + 1) ²
If 3 * 3 ^k > 3 * k ² and 3 * k ² > (k + 1) ^{2 then}
3 * 3 ^k > (k + 1) ²
Rewrite the left side as 3 ^{k + 1}
3 ^{k + 1} > (k + 1) ²
Which proves tha P(k + 1) is true

 

Problem 6

Prove that n ! > 2 ⁿ for n a positive integer greater than or equal to 4. (Note: n! is n factorial and is given by 1 * 2 * ...* (n-1)*n.)
Statement P (n) is defined by

n! > 2 ⁿ
STEP 1: We first show that p (4) is true. Let n = 4 and calculate 4 ! and 2 ⁿ and compare them
4! = 24
2 ⁴ = 16
24 is greater than 16 and hence p (4) is true.
STEP 2: We now assume that p (k) is true
k! > 2 ^k
Multiply both sides of the above inequality by k + 1
k! (k + 1)> 2 ^k (k + 1)
The left side is equal to (k + 1)!. For k >, 4, we can write
k + 1 > 2
Multiply both sides of the above inequality by 2 ^k to obtain
2 ^k (k + 1) > 2 * 2 ^k
The above inequality may be written
2 ^k (k + 1) > 2 ^{k + 1}
We have proved that (k + 1)! > 2 ^k (k + 1) and 2 ^k (k + 1) > 2 ^{k + 1} we can now write
(k + 1)! > 2 ^{k + 1}
We have assumed that statement P(k) is true and proved that statment P(k+1) is also true.

 

Problem 7

Use mathematical induction to prove De Moivre's theorem

[ R (cos t + i sin t) ] ⁿ = R ⁿ(cos nt + i sin nt)

for n a positive integer.
STEP 1: For n = 1

[ R (cos t + i sin t) ] ¹ = R ¹(cos 1*t + i sin 1*t)
It can easily be seen that the two sides are equal.
STEP 2: We now assume that the theorem is true for n = k, hence
[ R (cos t + i sin t) ] ^k = R ^k(cos kt + i sin kt)
Multiply both sides of the above equation by R (cos t + i sin t)
[ R (cos t + i sin t) ] ^k R (cos t + i sin t) = R ^k(cos kt + i sin kt) R (cos t + i sin t)
Rewrite the above as follows
[ R (cos t + i sin t) ] ^{k + 1} = R ^{k + 1} [ (cos kt cos t - sin kt sin t) + i (sin kt cos t + cos kt sin t) ]
Trigonometric identities can be used to write the trigonometric expressions (cos kt cos t - sin kt sin t) and (sin kt cos t + cos kt sin t) as follows
(cos kt cos t - sin kt sin t) = cos(kt + t) = cos(k + 1)t
(sin kt cos t + cos kt sin t) = sin(kt + t) = sin(k + 1)t
Substitute the above into the last equation to obtain
[ R (cos t + i sin t) ] ^{k + 1} = R ^{k + 1} [ cos (k + 1)t + sin(k + 1)t ]
It has been established that the theorem is true for n = 1 and that if it assumed true for n = k it is true for n = k + 1.

More Examples

1. Using the principle of mathematical induction, prove that 

1² + 2² + 3² + ..... + n² = (1/6){n(n + 1)(2n + 1} for all n ∈ N. 

Solution: 

Let the given statement be P(n). Then, 

P(n): 1² + 2² + 3² + ..... +n² = (1/6){n(n + 1)(2n + 1)}. 

Putting n =1 in the given statement, we get 

LHS = 1² = 1 and RHS = (1/6) × 1 × 2 × (2 × 1 + 1) = 1. 

Therefore LHS = RHS. 

Thus, P(1) is true. 

Let P(k) be true. Then,

P(k): 1² + 2² + 3² + ..... + k² = (1/6){k(k + 1)(2k + 1)}.

Now, 1² + 2² + 3² + ......... + k² + (k + 1)²

                    = (1/6) {k(k + 1)(2k + 1) + (k + 1)²

                    = (1/6){(k + 1).(k(2k + 1)+6(k + 1))}

                    = (1/6){(k + 1)(2k² + 7k + 6})

                    = (1/6){(k + 1)(k + 2)(2k + 3)}

                    = 1/6{(k + 1)(k + 1 + 1)[2(k + 1) + 1]}

⇒ P(k + 1): 1² + 2² + 3² + ….. + k² + (k+1)²

                    = (1/6){(k + 1)(k + 1 + 1)[2(k + 1) + 1]}

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.

2. By using mathematical induction prove that the given equation is true for all positive integers.

1 x 2 + 3 x 4 + 5 x 6 + …. + (2n - 1) x 2n = n(n+1)(4n−1)3$\frac{n(n+1)(4n-1)}{3}$

Solution:

From the statement formula

When n = 1,

LHS =1 x 2 = 2

RHS = 1(1+1)(4x1−1)3$\frac{1(1+1)(4x1-1)}{3}$ = 63$\frac{6}{3}$ = 2

Hence it is proved that P (1) is true for the equation.

Now we assume that P (k) is true or 1 x 2 + 3 x 4 + 5 x 6 + …. + (2k - 1) x 2k = k(k+1)(4k−1)3$\frac{k(k+1)(4k-1)}{3}$.

For P(k + 1)

LHS = 1 x 2 + 3 x 4 + 5 x 6 + …. + (2k - 1) x 2k + (2(k + 1) - 1) x 2(k + 1)

= k(k+1)(4k−1)3$\frac{k(k+1)(4k-1)}{3}$ + (2(k + 1) - 1) x 2(k + 1)

= (k+1)3$\frac{(k+1)}{3}$(4k² - k + 12 k + 6)

= (k+1)(4k2+8k+3k+6)3$\frac{(k+1)(4k^2+8k+3k+6)}{3}$

= (k+1)(k+2)(4k+3)3$\frac{(k+1)(k+2)(4k+3)}{3}$

= (k+1)((k+1)+1)(4(k+1)−1)3$\frac{(k+1)((k+1)+1)(4(k+1)-1)}{3}$ = RHS for P (k+1)

Now it is proved that P (k + 1) is also true for the equation.

So the given statement is true for all positive integers.

3. Using the principle of mathematical induction, prove that

1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ..... + n(n + 1) = (1/3){n(n + 1)(n + 2)}.

Solution:

Let the given statement be P(n). Then,

P(n): 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ..... + n(n + 1) = (1/3){n(n + 1)(n + 2)}.

Thus, the given statement is true for n = 1, i.e., P(1) is true.

Let P(k) be true. Then,

P(k): 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ..... + k(k + 1) = (1/3){k(k + 1)(k + 2)}.

Now, 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +...+ k(k + 1) + (k + 1)(k + 2)

          = (1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ....... + k(k + 1)) + (k + 1)(k + 2)

          = (1/3) k(k + 1)(k + 2) + (k + 1)(k + 2) [using (i)]

          = (1/3) [k(k + 1)(k + 2) + 3(k + 1)(k + 2)

          = (1/3){(k + 1)(k + 2)(k + 3)}

⇒ P(k + 1): 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 +......+ (k + 1)(k + 2)

                     = (1/3){k + 1 )(k + 2)(k +3)}

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1)is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all values of ∈ N.


4. By using mathematical induction prove that the given equation is true for all positive integers.

2 + 4 + 6 + …. + 2n = n(n+1)

Solution:

From the statement formula

When n = 1 or P (1),

LHS = 2

RHS =1 × 2 = 2

So P (1) is true.

Now we assume that P (k) is true or 2 + 4 + 6 + …. + 2k = k(k + 1).

For P(k + 1),

LHS = 2 + 4 + 6 + …. + 2k + 2(k + 1) 

= k(k + 1) + 2(k + 1) 

= (k + 1) (k + 2)

= (k + 1) ((k + 1) + 1) = RHS for P(k+1)

Now it is proved that P(k+1) is also true for the equation.

So the given statement is true for all positive integers.

5. Using the principle of mathematical induction, prove that

1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 +.....+ (2n - 1)(2n + 1) = (1/3){n(4n² + 6n - 1).

Solution:

Let the given statement be P(n). Then,

P(n): 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 +...... + (2n - 1)(2n + 1)= (1/3)n(4n² + 6n - 1).

When n = 1, LHS = 1 ∙ 3 = 3 and RHS = (1/3) × 1 × (4 × 1² + 6 × 1 - 1)

                                                   = {(1/3) × 1 × 9} = 3.

LHS = RHS.

Thus, P(1) is true.

Let P(k) be true. Then,

P(k): 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 + ….. + (2k - 1)(2k + 1) = (1/3){k(4k² + 6k - 1) ......(i)

Now,

1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 + …….. + (2k - 1)(2k + 1) + {2k(k + 1) - 1}{2(k + 1) + 1}

          = {1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 + ………… + (2k - 1)(2k + 1)} + (2k + 1)(2k + 3)

          = (1/3) k(4k² + 6k - 1) + (2k + 1)(2k + 3) [using (i)]

          = (1/3) [(4k³ + 6k² - k) + 3(4k² + 8k + 3)]

          = (1/3)(4k³ + 18k² + 23k + 9)

          = (1/3){(k + 1)(4k² + 14k + 9)}

          = (1/3)[k + 1){4k(k + 1) ² + 6(k + 1) - 1}]

⇒ P(k + 1): 1 ∙ 3 + 3 ∙ 5 + 5 ∙ 7 + ..... + (2k + 1)(2k + 3)

           = (1/3)[(k + 1){4(k + 1)² + 6(k + 1) - 1)}]

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.


6. By using mathematical induction prove that the given equation is true for all positive integers.

2 + 6 + 10 + ….. + (4n - 2) = 2n² 

Solution:

From the statement formula

When n = 1 or P(1),

LHS = 2

RHS = 2 × 1² = 2

So P(1) is true.

Now we assume that P (k) is true or 2 + 6 + 10 + ….. + (4k - 2) = 2k²

For P (k + 1),

LHS = 2 + 6 + 10 + ….. + (4k - 2) + (4(k + 1) - 2)

= 2k² + (4k + 4 - 2)

= 2k² + 4k + 2

= (k+1)²

= RHS for P(k+1)

Now it is proved that P(k+1) is also true for the equation.

So the given statement is true for all positive integers.

7. Using the principle of mathematical induction, prove that

1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ..... + 1/{n(n + 1)} = n/(n + 1)

Solution:

Let the given statement be P(n). Then,

P(n): 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ..... + 1/{n(n + 1)} = n/(n + 1).

Putting n = 1 in the given statement, we get

LHS= 1/(1 ∙ 2) = and RHS = 1/(1 + 1) = 1/2.

LHS = RHS.

Thus, P(1) is true.

Let P(k) be true. Then,

P(k): 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ..... + 1/{k(k + 1)} = k/(k + 1) ..…(i)

Now 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ..... + 1/{k(k + 1)} + 1/{(k + 1)(k + 2)}

[1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ..... + 1/{k(k + 1)}] + 1/{(k + 1)(k + 2)}

= k/(k + 1)+1/{ (k + 1)(k + 2)}.

{k(k + 2) + 1}/{(k + 1)²/[(k + 1)k + 2)] using …(ii)

= {k(k + 2) + 1}/{(k + 1)(k + 2}

= {(k + 1)² }/{(k + 1)(k + 2)}

= (k + 1)/(k + 2) = (k + 1)/(k + 1 + 1)

⇒ P(k + 1): 1/(1 ∙ 2) + 1/(2 ∙ 3) + 1/(3 ∙ 4) + ……… + 1/{ k(k + 1)} + 1/{(k + 1)(k + 2)}

                    = (k + 1)/(k + 1 + 1)

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1)is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.

8. Using the principle of mathematical induction, prove that

{1/(3 ∙ 5)} + {1/(5 ∙ 7)} + {1/(7 ∙ 9)} + ….... + 1/{(2n + 1)(2n + 3)} = n/{3(2n + 3)}.

Solution:

Let the given statement be P(n). Then,

P(n): {1/(3 ∙ 5) + 1/(5 ∙ 7) + 1/(7 ∙ 9) + ……. + 1/{(2n + 1)(2n + 3)} = n/{3(2n + 3).

Putting n = 1 in the given statement, we get

and LHS = 1/(3 ∙ 5) = 1/15 and RHS = 1/{3(2 × 1 + 3)} = 1/15.

LHS = RHS

Thus , P(1) is true.

Let P(k) be true. Then,

P(k): {1/(3 ∙ 5) + 1/(5 ∙ 7) + 1/(7 ∙ 9) + …….. + 1/{(2k + 1)(2k + 3)} = k/{3(2k + 3)} ….. (i)

Now, 1/(3 ∙ 5) + 1/(5 ∙ 7) + ..…… + 1/[(2k + 1)(2k + 3)] + 1/[{2(k + 1) + 1}2(k + 1) + 3

          = {1/(3 ∙ 5) + 1/(5 ∙ 7) + ……. + [1/(2k + 1)(2k + 3)]} + 1/{(2k + 3)(2k + 5)}

          = k/[3(2k + 3)] + 1/[2k + 3)(2k + 5)] [using (i)]

           = {k(2k + 5) + 3}/{3(2k + 3)(2k + 5)}

          = (2k² + 5k + 3)/[3(2k + 3)(2k + 5)]

          = {(k + 1)(2k + 3)}/{3(2k + 3)(2k + 5)}

           = (k + 1)/{3(2k + 5)}

          = (k + 1)/[3{2(k + 1) + 3}]

= P(k + 1): 1/(3 ∙ 5) + 1/(5 ∙ 7) + …….. + 1/[2k + 1)(2k + 3)] + 1/[{2(k + 1) + 1}{2(k + 1) + 3}]

                    = (k + 1)/{3{2(k + 1) + 3}]

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for n ∈ N.


9. By induction prove that 3ⁿ - 1 is divisible by 2 is true for all positive integers.

Solution:

When n = 1, P(1) = 3¹ - 1 = 2 which is divisible by 2.

So P(1) is true.

Now we assume that P(k) is true or 3^k - 1 is divisible by 2.

When P(k + 1),

3^{k + 1} - 1= 3^k x 3 - 1 = 3^k x 3 - 3 + 2 = 3(3^k - 1) + 2

As (3^k - 1) and 2 both are divisible by 2, it is proved that divisible by 2 is true for all positive integers.

10. Using the principle of mathematical induction, prove that

1/(1 ∙ 2 ∙ 3) + 1/(2 ∙ 3 ∙ 4) + …….. + 1/{n(n + 1)(n + 2)} = {n(n + 3)}/{4(n + 1)(n + 2)} for all n ∈ N.

Solution:

Let P (n): 1/(1 ∙ 2 ∙ 3) + 1/(2 ∙ 3 ∙ 4) + ……. + 1/{n(n + 1)(n + 2)} = {n(n + 3)}/{4(n + 1)(n + 2)} .

Putting n = 1 in the given statement, we get

LHS = 1/(1 ∙ 2 ∙ 3) = 1/6 and RHS = {1 × (1 + 3)}/[4 × (1 + 1)(1 + 2)] = ( 1 × 4)/(4 × 2 × 3) = 1/6.

Therefore LHS = RHS.

Thus, the given statement is true for n = 1, i.e., P(1) is true.

Let P(k) be true. Then,

P(k): 1/(1 ∙ 2 ∙ 3) + 1/(2 ∙ 3 ∙ 4) + ……... + 1/{k(k + 1)(k + 2)} = {k(k + 3)}/{4(k + 1)(k + 2)}. …….(i)

Now, 1/(1 ∙ 2 ∙ 3) + 1/(2 ∙ 3 ∙ 4) + ………….. + 1/{k(k + 1)(k + 2)} + 1/{(k + 1)(k + 2)(k + 3)}

           = [1/(1 ∙ 2 ∙ 3) + 1/(2 ∙ 3 ∙ 4) + ………..…. + 1/{ k(k + 1)(k + 2}] + 1/{(k + 1)(k + 2)(k + 3)}

           = [{k(k + 3)}/{4(k + 1)(k + 2)} + 1/{(k + 1)(k + 2)(k + 3)}]
                                                            [using(i)]

           = {k(k + 3)² + 4}/{4(k + 1)(k + 2)(k + 3)}

           = (k³ + 6k² + 9k + 4)/{4(k + 1)(k + 2)(k + 3)}

           = {(k + 1)(k + 1)(k + 4)}/{4 (k + 1)(k + 2)(k + 3)}

           = {(k + 1)(k + 4)}/{4(k + 2)(k + 3)

⇒ P(k + 1): 1/(1 ∙ 2 ∙ 3) + 1/(2 ∙ 3 ∙ 4) + ……….….. + 1/{(k + 1)(k + 2)(k + 3)}

                    = {(k + 1)(k + 2)}/{4(k + 2)(k + 3)}

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.



11. By induction prove that n² - 3n + 4 is even and it is true for all positive integers.

Solution:

When n = 1, P (1) = 1 - 3 + 4 = 2 which is an even number.

So P (1) is true.

Now we assume that P (k) is true or k² - 3k + 4 is an even number.

When P (k + 1),

(k + 1)² - 3(k + 1) + 4

= k² + 2k + 1 - 3k + 3 + 4

= k² - 3k + 4 + 2(k + 2)

As k² - 3k + 4 and 2(k + 2) both are even, there sum also will be an even number.

So it is proved that n² - 3n + 4 is even is true for all positive integers.

12. Using the Principle of mathematical induction, prove that

{1 - (1/2)}{1 - (1/3)}{1 - (1/4)} ….... {1 - 1/(n + 1)} = 1/(n + 1) for all n ∈ N.

Solution:

Let the given statement be P(n). Then,

P(n): {1 - (1/2)}{1 - (1/3)}{1 - (1/4)} ….... {1 - 1/(n + 1)} = 1/(n + 1).

When n = 1, LHS = {1 – (1/2)} = ½ and RHS = 1/(1 + 1) = ½.

Therefore LHS = RHS.

Thus, P(1) is true.

Let P(k) be true. Then,

P(k): {1 - (1/2)}{1 - (1/3)}{1 - (1/4)} ….... [1 - {1/(k + 1)}] = 1/(k + 1)

Now, [{1 - (1/2)}{1 - (1/3)}{1 - (1/4)} ….... [1 - {1/(k + 1)}] ∙ [1 – {1/(k + 2)}]

           = [1/(k + 1)] ∙ [{(k + 2 ) - 1}/(k + 2)}]

           = [1/(k + 1)] ∙ [(k + 1)/(k + 2)]

           = 1/(k + 2)

Therefore p(k + 1): [{1 - (1/2)}{1 - (1/3)}{1 - (1/4)} ….... [1 - {1/(k + 1)}] = 1/(k + 2)

⇒ P(k + 1) is true, whenever P(k) is true.

Thus, P(1) is true and P(k + 1) is true, whenever P(k) is true.

Hence, by the principle of mathematical induction, P(n) is true for all n ∈ N.