Mathematical Induction

There are two kinds of reasoning we generally apply while solving any problem.

One is Deductive reasoning and other is Inductive reasoning. Deductive reasoning where we try to figure out fact from a pool of given data. In Inductive reasoning we make conjecture statement on future events based upon the limited data that we have in our hand.

Mathematical Induction

Mathematical induction is a technique to provide mathematical proof. Which assume for every true value of P(n), P(n+1) is also holds true. If we can prove that one base case is true, then the +1 incremented case will also be true.

This hold for all-natural numbers.

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).

— Concrete Mathematics,

The method of induction requires two cases to be proved. The first case, called the base case proves that the property holds for the number 0. The second case, called the induction step, proves that, if the property holds for one natural number n, then it holds for the next natural number n+1. The base step not necessarily needed to be start from 0.

Studying Mathematical Induction has great relevance in Computer Science especially you can extend its proof to be used in Recursive programs.