MA375: Lecture Notes
Spring 2010, Prof. Walther
1/12/10 Induction
Definition of Induction Induction is a way to prove a statement that defines a rule for a series of equations. Usually, it is going to be used if what your proving requires you to "prove for all numbers." For example, we would use it to prove an equation for the sum of a series for any given n.
How to do it To complete a proof by induction you need to prove 2 things.
First you need to prove the "base case." This is probably going to be checking that the first value in your series is equal to your equation. Almost always, you'll be plugging and chugging 1 or 0 into what you were given and what we are trying to prove it's equal to.
Next, you need to assume that the n (just a variable that could represent any number) case is true, and prove that the n+1 case is true. (To make typing/reading shorter we will call this "The Crank")
Let's examine how this works by assuming we've proved the 2 things we need to prove. We have already proved the first case by just plugging it in and seeing that the rule works. Now since we know if the "n"th case works we know the "n+1"th case works and the 1st case works, by combining these facts we then know the 2nd case works. So we combine the crank fact with the fact we know the 2nd case works, and we know the 3rd case works. By continually adding "the crank fact" we know that every value above the first case works and therefore every case works.
Example Problem To prove: The sum of all integers from 0 to n = n * (n + 1)/2 AKA: 0 + 1 + 2 + 3 + 4...+ n-1 + n = n * (n + 1) / 2
1st We need to prove the base case.
The sum of all integers 0 to 0 = 0.
Plug 0 into the formula: 0 * (0 + 1)/2 = 0
0 = 0, so the base case has been proven.
Next, Assume sum of all integers from 0 to n (which I'm going to give the variable Sn) = n * (n+1)/2.
Prove: sum of all integers from 0 to n+1 (which I'm going to call Sn+1) = (n+1) * (n+1 +1)/2 = (n+1) * (n+2)/2
Sn = 0 + 1 + 2 + 3...+ n-1 + n
Sn+1 = 0 + 1 + 2 + 3...+n-1 + n + n+1
^From these equations, we can see that Sn+1 = Sn + n+1
Now we have 2 facts that we know are true,
Sn = n*(n+1)/2
Sn+1 = Sn + n+1
So, we substitute Sn into equation 2 to get:
Sn+1 = n*(n+1)/2 + n+1
Now we manipulate the equation with algebra:
Sn+1 = [n*(n+1) + 2(n+1)]/2
=(n+2)*(n+1)/2
which is what we were trying to prove.
A brief statement about finding formulas
Obviously, we will not always be given a formula to prove and have to find a formula ourselves for a given situation. So, knowing some tips to find formulas will be helpful.
Let's consider the problem: Find an equation for the sum of the numbers in any row of Pascal's Triangle and prove it.
Pascal's Triangle:
Row1 1
Row2 1 1
Row3 1 2 1
Row4 1 3 3 1
Row5 1 4 6 4 1
Row6 1 5 10 10 5 1
ect.
elements in pascals triangle are found by adding the 2 elements above it together.
One useful tool, is to make a table:
Row: 1 | 2 | 3 | 4 | 5 | 6
Sum: 1 | 2 | 4 | 8 | 16| 32
From the table, it's pretty clear that sum = 2 ^ (row-1). From there it's just proving it.
First the base case: Row 1's sum = 1.
2 ^ (1-1) = 2 ^ 0 = 1
Assume: sum(n) = 2 ^ (n-1)
Prove: sum(n+1) = 2 ^ n
Now, let's look at row 4: 1 3 3 1. The sum(4) = 1 + 3 + 3 + 1
To form row 5, we add the 2 numbers above it from row 4. So, row 5 = (0+1) (1+3) (3+3) (3+1) (1+0)
So, sum(5) = (0+1) + (1+3) + (3+3) + (3+1) + (1+0), manipulating it with algebra we can get:
sum(5) = 0 + (1+1) + (3+3) + (3+3) + (1+1) + 0, sum(5) = 2*(1 + 3 + 3 + 1), which if we look at sum(4) above, we can see: sum(5) = 2*sum(4)
This of course, works for any n. So, sum(n+1) = 2 * sum(n)
Back to the problem at hand, here's what we know (or assumed)
sum(n) = 2^(n-1)
sum(n+1) = 2 * sum(n)
By substituting the first equation into the second equation, we get:
sum(n+1) = 2 * (2^(n-1)), which by algebra is the same as:
sum(n+1) = 2^n. Which is what we were trying to prove.
