What is proof by induction and how do I employ it?
Proof by induction is a type of proof in which one tries to proof a statement is valid for any arbitrary number of n by first proving for k and then trying to further extrapolate this into a valid statement for k+1. An induction proof can be clearly structured in the following elements: The Statement, Checking validity for the base case, Assuming true for n=k, Proof for n = k+1, and finally the conclusion. I will illustrate this with an example: Use Induction to prove the statement: 1+2+3+...+n = (n*(n+1))/2 where n is a positive integer. This will be the statement itself : S(n): 1+2+3+...+n = (n*(n+1))/2. The base case will be where n=1 as n is a positive integer and 1 is the smallest number satisfying this condition. Thus one shows that in fact S(1): 1=(1*(1+1))/2 --> 1=1 as we can substitute 1=k; we can now assume the statement to be true for k: S(k):1+2+3+...+k = (k*(k+1))/2. If we now manage to prove this statement to be true for n = k+1, we prove the validity of the statement for n being positive integers. This is because we proved the statement to be true for the base case thus we know it is true for n=1 as we can substitute 1 for k we can assume the statement to be valid for n=k then if we prove the statement for n = k+1 we automatically proved the statement for n = 2, but now we can assume k=2 and the statement proves itself for all positive integers. To continue with the proof: S(k+1): 1+2+3+...+(k+1) (=) ((k+1)((k+1)+1))/2 --> 1+2+3+...+k+(k+1) (=) ((k+1)((k+2))/2 . This is where the inductive step takes place: as we know the bold part to be equivalent to (k*(k+1))/2, we can rewrite the expression as (k*(k+1))/2+(k+1) (=) ((k+1)((k+2))/2 --> 0.5(k(k+1) + 2*(k+1) (=) 0.5((k+1)*((k+2)). Now we distribute and simplify: 0.5(k2+k + 2k+2) (=) 0.5(k2+2k+k+2) --> 0.5(k2+3k+2) = 0.5(k2+3k+2) now we proved the statement to be true for k+1 and thus only need the conclusion to finish our proof: The Statement S(n) was proven correct for S(1), whilst S(k) was assumed to be true S(k+1) was proven correct. Thus the statement holds true for all positive integers.
