

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) = n^{2} 
Solution:
1) For
n
= 1, we
have 2 · 1 
1 = 1^{2}, therefore
P(1)
holds, 
2)
Assume that the statement is true for a particular value
n
= k, that is

1
+ 3 + 5 + . . . + (2k 
1) = k^{2} 
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 = k^{2}
+ 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 = 1, therefore
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

1^{2}
+ 2^{2}
+ 3^{2} + . . . + n^{2} = n(n + 1)(2n + 1)/6 
Solution:
1) For
n
= 1, we
have 1^{2}
= 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

1^{2}
+ 2^{2}
+ 3^{2} + . . . + k^{2} = k(k + 1)(2k + 1)/6 
3) Prove that the sum is true for n
= k
+ 1, that is

1^{2}
+ 2^{2}
+ 3^{2} + . . . + (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

1^{2}
+ 2^{2}
+ 3^{2} + . . . + k^{2} + (k + 1)^{2 }=
k(k + 1)(2k + 1)/6 + (k + 1)^{2 }= (k + 1)(2k^{2
}+ 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 a_{n}
= a_{1} + (n 
1)d, 
for
the general term of an arithmetic sequence,
holds.

Solution: 1) For
n
= 1, we obtain a_{n}
= a_{1} + (1 
1)d = a_{1}, so P(1)
is
true,

2)
Assume that the formula a_{n}
= a_{1} + (n 
1) holds
for all
positive integers n
> 1, then

3)
We should prove that the formula holds
for n + 1, that is
a_{n
}_{+ 1} = a_{1} + [(n + 1) 
1]d = a_{1} + n ·
d.

Since, by assumption a_{n}
= a_{1} + (n 
1)d, and by the
definition of an arithmetic sequence a_{n
}_{+ 1} 
a_{n}
= d,

then, a_{n
}_{+ 1} = a_{n} + d = a_{1}
+ (n 
1)d + d = a_{1} + n ·
d.


Example: Prove
by
mathematical induction that the formula S_{n}
= (n/2) ·
(a_{1} +
a_{n}) for
the sum of the first n
terms of an arithmetic sequence,
holds.

Solution: 1) For
n
= 1, we obtain S_{1}
= (1/2) ·
(a_{1} +
a_{1})
= a_{1}, so P(1)
is
true,

2)
Assume that the formula S_{n}
= (n/2) ·
(a_{1} +
a_{n}) 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 a_{n}
= a_{1} ·
r ^{n}^{

1} for
the general term of a geometric sequence,
holds.

Solution: 1) For
n
= 1, we obtain a_{n}
= a_{1} ·
r ^{1}^{

1}
= a_{1}, so P(1)
is
true,

2)
Assume that the formula a_{n}
= a_{1} ·
r ^{n}^{

1} holds
for all
positive integers n
> 1, then

3)
We should prove that the formula holds
for n + 1, that is
a_{n
}_{+ 1} = a_{1} ·
r ^{(}^{n + 1)}^{

1} = a_{1} ·
r ^{n}.

Since, by assumption a_{n}
= a_{1} ·
r ^{n}^{

1}, and by the
definition of a geometric
sequence a_{n
}_{+ 1}
= a_{n} ·
r,

then, a_{n
}_{+ 1} = a_{n} ·
r = a_{1} ·
r ^{n}^{

1} ·
r = a_{1} ·
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. 