CS 201 - 9/11/14
inductive proof
Sum i from 1 to n = n (n+1) / 2
Proved Base Case Last Time:
Now we need to solve the inductive case:
Assume the formula is true for M
Show the formula is true for M+1
Sum of i from 1 to M+1 = (M+1) * ((M+1) + 1) / 2
1 + 2 + 3 + ... + M-1 + M + M+1 =
(1 + 2 + 3 + ... + M-1 + M) + M+1 =
(Sum of i from 1 to M) + M+1 =
Now we apply the Inductive Hypothosis
(M * (M + 1) / 2) + M+1 =
(M^2 + M) / 2 + M+1 =
M^2/2 + M/2 + 2M/2 + 2/2 =
(M^2 + 3M + 2) / 2 =
(M + 1)(M + 2) / 2 =
(M+1) * ((M+1) + 1) / 2 =
Since the LHS equals the RHS the inductive case
has been proven.
By combine the base case and the inductive case,
using the Principles of Mathematical Induction
we have shown that
Sum of i from 1 to n = n * (n+1) / 2
is true for all values of i greater than or equal
to 1
When solving an Inductive Proof,
Step 1. Understand the general formula being proved
Step 2. Understand and solve the base case
Step 3. The Inductive Case
3a. State the Inductive Hypothesis
"Assume true for M"
"Show True for M+1"
Use a different variable for the terms than
used in the original formula
3b. State the formula for the Value M+1
3c. Manipulate one side of the formula from 3b
the express a sub-portion of the that
side in terms of M and some other stuff.
3d. Apply the Inductive Hypothesis on the
portion of the side contain M
3e. Reduce/Maniplution the side of the formula
so that it (hopefully) match the other
side
4. Insert verbiage of "The principle of Mathematical
Induction" to finalize the proof.
The above idea is called Simple Induction
- where the step N relies on step N-1
- there is only one base case
Complete Induction is when the Induction Proof has at
least one of
- multiple base cases
- step N relies on some step between step N-1
and step 0
- step N relies on multiple steps between ste N-1
and step 0
Comon case requiring Complete Induction:
- formula using either even or odd values
- the Fibonacci sequence
step 0 = x (First base case)
step 1 = y (Second Base Case)
step N = (step N-1) + (step N-2)
When dealing with Complete Inductive Proofs, we
must
- solve each base case seperately
- solve each inductive step seperately