CS 201 - 10/7/14
int x;
int y;
char maze[22][22];
scanf ("%d", &x);
scanf ("%d", &y);
while ( x != 1 || y != 1)
{
// process input
if (x and y are valid)
maze [x][y] = '*';
scanf ("%d", &x);
scanf ("%d", &y);
}
If we are reading from standard input, we can use
redirection to read from a file.
Assume we have a program compiled into a file
called proj2.exe
At a command prompt, type:
proj2.exe < filename.txt
Homework 1 Due Today
Quiz 1 on Thursday
1. Difference between when a simple inductive
proof versus a strong inductive proof is
needed.
2. Simple inductive proof from the homework
3. Simple inductive proof that is new
Show that 1/(1*2) + 1/(2*3) + ... + 1/(n*(n+1)) = n/(n+1)
for all integers n>= 1
Base Case n = 1
Show Sum of: 1/(1*2) + 1/(2*3) + ... + 1/(n*(n+1)) = n/(n+1)
for n = 1
(LHS) Sum of 1 term: 1/ (1*2) = 1/2
(RHS) Show the formula is true
n/(n+1) for n =1
1/(1+1)
1/2
Since, LHS and RHS are equal ==> base case is proven
Inductive Case:
Inductive Hypothosis:
Prove true for M+1, assuming true for M
Show that
1/(1*2) + 1/(2*3) + ... + 1/((M+1)*(M+1+1))
= (M+1)/(M+1+1)
Expand the Summation (LHS) to show more steps
[ 1/(1*2) + 1/(2*3) + ... + 1/((M)*(M+1)) ] + 1/((M+1)*(M+1+1))
Apply the Inductive Hypothosis, replace the
portion in the [ ] with the result of the
formula for M
[ (M)/(M+1) ] + 1/((M+1)*(M+1+1))
Work the math for get to: (M+1)/(M+1+1)
M/(M+1) + 1 / ((M+1)*(M+1+1))
M*(M+2)/(M+1)(M+2) + 1/(M+1)(M+2)
( M*(M+2) + 1) / (M+1)(M+2)
( M^2 + 2M + 1) / (M+1)(M+2)
(M + 1 )(M + 1 ) / (M+1)(M+2)
(M+1)/(M+2)
(M+1) / (M+1+1)
Since LHS equals RHS of original equation ==>
Inductive case is proved.
Since both base and inductive cases are proved,
by Principle of MI, this proves for all N