Mathematics for Programmers (1) Iterative Method and Mathematical Induction Method

Posted on Edited on In Waline:

What I want to convey is a feeling

I have always told my junior brothers and sisters that if you don’t learn the meaning of out-point philosophy, you can’t understand its principles. It only stays on the surface, what others say is what they say, and it always stays at the level of “equipment”, and you can’t draw inferences from one another.

Sometimes we can easily understand a knowledge point in depth, and sometimes we need to contact other knowledge points, you can summarize the common parts between them, that is, the principle.

The content of this blog is also like this, our junior high school math knowledge, mathematical induction. But not only mathematical induction, but also how to verify it with our usual programming and find the commonalities between the two.

This blog seems simple, but what I want to convey is a feeling, a way of thinking.

First of all, let’s talk about an example given by our math teacher when we were studying index in junior high school in order to let us understand the power of exponential explosion:

The ancient Indian king Shahan loved to play chess, and he planned to reward the inventor of chess, Prime Minister Sisar Ban Dahir. The wise minister pointed to the chess board and said to the king, "Your Majesty, I don’t want any other rewards, please put one grain of wheat in the first small cell of this chess board, two grains in the second small cell, four grains in the third small cell, and so on, each small cell is twice as much as the previous small cell until it is full

Those who have heard this story should know that if the reward is really given in this way, all the taxes in the whole of India for the next 50 years will not be enough.

How many grains of wheat do you need to fill these 64 squares? This is quite a large number, and it is not easy to calculate the result manually. If you think you are awesome, you can try to calculate with a pen. In fact, there is a corresponding method in the whole process of calculating wheat grains, which is exactly the first concept we are going to talk about today: ** Iterative Method **.

Iterative method

What exactly is the iterative method?

** Iterative method, in simple terms, is actually constantly using the old variable value to recursively calculate the new variable value. **

I may still say this in an abstract way and it is not easy to understand. Let’s go back to the story just now. The minister requires that the number of wheat in each grid is twice that of the previous grid, so the number of wheat in the previous grid is the old variable value, which we can first denote as Xn − 1; and the number of wheat in the current grid is the new variable value, which we denote as Xn. The recursive relationship between these two variables is like this: f (n) = f (n - 1) * 2

If you have a little programming experience, you should be able to find that the idea of iteration method is easily implemented through the loop language in computer language. You know, computers are inherently suitable for doing repetitive work. We can use loop statements to make the computer repeat the recursive steps in the iteration, and then deduce the final value of the variable.

I won’t put the code on how to implement it, it’s very simple.

What are the specific applications of the iterative method?

After seeing this, you may have roughly understood the core concept of iterative method. Iterative method has a wide range of applications in both mathematics and computer fields. In general, iterative method can be used in the following aspects:

  • Find the exact or approximate solution of a number. Typical methods include the bisection method and Newton’s method.

  • ** Find the target value within a certain range **. Typical methods include binary search.

  • ** Iteration in Machine Learning algorithms **. There are many related algorithms or models, such as K-means clustering, Markov chain of PageRank, layer descent, etc. The reason why iterative methods are widely used in Machine Learning is that many times the process of Machine Learning is to find a local optimal solution based on known data and certain assumptions. The iterative method can help the learning algorithm search step by step until it finds this solution.

Mathematical induction

What is mathematical induction?

We mentioned in the previous section that the rule for placing grains of wheat on the chessboard is to put one grain in the first square, two grains in the second square, and so on, and each small square has twice as many grains of wheat as the previous small square, until 64 squares are filled.

Let’s imagine that we’ve traveled to ancient India, and we’re standing next to the king, looking at this chessboard, and you find that the numbers of wheat in squares 1 to 8 are: 1, 2, 4, 8, 16, 32, 64, 128. ** At this point, the king wants to know how many grains of wheat are needed in total. **

If we follow the idea of the iterative method just now, we need to loop 64 times, calculate the number of cells per cell, and then add them up.

Can we try to find a rule that allows us to directly calculate the total number?

Can we boldly assume that the total number of grains in the first n squares is 2n − 1? If this assumption holds, then the total number of grains required to fill 64 squares is 1 + 2 + 22 + 23 + 24 +… + 263 = 264 − 1 = 18446744073709551615.

Whether this hypothesis holds or not remains to be verified. But for problems like this infinite sequence of numbers, we can usually use Mathematical Induction to prove it.

In number theory, mathematical induction is used to prove that any given situation is correct, that is, the first, second, third, and all cases are no exceptions.

General steps of mathematical induction

  • Prove whether the basic case (usually when n = 1) holds;

  • Suppose n = k − 1 holds, then prove that n = k also holds (k is any natural number greater than 1). As long as you have studied mathematics, I think you are familiar with this step. However, for now you need to keep this step in mind, and then we will use this step to prove the example at the beginning.

How to solve this problem

In order to give you a better understanding, I will divide the original proposition into two sub-propositions to prove it. The first sub-proposition is that the number of grains in the nth square is 2n − 1. The second sub-proposition is that the sum of the grains in the first n squares is 2n − 1.

First, let’s prove the first sub-proposition.

  • Basic case: We have verified that when n = 1, the number of grains in the first cell is 1, which is equal to 21 − 1. Therefore, the proposition holds for k = 1.

  • Suppose that the number of grains in the k − 1th cell is 2k − 2. Then the number of grains in the k − 1th cell is twice that of the k − 1th cell, that is, 2k − 2 ∗ 2 = 2k − 1. Therefore, if the proposition holds when k = n − 1, it also holds when k = n.

So, the first sub-proposition holds. On this basis, I will prove the second sub-proposition.

  • Basic case: We have verified that when n = 1, the total number of grains in all lattices is 1. Therefore the proposition holds for k = 1.

  • Assuming that the total number of grains in the first k − 1 cell is 2k − 1 − 1, based on the conclusion of the previous proposition, the number of grains in the kth cell is 2k − 1. Then the total number of grains in the first k cell is (2k − 1 − 1) + (2k − 1) = 2 ∗ 2k − 1 = 2k − 1.

Therefore, if the proposition holds for k = n − 1, then it also holds for k = n. Speaking of which, I have proved that both propositions are true. ** Compared with calculations using iterative methods, the biggest feature of mathematical induction is the word “induction”. It has summed up a rule. As long as we can prove that this rule is correct, there is no need for step-by-step calculations, which can save a lot of time and resources **.

The logic of recursion calls and mathematical induction is the same

I don’t know if you have found it, in fact, our mathematical induction proof process is similar to the recursion call process.

But only the process and ideas are similar, in fact, there are still subtle differences. For example, the results of our example are only related to n, which can be directly obtained, and some are not only related to n, such as the Fibonacci sequence. This kind, then you need to use the iterative method, but we can use the idea of Dynamic Programming to optimize.

Summary

Finally, let me repeat the thought I want to convey:

** A piece of knowledge, if you don’t learn the meaning of out-point philosophy, it is not considered to understand its principles, it only stays on the surface, what others say is what, it always stays at the level of “device”, and you can’t draw inferences from one case. **

Iterative method and mathematical induction are basic mathematical knowledge in our junior high school, and they are also commonly used ideas in our programming, but we may not realize it.

Computers are good at doing repetitive problems and generally encounter repetitive problems.

  • Our first reaction is to use loops, which is a very simple iterative idea.
    But we can consider whether we can use the idea of mathematical induction to summarize the results of the nth time on the basis of iteration, because generally what is solved by iteration can be solved by recursion, and the proof process of mathematical induction is the process of recursion.
  • If the ** result of the summary is only related to n, we can skip n cycles ** and get the result directly.
  • If not, we can consider using Dynamic Programming to reduce the repeated calculations in iterations.