CS 201 - 10/6/14
Thursday 10/9/14
Quiz on inductive proof(s)
- solve an simple inductive proof (maybe solve two)
- question or two on when a strong inductive proof
might be needed.
- when more than 1 base case is needed
we must do a strong inductive proof
- when the inductive case only relies on the
previous value in the sequeunce
(given M is true, prove M+1), we can use
the simple inductive proof. Otherwise,
we must use the strong inductive proof.
Prove the following using Strong Mathematical Induction:
Suppose that a sequence is defined as:
g[0] = 12
g[1] = 29
g[k] = 5*g[k-1] - 6*g[k-2] for all integers k>=2
Prove that g[n] = 5*(3^n) + 7*(2^n)
for all integers n>= 0
First part prove the 2 base cases (when n = 0, n = 1):
Base Case: n = 1
g[0] = 5*3^n + 7*2^n
= 5*3^0 + 7*2^0
.... finish rest for base cases on your own
Inductive Case:
Inductive Hypothesis:
{
Assume true for values of n >= 0 and n < k,
Show true for k.
}
Show that g[k] = 5*3^k + 7*2^k
By the sequence definition
5*g[k-1] - 6*g[k-2] = 5*3^k + 7*2^k
Apply the Inductive Hypothesis
5*(5*3^(k-1) + 7*2^(k-1)) - 6(5*3^(k-2) + 7*2^(k-2)) =
... work the equation until we get ....
5*3^k + 7*2^k =