What is mathematical induction and how does it work?
Mathematical induction is a method of proving if a mathematical statement is true for all natural numbers. To start with, I am going to give an analogical example in order to have a better understanding. Imagine a person that has never walked but knows how to. How can we prove that he can walk an entire mile in one go? This is simple: that person must take the first step and be able to progress onto the next one. Then, we just need him to repeat the same exact process as many times as it takes to reach a mile. As he proved to be able to execute the repetition, it is just a matter of time for him to reach his goal, but he can do it!
Mathematically, once we have an expression that we want to prove, we have to tell if it is true for a chosen natural number (1, 2, 3... whatever). Only if this is true, we will assume that it is true for all natural numbers (true for n=k), if it was not, the expression would be false. Then, if it is true for n=k, it should be true for n=k+1. If this last part is true, then the expression is proved to be true for n.
Now, here is a numerical example:
I want to know whether:
1+3+5+...+(2n-1)=n2 is true or not.
1) Is it true for e.g. n=2?
1+(2x2-1)=22 is true
2) Only then we assume
1+3+...+(2k-1)=k2 is true.
3) If it is true for n=k, it should be true for n=k+1:
1+3+...+(2k-1)+(2(k+1)-1)=(k+1)2
Seeing the previous equation, we know that:
1+3+5+...+(2k-1)=k2
Then if we do the substitution we obtain:
k2+(2(k+1)-1)=(k+1)2
If we solve it:
k2+2k+1=k2+2k+1 which is the proof for the expression to be true for all natural numbers.
