Lesson 3

The method of mathematical induction is one of the most important and frequently used methods in discrete mathematics. As the domino analogy suggests, it is a natural way of proving that something holds for all positive integers.

Note at the same time that the method of mathematical induction tells us nothing about where the statement we are proving comes from.

Indeed, we would not be able to find the formula for \(1+3+5+\dotsb+(2n-1)\) by induction, although we could prove the formula by induction after it appeared from somewhere. Where did it come from?

For this particular formula, an important technique of discrete mathematics works perfectly — look at small values of the parameter and guess: by writing out the sums \[1,\ 1+3=4,\ 1+3+5=9,\ 1+3+5+7=16,\ 1+3+5+7+9=25,\] it is not difficult to see the squares of integers.

Another standard technique is to consult Internet or LLMs. Finally, for the formula we are considering, there is also a geometric proof.