Mathematical Induction
         Mathematical induction examples
Mathematical Induction
Mathematical induction is a formal method of proving that all positive integers n have a certain property P(n)
The principle of mathematical induction states that a statement P(n) is true for all positive integers, n N 
                        (i)  if it is true for n = 1, that is, P(1) is true and
                       (ii)  if P(k) is true implies P(k + 1) is true.
Thus, every proof using the mathematical induction consists of the following three steps:
                     1) Prove that the statement is true for the first term in the sequence (or series),
                        i.e., prove P(1) is true for n = 1,
                     2) Assume that the statement is true for a particular value n = k,
                         i.e., assume P(k) is true
                     3) Prove that the statement is true for the next term in the sequence n = k + 1
                        i.e., prove P(k) is true implies P(k + 1) is true.
Mathematical induction examples
Example:  Prove by mathematical induction that for all positive integers n
1 + 3 + 5 + . . . + (2n - 1) = n2
Solution:   1) For n = 1, we have  2 1 - 1 = 12therefore P(1) holds,
                 2) Assume that the statement is true for a particular value n = k, that is
1 + 3 + 5 + . . . + (2k - 1) = k2
                 3) Prove that the sum is true for n = k + 1that is
1 + 3 + 5 + . . . + [2(k + 1) - 1] = (k + 1)2
If, to the left and right side of the equality 2) we add 2k + 1 increased is given series by next term
1 + 3 + 5 + . . . + (2k - 1) + 2k + 1 = k2 + 2k + 1 = (k + 1)2
thus, the given statement is true for all positive integers.
Example:  Prove by mathematical induction that for all positive integers n
1 + 2 + 3 + . . . + n = n(n + 1)/2
Solution:   1) For n = 1, we have  1 = 1 (1 + 1)/2 = 1therefore P(1) holds,
                 2) Assume that the statement is true for a particular value n = k, that is
1 + 2 + 3 + . . . + k = k(k + 1)/2
                 3) Prove that the sum is true for n = k + 1, that is
1 + 2 + 3 + . . . + (k + 1) = (k + 1)(k + 2)/2
If, to the left and right side of the equality 2) we add k + 1 increased is given series by next term
1 + 2 + 3 + . . . + k + (k + 1) = k(k + 1)/2 + (k + 1) = [k(k + 1) + 2(k + 1)]/2 = (k + 1)(k + 2)/2
therefore, the given statement is true for all positive integers.
Example:  Prove by mathematical induction that for all positive integers n
12 + 22 + 32 + . . . + n2 = n(n + 1)(2n + 1)/6
Solution:   1) For n = 1, we have  12 = 1 ( 1 + 1)(2 1 + 1)/6 = 6/6 = 1  therefore P(1) holds,
                 2) Assume that the statement is true for a particular value n = k, that is
12 + 22 + 32 + . . . + k2 = k(k + 1)(2k + 1)/6
                 3) Prove that the sum is true for n = k + 1, that is
12 + 22 + 32 + . . . + (k + 1)2 = (k + 1)(k + 2)(2k + 3)/6
If, to the left and right side of the equality 2) we add (k + 1)2 increased is given series by next term
12 + 22 + 32 + . . . + k2 + (k + 1)2 = k(k + 1)(2k + 1)/6 + (k + 1)2 = (k + 1)(2k2 + 7k + 6)/6
                                                             = (k + 1)(k + 2)(2k + 3)/6
therefore, the given statement is true for all positive integers.
Example:  Prove by mathematical induction that for all positive integers n
1 2 + 2 3 + 3 4 + . . . + n (n + 1) = n(n + 1)(n + 2)/3
Solution:   1) For n = 1, we have  1 2 = 1 (1 + 1)(1 + 2)/3 = 1 2 therefore P(1) is true,
                 2) Assume that the statement is true for a particular value n = k, that is
1 2 + 2 3 + 3 4 + . . . + k (k + 1) = k(k + 1)(k + 2)/3
                 3) By adding (k + 1) (k + 2) to both sides of of the equality 2),  that is
1 2 + 2 3 + 3 4 + . . . + k (k + 1) + (k + 1) (k + 2) = k(k + 1)(k + 2)/3 + (k + 1) (k + 2)
                                                                                              = (k + 1)(k + 2)(k + 3)/3
given sum is increased by the value of the next term of the series to prove P(n + 1) is true for all positive integers.
Example:  Prove by mathematical induction that the formula  an = a1 + (n - 1)d,
for the general term of an arithmetic sequence, holds.
Solution:   1) For n = 1, we obtain an = a1 + (1 - 1)d = a1, so P(1) is true,
                 2) Assume that the formula an = a1 + (n - 1) holds for all positive integers n > 1, then
      3) We should prove that the formula holds for n + 1, that is  an + 1 = a1 + [(n  + 1) - 1]d = a1 + n d.
Since, by assumption an = a1 + (n - 1)d, and by the definition of an arithmetic sequence an + 1 - an = d,
then,  an + 1 = an + d = a1 + (n - 1)d + d = a1 + n d.
Example:  Prove by mathematical induction that the formula Sn = (n/2) (a1 + an) for the sum of the first n terms of an arithmetic sequence, holds.
Solution:   1) For n = 1, we obtain S1 = (1/2) (a1 + a1) = a1, so P(1) is true,
                 2) Assume that the formula Sn = (n/2) (a1 + an) holds for all positive integers n > 1, then
3) We should prove that the formula holds for n + 1, that is
Proof, since
Example:  Prove by mathematical induction that the formula an = a1   r n - 1 for the general term of a geometric sequence, holds.
Solution:   1) For n = 1, we obtain an = a1   r 1 - 1 = a1, so P(1) is true,
                 2) Assume that the formula an = a1   r n - 1 holds for all positive integers n > 1, then
                 3) We should prove that the formula holds for n + 1, that is  an + 1 = a1   r (n + 1) - 1 = a1   r n.
Since, by assumption an = a1   r n - 1, and by the definition of a geometric sequence an + 1 = an   r,
then,  an + 1 = an   r = a1   r n - 1   r = a1   r n.
Example:  Prove by mathematical induction that the formula
for the sum of the first n terms of a geometric sequence, holds.
Solution:   1) For n = 1, we obtain so P(1) is true,
                 2) Assume that the formula  holds for all positive integers n > 1, then
                 3) We should prove that the formula holds for n + 1, that is
Proof, as
Intermediate algebra contents
Copyright 2004 - 2020, Nabla Ltd.  All rights reserved.