Proof by induction is a method of deductive reasoning that produces a fully rigorous mathematical proof:
Step 1 Prove that the result is true for a starting value, such as . This is called the basis case.
Step 2 Assume that the result is true for some value,
Step 3 Prove that if it is true for , it is true for .
Step 4 Conclude that the proposition is true for all positive integers.
Since we have proved the result for a general value, , then if we prove it for the next value, , we can logically conclude that it will be true for the next value, and the next, and the next, and so on ad infinitum.
Step 1: when : LHS = , RHS = . Therefore, we have proved the hypothesis for one value...
Step 2: Now let , and prove this.
Let us use the symbol to represent the series
However, also represents (which is the same series, but in a different order)
If we add the two series together, we get:
Step 3: Now let :
However, the part in italics of the above line, is already known. Thus:
When we expand the left hand side, we get:
Step 4 The left hand side of the equation is equal to the right hand side, so therefore we can conclude that, by the principle of mathematical induction, since it is true for , and since if it is true for then it is true for , it is true for any positive integer.