#mathematical questions and answers

#

# Mathematical Induction – Problems With Solutions

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

Use mathematical induction to prove that

**1 + 2 + 3 +. + n = n (n + 1) / 2**

for all positive integers n.

__Solution to Problem 1:__

- Let the statement P (n) be

1 + 2 + 3 +. + n = n (n + 1) / 2

Right Side = 1 (1 + 1) / 2 = 1

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

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

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

**1 2 + 2 2 + 3 2 +. + n 2 = n (n + 1) (2n + 1)/ 6**

For all positive integers n.

__Solution to Problem 2:__

- Statement P (n) is defined by

1 2 + 2 2 + 3 2 +. + n 2 = n (n + 1) (2n + 1)/ 2

Left Side = 1 2 = 1

Right Side = 1 (1 + 1) (2*1 + 1)/ 6 = 1

1 2 + 2 2 + 3 2 +. + k 2 = k (k + 1) (2k + 1)/ 6

1 2 + 2 2 + 3 2 +. + k 2 + (k + 1) 2 = k (k + 1) (2k + 1)/ 6 + (k + 1) 2

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

= (k + 1) [ 2k 2 + 7k + 6 ] /6

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

1 2 + 2 2 + 3 2 +. + k 2 + (k + 1) 2 = (k + 1) [ (k + 2) (2k + 3) ] /6

Use mathematical induction to prove that

**1 3 + 2 3 + 3 3 +. + n 3 = n 2 (n + 1) 2 / 4**

for all positive integers n.

__Solution to Problem 3:__

- Statement P (n) is defined by

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

Left Side = 1 3 = 1

Right Side = 1 2 (1 + 1) 2 / 4 = 1

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

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

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

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

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

1 3 + 2 3 + 3 3 +. + k 3 + (k + 1) 3 = (k + 1) 2 [ (k + 2) 2 ] / 4

Prove that for any positive integer number n. **n 3 + 2 n** is divisible by 3

__Solution to Problem 4:__

- Statement P (n) is defined by

n 3 + 2 n is divisible by 3

3 is divisible by 3

k 3 + 2 k is divisible by 3

is equivalent to

k 3 + 2 k = 3 M. where M is a positive integer.

(k + 1) 3 + 2 (k + 1) = k 3 + 3 k 2 + 5 k + 3

= [ k 3 + 2 k] + [3 k 2 + 3 k + 3]

= 3 M + 3 [ k 2 + k + 1 ] = 3 [ M + k 2 + k + 1 ]

Prove that **3 n n 2** for n = 1, n = 2 and use the mathematical induction to prove that 3 n n 2 for n a positive integer greater than 2.

__Solution to Problem 5:__

- Statement P (n) is defined by

3 * 3 k 3 * k 2

k 2 2 k and k 2 1

2 k 2 2 k + 1

3 k 2 k 2 + 2 k + 1

3 * k 2 (k + 1) 2

3 * 3 k (k + 1) 2

3 k + 1 (k + 1) 2

Prove that **n. 2 n** 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.)

__Solution to Problem 6:__

- Statement P (n) is defined by

k! (k + 1) 2 k (k + 1)

2 k (k + 1) 2 * 2 k

2 k (k + 1) 2 k + 1

Use mathematical induction to prove De Moivre’s theorem

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

for n a positive integer.

__Solution to Problem 7:__

- STEP 1: For n = 1

[ R (cos t + i sin t) ] 1 = R 1 (cos 1*t + i sin 1*t)

[ R (cos t + i sin t) ] k = R k (cos kt + i sin kt)

[ 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)

[ 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) ]

(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

[ R (cos t + i sin t) ] k + 1 = R k + 1 [ cos (k + 1)t + sin(k + 1)t ]