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 + 1, that 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