Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers.
Proof by induction is done in two steps.
From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers. Mathematical induction, in some form, is the foundation of all correctness proofs for computer programs.
The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:
The hypothesis in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.
Whether n = 0 or n = 1 depends on the definition of the natural numbers. If 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic, the base case is given by n = 0. If, on the other hand, 1 is taken as the first natural number, then the base case is given by n = 1.
1) Prove 1+2+...+n=n(n+1)/2 using a proof by induction
Basis: Let n=1: 1 = 1( 1+1)/2 = 1(2)/2 = 1 is true,
Induction Hypothesis: Assume n=k holds: 1+2+...+k=k(k+1)/2
Show n=k+1 holds: 1+2+...+k+(k+1)=(k+1)((k+1)+1)/2 I just substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.
Induction Step: Now I start with the left side of the equation I want to show and proceed using the induction hypothesis and algebra to reach the right side of the equation. 1+2+...+(k+1)=1+2+...+k+(k+1)
=k(k+1)/2 + (k+1) by the Induction Hypothesis
=(k(k+1)+2(k+1))/2 by 2/2=1 and distridution of division over addition
=(k+2)(k+1)/2 by distribution of multiplication over addition
=(k+1)(k+2)/2 by commutativity of multiplication (this is the answer we wanted from the hypothesis)