CS 201 - 9/29/14
Inductive Proofs
Weak Inductive Proof
Wording of Inductive Hypothosis:
Assume the statement is true for a value of N,
Prove for a value of N+1
Wording for Strong Inductive Proof (Epp Text):
"Show that for all integers k>S if the property is
true for all i with S <= i < k, then prove it
is true for k."
"Assume true for p < M, Prove true for M"
=========================
Given the sequence, c:
c[0] = 2
c[1] = 2
c[2] = 6
c[k] = 3 * c[k-3] for all integers k>=3
Prove c[n] is even for all integers n >= 0
Even integers can be represented as 2 * I
for some integer I
If an integer X that can be expressed as 2 * Y
for some integer Y, then X is even.
Base Cases: n = 0, n = 1, n = 2
c[0] = 2 = 2 * 1, since 1 is an integer C[0] is even
c[1] = 2 = 2 * 1, since 1 is an integer C[1] is even
c[2] = 6 = 2 * 3, since 3 is an integer C[2] is even
Inductive Hypothosis:
Assume true for all p < M, Prove true for M
where p >= 0 and where M >= 3
C[M] = 3 * C[M-3]
By applying then IH (Inductive Hypothesis),
we can replace C[M-3] in the above expression
This tells us the C[M-3] is even which
can be express as 2 * I for some integer I
C[M] = 3 * 2 * I
C[m] = 2 * 3 * I by Communative Prop of *
C[M] = 2 * J by the laws of Mulp on Integers
J is an Integer
Since C[M] is expressed a 2 * some Integer,
c[M] is even.
====================================
Given the sequence b
b[1] = 4
b[2] = 12
b[k] = b[k-2] + b[k-1] for all integers k >= 3
Prove that b[N] is divisible by 4
for all integers N >= 1
A number that is divisible by 4 can be expressed
as 4 * I for some integer value I
Base Cases: n = 1, n = 2
b[1] = 4 (by definition of the sequence, i.e it was given)
= 4 * 1
since 1 is an integer, b[1] is even