CS 201 - 9/9/14
fgets()
--------------
inductive proof
Sum i from 1 to n = n (n+1) / 2
First solve the base case (n = 1)
Sum of value from 1 to 1 = 1 * (1 + 1) / 2
Show the value of the Left Hand Side:
By Math. Def: Sum of 1 with nothing else is 1
(additive identity)
Show the value of the Right hand Side
1 * (1 + 1) / 2
1 * 2 / 2
2 / 2
1
Since the LHS equals the RHS the base case is
proved true.
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 is (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
(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