Mathematical Induction – Problems With Solutions #answer #to #life


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

    • STEP 1: For n = 1

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

  • Leave a Reply

    Your email address will not be published. Required fields are marked *