A proof by induction is the powerful and important technique for proving theorems, in which every step must be justified.

For each positive integer n, let P(n) be a mathematical statement that depends on n. Assume we wish to prove that P(n) is true for all positive integers n.A proof by induction of such a statement is carried out as follows:

Basis: Prove that P(1) is true.

Induction Step: Prove that for all n ≥ 1, the following holds: If P(n) is true, then P(n+1) is also true.

In the induction step, we choose an arbitrary integer n ≥ 1 and assume that P(n) is true; this is called the induction hypothesis. Then we prove that P(n+1) is also true.

Theorem 1: For all positive integers n, we have 1 + 2 + 3 + ….+ n = n(n+1)/2.

Proof: We start with the basis of the induction. If n = 1, then the left-hand side is equal to 1, and so is the right-hand side. So the theorem is true for n = 1.

For induction step, let n ≥ 1 and assume that the theorem is true for n, i.e., assume that 1 + 2 + 3 + …. +n =  n (n + 1) / 2

So what induction is saying , it should be true for n + 1 which means:

1 + 2 + 3 + …. + (n + 1)  = (n + 1)((n+1) + 1) / 2 , where n replaced with (n  + 1), by the induction hypothesis

this implies to

1 + 2 + 3 + …. + n + 1 = (n + 1) (n + 2) /2 , so we will prove this and it will proved the theorem.

Now takes L. H .S

=> 1 + 2 + 3 + ….. +  (n + 1) = 1 + 2 + 3 + ….. + n + n + 1 , (n + 1 comes after n)

we know 1 + 2 + 3 + …. + n = n(n+1)/2

=> n(n+1)/2 + (n + 1)

=> (n2 + n + 2n + 2)  / 2

=> (n(n + 1) + 2(n+1)) / 2  , by distribution of division over addition (or factorization)

=> (n + 1) (n + 2) / 2 = R.H.S

Also Read: Pigeon Hole Principle Mathematical Preliminaries Part 3