Short notes on mathematics and programming

Let’s talk about the principle of mathematical induction

You can simply write programs. You can ask neural nets to write programs. You can also prove that a program works correctly. I often hear a friend’s phrase in my head: "When I program, I prove correctness. When the proof converges, the program starts working."

And LLMs are not that simple either. The strongest current Google model for solving tasks and proving theorems was trained with systems that verify proof correctness.

Simple things are often the hardest. Mathematical induction is from that family. First: why do we need it? You want to prove a statement is always true. What does "always" mean? It means true for every natural number n.

What kinds of statements?
For example: "The sum of the first n odd numbers equals n*n." Or: "If you draw n lines on a plane without much aiming, the number of regions is n * (n + 1) / 2 + 1."

Why so complicated?
Just test several values and be done, right? Unfortunately, no. For example, people say n*n + n + 41 is prime. It is tempting to believe because for 1,2,3,4,5,6 it works. 43 is prime, 47 too. But if you go farther, you find a value where it is not prime. So what do we do?

Now we are ready to formulate mathematical induction. If you can prove:

  1. Statement is true for n = 1

  2. If statement is true for n, then it is true for n + 1
    then statement is true for every n.

  3. is called the induction base.

  4. is the induction step.

Why does this make sense?
I imagine a swamp with hummocks. The hummocks are numbered 1,2,3,.... The swamp is huge, with infinitely many hummocks. We need to know whether we can hop across all of them.

Base says you can stand on hummock 1. Induction step says if you are on some hummock, you can get to the next one. Meditate on this: if it starts feeling like these two facts imply you can hop through all hummocks, then you accept induction.

More details here: Shen

And here is a joke that helps remember the principle.

Statement: "A bus can fit n people."
Base: n = 1 -> "One person fits in a bus" -> true.
Induction step: "Practice shows that no matter how full the bus is, one more person can still squeeze in" -> true.

Therefore, a bus can fit as many people as you want. A million, a billion.

#education #devTopic #junior