How does mathematical induction actually work?
After surfing on the internet for a while, I found the following analogy. Consider rectangular tiles (dominoes) stacked on beside the other. When we force the first tile to fall, the others begin to fall. To actually know if all the tiles have fallen, we need to know the following-
- If the first tile has fallen or not. (If not, non of them have fallen)
- If the first tile has fallen, then we can pick some random tile from the stack to check if that has fallen. If this tile has fallen, then the previous tile must have also fallen.
- From this, we can conclude that all the tiles have fallen.
But I don't understand how this idea of induction works with numbers?
If you just look at the definition, it may be hard to know. But if you really try it, it is easy to get it.
Let there is a statement $S\left(x\right)$, what induction works is:
$1)$ $S\left(1\right)$ is true
$2)$ If $S\left(k\right)$ is true, then $S\left(k+1\right)$ is true
Then, for all natural numbers $k$, $S\left(k\right)$ is true.
So we try to know the reason. Firstly, $S\left(1\right)$ is true from the first statement, then by the second statement, $S\left(2\right)$ is also true. Then also by the second statement, $S\left(3\right)$ is true. After that, you'll find that $S\left(4\right),S\left(5\right),S\left(6\right),\dots$ is also true. That's why induction works.