Mathematical Induction is a proof technique used to prove the statement in the form: Vn E N, P(n) There are two parts to a proof by induction: Basis Step: Show P(n) is true if P(1) is true Inductive Step: Show the statement Vk E N, P(k)=P(k+1) is true The idea is that if you can show a statement is true for an initial value, and you can show that if it is true for any random value k then it is also true for the next value, k+1, then that statement will be true indefinitely. Let's look at some examples: Prove: for every integer n, 1+2+3+,,,+n = n(n+1)/2
Prove: for every positive integer n, 1/(1*2)+1/(2*3) + 1/(3*4)+...+ 1/(n(n+1)) = n/(n+1)