This is not the document you are looking for? Use the search form below to find more!

Report home > Education

Mathematical Induction

0.00 (0 votes)
Document Description
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (non-negative integers). It is done by proving that the rst statement in the in nite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.
File Details
  • Added: November, 11th 2010
  • Reads: 938
  • Downloads: 24
  • File size: 114.89kb
  • Pages: 8
  • Tags: mathematical, induction, proofs
  • content preview
Submitter
Embed Code:

Add New Comment




Related Documents

Mathematical Induction

by: circleteam123, 4 pages

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers (positive integers). It is done by proving that the first ...

How to Solve Mathematical Induction

by: tutorciecle123, 4 pages

One of the most important tasks in mathematics is to discover and characterize regular patterns or sequences. The main mathematical tool we use to prove statements about sequences is induction. ...

Induction- Division

by: Kiril, 3 pages

פתרון שאלת הוכחת התחלקות ...

Free Algebra Problem Solver

by: circleteam123, 4 pages

Mathematics is a subject that is included in every stream of education and its problems gets tougher as student moves further in his studies. That's why proper assistance in solving math problems is ...

Linear Function Definition

by: circleteam123, 4 pages

In mathematics, the concept linear algebra can be considered as a part of algebra. Linear function is a mathematical concept which deals with two different concepts that is first degree of polynomial ...

Slope Of The Tangent Line

by: tutorciecleteam, 4 pages

Slope Of The Tangent Line In today session we discuss the tangent line approximation. Before going on the main topic we discuss about slope of line or tangent slope. The trigonometrically tangent of ...

Slope Of The Tangent Line

by: tutorciecleteam, 4 pages

Slope Of The Tangent Line In today session we discuss the tangent line approximation. Before going on the main topic we discuss about slope of line or tangent slope. The trigonometrically tangent of ...

Definition Of A Function

by: circleteam123, 4 pages

A function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output. An example is the function that relates each real ...

Math Tutor Online Free

by: circleteam123, 4 pages

Hello friends once again I welcome you all to learn a new topic of mathematics in an interesting way. Today, you will learn statistics and calculus. Who will tell me what you understand by ...

8th Grade Math

by: mahesh4528, 3 pages

ntroduction to English for 8th Grade In this segment of English lesson for 8th grade Math students you will learn about interrogative sentences and its usage Lesson for 8th Grade - Interrogative .. ...

Content Preview
000.3 - Mathematical Induction
c 2010 Treasure Trove of Mathematics
Mathematical induction is a method of mathematical proof typically used to
establish that a given statement is true of all natural numbers (non-negative
integers).1 It is done by proving that the first statement in the infinite se-
quence of statements is true, and then proving that if any one statement in
the infinite sequence of statements is true, then so is the next one.
Mathematical induction should not be misconstrued as a form of inductive
reasoning, which is considered non-rigorous in mathematics. In fact, math-
ematical induction is a form of rigorous deductive reasoning.
1
Introduction
The natural numbers, N, is the set of all non-negative integers:
N = {0, 1, 2, 3, . . .}.
Very often we want to prove some mathematical statement involving every
member of N. The simplest and most common form of mathematical in-
duction proves that a statement involving a natural number n holds for all
values of n. The proof consists of two steps:
1. The basis (base case): showing that the statement holds when n is
equal to the lowest value that n is given in the question. Usually,
n = 0 or n = 1.
2. The inductive step: showing that if the statement holds for some n,
then the statement also holds when n + 1 is substituted for n.
The assumption in the inductive step that the statement holds for some
n is called the induction hypothesis (or inductive hypothesis). To perform
1This document may be freely distributed, but not altered.
1

the inductive step, one assumes the induction hypothesis and then uses this
assumption to prove the statement for n + 1.
The choice between n = 0 and n = 1 in the base case is specific to the
context of the proof: If 0 is considered a natural number, as is common in
the fields of combinatorics and mathematical logic, then n = 0. If, on the
other hand, 1 is taken as the first natural number, then the base case is
given by n = 1.
This method works by first proving the statement is true for a starting
value, and then proving that the process used to go from one value to the
next is valid. If these are both proven, then any value can be obtained by
performing the process repeatedly. It may be helpful to think of the domino
effect; if one is presented with a long row of dominoes standing on end, one
can be sure that:
1. The first domino will fall.
2. Whenever a domino falls, its next neighbor will also fall.
So it is concluded that all of the dominoes will fall, and that this fact is
inevitable. Consider the following statement:
n(n + 1)
0 + 1 + 2 + 3 + · · · + n =
(1)
2
for every n ≥ 0. Suppose that the statement happens to be true for a
particular value of n, say n = k. Then we have:
k(k + 1)
0 + 1 + 2 + 3 + · · · + k =
.
(2)
2
We want to start from here, and convince ourselves that the statement is
also true for the next value, n = k + 1. Plug k + 1 into (1),
(k + 1)(k + 2)
0 + 1 + 2 + 3 + · · · + k + (k + 1) =
.
(3)
2
Notice that the left-hand side of (3) is the same as the left-hand side of (2)
except that there is an extra k + 1 added to it. So if (2) is true, then we can
add k + 1 to both sides of it to get:
2

k(k + 1)
0 + 1 + 2 + 3 + · · · + k + (k + 1)
=
+ (k + 1)
2
k(k + 1) + 2(k + 1)
=
2
(k + 1)(k + 2)
=
2
showing that (3) is true if (2) is true. To complete the proof, we need only
confirm the base case. To do so, simply plug n = 0 into the original equation
and verify the equality.
2
Formal Definition of Induction
Let S(n) be any statement about a natural number n. If S(0) is true and,
if S(k) is true then S(k + 1) is also true, then S(n) is true for every n ∈ N.
3
Examples
1. Show that
n(n + 1)(2n + 1)
02 + 12 + 22 + · · · + n2 =
.
6
Solution. If n = 0 we have the trivial case:
02 = 0(1)(1)/6.
Assume that the equation is true for n = k:
k(k + 1)(2k + 1)
02 + 12 + · · · + k2 =
.
(4)
6
From (4), we want to show that:
(k + 1)((k + 1) + 1)(2(k + 1) + 1)
02 + 12 + · · · + k2 + (k + 1)2
=
6
(k + 1)(k + 2)(2k + 3)
=
6
Begin with (4) and add (k + 1)2 to both sides:
k(k + 1)(2k + 1)
02 + 12 + · · · + k2 + (k + 1)2 =
+ (k + 1)2
6
3

Now just rearrange to complete the proof:
k(k + 1)(2k + 1) + 6(k + 1)2
02 + 12 + · · · + (k + 1)2 =
6
(k + 1)(2k2 + k + 6k + 6)
02 + 12 + · · · + (k + 1)2
=
6
(k + 1)(k + 2)(2k + 3)
=
6
2. Let Fk be the Fibonacci numbers defined by: F0 = 0, F1 = 1, and if
k > 1, Fk = Fk−1 + Fk−2. Show that:
Fn−1Fn+1 = F 2
n + (−1)n
and that
n
F 2
i = FnFn+1
i=0
Solution. Part 1:
First check for n = 1:
F0F2 = 0 · 2 = 0 = F 2
1 + (−1)1 = 1 − 1 = 0.
If we assume it is true for n = k, we have:
Fk−1Fk+1 = F 2
k + (−1)k .
(5)
From (5), we need to show that the equality continues to hold for
n = k + 1, i.e., we need to show that if we start with (5) we can show
that:
FkFk+2 = F 2
k+1 + (−1)k+1.
Since Fk+2 = Fk + Fk+1, the equation above is equivalent to:
Fk(Fk + Fk+1) = F 2
k+1 + (−1)k+1.
or to
F 2
k + Fk Fk+1 = F 2
k+1 + (−1)k+1.
Substitute F 2 from the right-hand side of (5):
k
Fk−1Fk+1 − (−1)k + FkFk+1 = F 2
k+1 + (−1)k+1
4

or
Fk+1(Fk−1 + Fk) = F 2
k+1 + (−1)k+1 + (−1)k = F 2
k+1
or
F 2
k+1 = F 2
k+1
Part 2:
For n = 0:
0
F 2
i = F 2
0 = 0 = F0F1 = 0 · 1 = 0
i=0
If it is true for n = k:
k
F 2
i = Fk Fk+1
(6)
i=0
then we can F 2
to both sides of (6) to get:
k+1
k+1
F 2
i = Fk Fk+1 + F 2
k+1 = Fk+1(Fk + Fk+1) = Fk+1Fk+2
i=0
3. Show that:
1
1
1

1 + √ + √ + · · · + √
≤ 2 n.
2
3
n
Solution. For the n = 1 case we have

1 ≤ 2 1 = 2.
Assume the equation is true for n = k:
1
1
1

1 + √ + √ + · · · + √
≤ 2 k.
2
3
k

To show it is also true for n = k + 1, add 1/ k + 1 to both sides:
1
1
1

1
1 + √ + · · · + √ + √
≤ 2 k + √
.
2
k
k + 1
k + 1
Thus if we can show that

1

2 k + √
≤ 2 k + 1
k + 1
5


then the proof is complete. Multiply both sides by
k + 1 and then
square both sides to obtain:
4k(k + 1) + 4
k(k + 1) + 1 ≤ 4(k2 + 2k + 1).
4
k(k + 1) ≤ 4k + 3
Squaring again:
16k2 + 16k ≤ 16k2 + 24k + 9
which is always true.
4. Show that:
2! · 4! · 6! · · · (2n)! ≥ ((n + 1)!)n.
Solution. First show it is true for n = 1:
2! = 2 ≥ (2!)1 = 2.
Next assume it is true for n = k:
2! · 4! · 6! · · · (2k)! ≥ ((k + 1)!)k.
(7)
If we multiply both sides of (7) by (2(k + 1))!, we get:
2! · 4! · · · (2k)! · (2k + 2)! ≥ ((k + 1)!)k · (2k + 2)!.
If it can be shown that the right-hand side of the equation above is
larger than ((k + 2)!)k+1, the proof is complete. The term (2k + 2)! on
the right-hand side can be written:
(2k + 2)! = (2k + 2)(2k + 1)(2k) · · · (k + 3)(k + 2)!
This consists of k terms, all greater than k + 2, multiplied by (k + 2)!,
so
((k + 1)!)k(2k + 2)!
>
((k + 1)!)k(k + 2)k(k + 2)!
=
((k + 2)!)k(k + 2)! = ((k + 2)!)k+1
6

5. Show that:

π
2 +
2 +
2 + · · · +
2 = 2 cos 2n+1
where there are n 2s in the expression on the left.
Solution. For n = 1 case we have:

π


2 = 2 cos
= 2 cos π/4 = 2 2/2 =
2.
22
Now assume it is true for k nested square roots:

π
2 +
2 +
2 + · · · +
2 = 2 cos
.
2k+1
Add 2 to both sides and take the square root, so the LHS will have
k + 1 nested square roots, and the right hand side will be:
π
2 + 2 cos
.
(8)
2k+1
All we need to show is that the value above is equal to
π
2 cos
.
(9)
2k+2
We know that for any angle θ we have:
1 + cos 2θ
cos θ =
.
(10)
2
Substitute π/2k+2 for θ in 10 and the equality of 8 and 9 becomes
immediately obvious.
4
References
1. H. Amann, J. Esher, Analysis 1, Birkhauser Basel; 1st edition, 2010.
2. H. Amann, J. Esher, Analysis 2, Birkhauser Basel; 1st edition, 2008.
3. H. Amann, J. Esher, Analysis 3, Birkhauser Basel; 1st edition, 2009.
4. S. Lay, Analysis: With an Introduction to Proof, Prentice Hall; 4th
edition, 2004.
7

5. S. Hedman, A First course in Logic: An Introduction to Model The-
ory, Proof Theory, Computability, and Complexity, Oxford University
Press; 2004.
6. R. Larson, B. Edwards, Calculus, Brooks Cole; 9th edition, 2009.
7. R. Larson, R. Hostetler, B. Edwards, Calculus (With Analytic Geom-
etry), Brooks Cole; 8th edition, 2005.
8. M. Lial, J. Hornsby, D. Schneider, College Algebra, Addison Wesley;
10th edition, 2008.
9. C. Mckeague, M. Turner, Trigonometry, Brooks Cole; 6th edition,
2007.
10. M. Lial, J. Hornsby, D. Schneider, Trigonometry, Addison Wesley; 9th
edition, 2008.
11. R. Larson, Trigonometry, Brooks Cole; 8th edition, 2010.
12. R. Moyer, F. Ayres, Schaum’s Outline of Trigonometry, McGraw-Hill;
4th edition, 2008.
13. G.F. Simmons, Precalculus Mathematics in a Nutshell, Wipf & Stock
Publishers; 2003.
14. M. Sullivan, Trigonometry: A Unit Circle Approach, Prentice Hall;
8th edition, 2007.
15. R. Larson, Algebra and Trigonometry, Brooks Cole; 5th edition, 2000.
8

Document Outline

  • Introduction
  • Formal Definition of Induction
  • Examples
  • References

Download
Mathematical Induction

 

 

Your download will begin in a moment.
If it doesn't, click here to try again.

Share Mathematical Induction to:

Insert your wordpress URL:

example:

http://myblog.wordpress.com/
or
http://myblog.com/

Share Mathematical Induction as:

From:

To:

Share Mathematical Induction.

Enter two words as shown below. If you cannot read the words, click the refresh icon.

loading

Share Mathematical Induction as:

Copy html code above and paste to your web page.

loading