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
