** **

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

**STEP 1: We first show that p (1) is true.**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)

**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).****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**

**STEP 1: We first show that p (1) is true.**Left Side = 1 2 = 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 + 2 2 + 3 2 +. + k 2 = k (k + 1) (2k + 1)/ 6

**and show that p (k + 1) is true by adding (k + 1) 2 to both sides of the above statement**1 2 + 2 2 + 3 2 +. + k 2 + (k + 1) 2 = k (k + 1) (2k + 1)/ 6 + (k + 1) 2

**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 2 + 7k + 6 ] /6

**Now factor 2k 2 + 7k + 6.**= (k + 1) [ (k + 2) (2k + 3) ] /6

**We have started from the statement P(k) and have shown that**1 2 + 2 2 + 3 2 +. + k 2 + (k + 1) 2 = (k + 1) [ (k + 2) (2k + 3) ] /6

**Which is the statement P(k + 1).****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**

**STEP 1: We first show that p (1) is true.**Left Side = 1 3 = 1

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

**hence p (1) is true.****STEP 2: We now assume that p (k) is true**1 3 + 2 3 + 3 3 +. + k 3 = k 2 (k + 1) 2 / 4

**add (k + 1) 3 to both sides**1 3 + 2 3 + 3 3 +. + k 3 + (k + 1) 3 = k 2 (k + 1) 2 / 4 + (k + 1) 3

**factor (k + 1) 2 on the right side**= (k + 1) 2 [ k 2 / 4 + (k + 1) ]

**set to common denominator and group**= (k + 1) 2 [ k 2 + 4 k + 4 ] / 4

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

**We have started from the statement P(k) and have shown that**1 3 + 2 3 + 3 3 +. + k 3 + (k + 1) 3 = (k + 1) 2 [ (k + 2) 2 ] / 4

**Which is the statement P(k + 1).****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**

**STEP 1: We first show that p (1) is true. Let n = 1 and calculate n 3 + 2n**3 is divisible by 3

**hence p (1) is true.****STEP 2: We now assume that p (k) is true**k 3 + 2 k is divisible by 3

is equivalent to

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

**We now consider the algebraic expression (k + 1) 3 + 2 (k + 1); expand it and group like terms**(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 ]

**Hence (k + 1) 3 + 2 (k + 1) is also divisible by 3 and therefore statement P(k + 1) is true.****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**

**STEP 1: We first show that p (1) is true. Let n = 1 and calculate 3 1 and 1 2 and compare them****3 is greater than 1 and hence p (1) is true.****Let us also show that P(2) is true.****Hence P(2) is also true.****STEP 2: We now assume that p (k) is true****Multiply both sides of the above inequality by 3**3 * 3 k 3 * k 2

**The left side is equal to 3 k + 1. For k , 2, we can write**k 2 2 k and k 2 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 2 k + 1

**We now add k 2 to both sides of the above inequality to obtain the inequality**3 k 2 k 2 + 2 k + 1

**Factor the right side we can write**3 * k 2 (k + 1) 2

**If 3 * 3 k 3 * k 2 and 3 * k 2 (k + 1) 2 then**3 * 3 k (k + 1) 2

**Rewrite the left side as 3 k + 1**3 k + 1 (k + 1) 2

**Which proves tha P(k + 1) is true****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**

**STEP 1: We first show that p (4) is true. Let n = 4 and calculate 4. and 2 n and compare them****24 is greater than 16 and hence p (4) is true.****STEP 2: We now assume that p (k) is true****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****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****We have assumed that statement P(k) is true and proved that statment P(k+1) is also true.****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:__

**[ R (cos t + i sin t) ] 1 = R 1 (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.**** **