http://www.ck12.org Chapter 12. Discrete Math
12.9 Induction Proofs
Here you will learn how to prove statements about numbers using induction.
Induction is one of many methods for proving mathematical statements about numbers. The basic idea is that you
prove a statement is true for a small number like 1. This is called the base case. Then, you show that if the statement
is true for some random numberk, then it must also be true fork+1.
An induction proof is like dominoes set up in a line, where the base case starts the falling cascade of truth. Once you
have shown that in general if the statement is true forkthen it must also be true fork+1, it means that once you
show the statement is true for 1, then it must also be true for 2, and then it must also be true for 3, and then it must
also be true for 4 and so on.
What happens when you forget the base case?
Watch This
MEDIA
Click image to the left for use the URL below.
URL: http://www.ck12.org/flx/render/embeddedobject/62271http://www.youtube.com/watch?v=QHkG0d5kZvE James Sousa: Mathematical Induction
Guidance
Induction is a method of proof usually used to prove statements about positive whole numbers (the natural numbers).
Induction has three steps:
- The base case is where the statement is shown to be true for a specific number. Usually this is a small number
like 1. - The inductive hypothesis is where the statement is assumed to be true fork.
- The inductive step/proof is where you show that then the statement must be true fork+1.
These three logical pieces will show that the statement is true for every number greater than the base case.
Suppose you wanted to use induction to prove:n≥ 1 , 2 + 22 + 23 +···+ 2 n= 2 n−^1 −2.
Start with theBase Case. Show that the statement works whenn=1:
21 =2 and 2^1 +^1 − 2 = 4 − 2 =2. Therefore, 2^1 = 21 +^1 −2. (Both sides are equal to 2)
Next, state yourInductive Hypothesis. Assume that the statement works for some random numberk:
2 + 22 +···+ 2 k= 2 k+^1 −2 (You are assuming that this is a true statement)
Next, you will want to use algebra to manipulate the previous statement toprovethat the statement is also true for
k+1. So, you will be trying to show that 2+ 22 +···+ 2 k+^1 = 2 k+^1 +^1 −2. Start with the inductive hypothesis and
multiply both sides of the equation by 2. Then, do some algebra to get the equation looking like you want.