1. Mathematical induction

What is the mathematical analysis for? It studies real numbers and functions. Why the mathematical analysis is worth studying? Because of two reasons. Firstly, all approximations of anything what is happening in the real world (physics, economy, mechanics, and so on) is a function on real numbers. If one wants to know anything about the phenomena taking place in the real world, to study, understand, or even simulate it, one needs to know the mathematical analysis.

Secondly, as usually studying mathematical analysis is simply practice of thinking. And the ability to think logically is important regardless of who you are: mathematician, economist or programmer.

We start with the mathematical induction. It is a powerful tool to prove things. The sentences proved by this method will not have a continuous character like the rest of calculus, will only concern for example natural numbers.

It is a very simple and yet powerful method of making conclusions. Assume we have a sequence of batteries (arranged left to right) about which we know two facts:

  • the first battery in the sequence has its minus side on the left
  • each subsequent battery is placed well in the sense it has on the left side opposite sign then the previous battery on the right side,

then immediately we can tell, that all the batteries in the sequence have minus side on the left. Obvious, isn’t it? Those two pieces of deduction are called the first and the induction steps.

More generally we are given a sentence which depends on a natural number n (in our example: n-th battery has minus side on the left) and we would like to prove that the sentence is true for any n. The mathematical induction makes it sufficient to check only the two following facts:

  • the sentence is true for n=0 (the first step)
  • the following implication holds: if the sentence is true for n=k, then it is true for n=k+1 (induction step).

Let us prove a mathematical fact using the induction. E.g. that for any natural n, the sum 0+1+2+\ldots+n equals \frac{n(n+1)}{2}. First we check the first step. Indeed for n=0 we get 0=\frac{0\cdot 1}{2}.

Next we check the induction step. Assume that the sentence is true for n=k, meaning 0+\ldots+k=\frac{k(k+1)}{2} (we will call it the induction assumption). We would like to prove the sentence for n=k+1, i.e. 0+1+\ldots+k+(k+1)=\frac{(k+1)(k+2)}{2}. Using the induction assumption:

    \[0+\ldots k+(k+1)=\frac{k(k+1)}{2}+k+1\]

Therefore:

    \[=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+2)(k+1)}{2}\]

and we are done. We have checked the induction step. Under the principle of induction we have proved that for all n, 0+1+2+\ldots+n=\frac{n(n+1)}{2}.