CS 201 - 9/25/14
Late Policy for Programming Projects
1 day 10% penalty
2 days 20% penalty
3 days 40% penalty
4 days 80% penalty
5 days 100+% penalty
Inductive Proofs.
Sum of i*(i+1) from i=1 to n-1 is n(n-1)(n+1) /3
for all n >= 2
Base Case: n = 2
Left Side Expression
Sum of i*(i+1) from 1 to 1
1*(1+1)
1 * 2
2
Right Side Expression
n(n-1)(n+1) / 3 replace 2 for n
2*(2-1)*(2+1) /3
(2* 1 * 3 ) / 3
6 / 3
2
Since LHS equal RHS for Base Case, Base Case is proven
Inductive Case
Assume true for M, Prove True for M+1
Show Sum of i*(i+1) from i=1 to n-1 is n(n-1)(n+1) /3
for all n = M+1
Left Hand Side
Sum of i*(i+1) from i=1 to M+1-1
Right hand Side
M+1(M+1-1)(M+1+1) /3
Work the LHS so it equals the RHS
Sum of i*(i+1) from i=1 to M+1-1
Express this in terms of M and M+1
First expand into series form
[1*(1+1) + 2*(2+1) + 3*(3+1) + ... +
(M-1)*(M-1+1)] + (M)*(M+1)
Then compress part of the series to express in
terms of M
[Sum of i*(i+1) from i=1 to M-1] + (M)*(M+1)
Apply the inductive Statement on the M portion
[M(M-1)(M+1) /3] + (M)*(M+1)
(M^2-M)(M+1) / 3 + (M)(M+1)
(M^3 + M^2 - M^2 - M)/3 + M^2 + M
M^3/3 - M/3 + 3M^2/3 + 3M/3
(M^3 - M + 3M^2 + 3M) / 3
(M^3 + 3M^2 + 2M) / 3
M (M^2 + 3M + 2) / 3
M (M + 1)(M + 2) /3
(M + 1 )(M)(M + 2) /3
(M+1)(M+1-1)(M+1+1) /3
The above equal the Right hand Side of
M+1(M+1-1)(M+1+1) /3
Since the LHS equals the RHS, we have proved the
inductive case
By proving both the Base Case and the Inductive Case
and appling the Principle of Mathematical Induction
we have proved the original claim.
Strong Inductive Proofs have either(or both)
multiple base cases
or
inductive steps not relying on the immediate previous
value
Consider the following sequence
C0 = 2
C1 = 2
C2 = 6
CK = 3 * C(k-3) FOR ALL INT k >= 3
2 2 6 6 6 18 18 18 54 54 54 ....
Prove that CN is even for all n > 1
We have 3 Base Case n = 2, 3, 4
C2 = 6
C3 = 6
C4 = 6
An integer is even if that integer can be expressed
as 2k where K is also and integer
The value of 6 can be expressed as 2*3.
Since 3 is an integer, 6 is even.
Induction Case
Show that Ck is even when k > 4
show that Ck can be express as 2 * I
where I is some integer