CS 201 - 9/30/14
Why are we studying Inductive proofs?
What is the big picture??
Most Programs require an inductive proof to
be shown to be correct.
Most programs require an inductive proof to
prove/show/determine run time of the program.
Formal proofs of the above type are not part of CS 201
==================================
From Last Time
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 divisibly by 4
b[2] = 12 (given by def. of the sequence)
= 4 * 3
since 3 is an integer, b[2] is divisible by 4
Inductive Case:
Inductive Hypothesis:
Show the for all integers k >= 3 if the property
is true ( b[k] is divisible by 4 ) for all i
with 1 <= i < k, then the property is true for
all k.
"Assume true for p < k, Prove true for k."
Write out the equation for k
b[k] = b[k-2] + b[k-1]
Show b[k] is divisible by 4, we can use that
b[l] is known to be divisible by for all
1 <= l < k
b[k] = 4 * X + 4 * Y (substitute for b[k-2]
and b[k-1])
where X and Y are some
integer values
= 4 * (X + Y) by distributive law
= 4 * Z , where Z is some integer
since Integer + Integer
equals another integer
By being able to express b[k] in terms
of 4 times some integer, we prove the
b[k] is divisible by 4.
Thus, Proving the inductive case.
By the property of String mathematical Induction
we have proved that all values in the sequence
are divisible by 4.
When dealing C pointers, invalid address references
is a HUGE issue and can be extremely time consuming.
node* head;
Head is storing an address
head->elem = 5;
The above statement causes a "run-time violation"
if the address in head is not 100% correct.
Understanding a few simple debugging tips can
greatly help reduce development time.
One debugging tool is called gdb