What is mathematical induction:
Mathematical induction is a method of proving that a statement is true for all natural numbers. In the context of computer science, it can be used to prove that a recursive or incremental insertion algorithm is correct.Recursive or incremental algorithms can fall into two types of mathematical formulae:
- Arithmetic Progression - Difference between the sequence of numbers is constant. For example the sequence 2,4,6,8,10 (The difference between each number in the sequence is 2).
- Geometric Series - The ratio between the terms is constant or that each term is found by multiplying the previous by some constant.. For example the following sequence 2,4,8,16,32 (The sequence has a factor of 2 between each number)
