(Note: This discussion assumes that you have already studied Sections 3.2 - 3.4 of Rosen, with emphasis on 3.2. I am assuming that you already know the two parts needed for an inductive proof [Basis step and Induction step], and that you know what the inductive hypothesis is [that a given formula holds for some n].)
There is no one single algorithm which will always work for inductive proofs. (See Practice Problems 4 for some different examples.) But as with any other problem, there are some general ways of organizing your work that improve your chances of finding a correct solution. Work plenty of problems...the only way to develop a sufficiently large 'bag of tricks' is practice.
Step 1. Figure out what your function is. In many problems, this will be given to you explicitly. However, in practical applications, finding a general expression as a function of n may be the biggest challenge of the entire problem.
Step 1a. Find a base case. This will generally be n = 0 or n = 1. However, depending on the problem, it may be something else. Verify that the function is valid for your base case. Simply generating the next few cases may help you understand the function better, but is worthless in completing the proof. Repeat after me: An example is not a proof. Also, note that if your formula doesn't work for your base case, and you have chosen the correct base case, you're done; you've found a counterexample, so you're being asked to prove something that's not true. For example: Prove n2 is odd for all n > 0. n = 2 is a counterexample, so this must be false. Just make sure you've chosen the correct base case. If something is being asserted as true for all n > 5, for example, your base case will be 6. It doesn't matter if it's not true for n = 3, because you're not interested in any cases except n > 5.
Step 2. Find some different ways of expressing your function. The idea is to generate as many starting points as possible. This shouldn't take loads of time, and for some simple expressions, there may not be any obvious convenient rearrangements. (Other rearrangements always exist...in theory...but it's not worth spending hours trying to find them.) For example, suppose S(n) = n2 - 1. One rearrangment that comes to mind immediately is S(n) = (n + 1) (n - 1). Write that down as well; it may come in handy.
Step 3. Figure out your goal. In inductive proofs, this will almost always be your original expression, with every occurence of n replaced by (n+1).
Step 4. Write down your goal in as many ways as you can find.
Make a game of it:
S(n) = n2 - 1 = (n + 1) (n - 1)
a. S(n + 1) = (n + 1)2 - 1
b.
= n2 + 2n + 1 - 1
c.
= n2 + 2n
d.
= n (n + 2)
e. S(n+ 1) = (n + 1 + 1) (n + 1 - 1) = (n + 2) (n)
Without trying particularly hard, we've found five different ways of expressing S(n + 1).
Why bother doing this? Because we're going to be doing some algebraic manipulation, and we don't know in advance which expression for S(n+1) we're going to need. The more starting points and goals you can generate, the greater your chances of finding a path from one to the other.
Step 5: Find an expression for f(n+1) based on the function for f(n). In general, you will want to take your expression for f(n) and add the (n+1) term. For example, the sum of the first (n + 1) integers is the sum of the first (n) integers, plus (n + 1). (n + 1)! = (n + 1) * n!. The sum of the first (k + 1) odd integers is the sum of the first (k) odd integers, plus ( 2(k+1) + 1). And so on and so forth. Now we come to the hard part......
Step 6. Show algebraically that the formula you obtained in step 5 can be converted into one of the forms you found in step 4. When you have done so, you have demonstrated that the validity of the formula for n implies its validity for (n + 1), and therefore for all integers greater than your base case.
Let's work through an example to see how it's done.
PROVE: The sum of the first n positive integers is (n2 + n) / 2.
STEP 1. Our function is F(n) = (n2 + n) / 2.
STEP 1a (BASIS STEP). We are working with positive integers, so our base case is n = 1. The sum of the first 1 integer is 1, and 1 = (1 + 1) / 2. We have found a valid base case.
STEP 2. (n2 + n) / 2 = n(n+1)/2 = (n/2) * (n+1) = (n/2 + 1/2) * n. We decide (somewhat arbitrarily) that other ways of rewriting the equation are probably going to be a little complicated, so we won't bother unless it looks like we really need to.
STEP 3. Goal: Our goal is our original expression, with every n replaced
by n+1:
(n + 1)2 + (n+1)
F(n+1) = ---------------------
2
STEP 4: Rewrite the formula from 3 in several different ways:
F(n+1) = [ (n + 1)2 + (n+1) ] / 2
= (n+1) (n+1 + 1)/2
= (n+1)(n+2)/2
= (n2 + 3n + 2)/2
= [(n+1)/2] * (n+1+1)
All of these are simply different ways of writing the same thing. But
we don't know which form is going to come up in steps 5 and 6; we want
to be able to recognize any form we come across.
STEP 5: The sum of the first (n + 1) integers is the sum of the first
n integers, plus the n + 1 term:
F(n + 1) = F(n) + n+ 1
= [ (n2 + n) / 2 ] + n + 1
We are now ready (finally!) to carry out the inductive step of our proof. We have our starting point from step 5, and we established our goal in steps 3 and 4.
STEP 6. Show that the expression obtained in step 5 is equivalent to one of the expressions from step 4.
F( n + 1) = [ (n2 + n) / 2 ] + n + 1
= [ (n2 + n) / 2 ] + (2n + 2)/2
// Multiply (n+1) by 2/2 to establish a common denominator
= (n2 + n + 2n + 2) / 2
// Combine terms that share a denominator
= (n2 + 3n + 2) / 2
// Combine like terms
= (n + 1)(n + 2) / 2
// Q.E.D.
= (n + 1) (n + 1 + 1) / 2
We formally present the proof as something like this:
------------------------------------
Pf.
The proof is by induction on n.
BASIS STEP: For the base case of n = 1, the sum = 1 = (1 + 1)/2 = (12
+ 1)/2
INDUCTION: Assume the relation holds for some n; that is, that the
sum of the first n positive integers = (n2 + n) / 2.
Then
F( n + 1) = F(n) + n + 1
= [ (n2 + n) / 2 ] + n + 1
= [ (n2 + n) / 2 ] + (2n + 2)/2
= (n2 + n + 2n + 2) / 2
= (n2 + 3n + 2) / 2
= (n + 1)(n + 2) / 2
Q.E.D.
------------------------------------
What have we proven? We have proven that the relationship holds for
the base case of n = 1, and that in general, if it is true for some integer
n, it is also true for n + 1. Thus, because it is true for 1, it is true
for 2; because it is true for 2, it must be true for 3; and so on. It must
be true for any integer greater than 1.
This page copyleft 1999 Brian K.Hare