Proofs of Universal Statements: Mathematical Induction · The Method of Mathematical Induction

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Problem. You are reviewing your friend's code and see a line in the code that calculates the sum of the first \(n\) odd numbers: \[1+3+5+\dotsb+(2n-1)\ .\] 

sum(range(1, 2 * n, 2))
You know that there is a formula for such a sum: for all positive integers \(n\), the following equality holds \[1+3+5+\dotsb+(2n-1)=n^{2}\ .\]

If you replace the sum calculation with \(n^{2}\), the code will become both more compact and efficient (for example, for \(n=10^{9}\), calculating the sum of a billion terms will take a noticeable amount of time, while \(n^{2}\) is calculated instantly). But how can you convince your friend that the formula is true for all positive integers \(n\)?

For example, it is not difficult to verify that this formula is true for all integers \(1 \le n < 1000\). 

for n in range(1, 1000):
    assert sum(range(1, 2 * n, 2)) == n ** 2

Does this prove the formula?

5 points

  1. Yes, it does.

  2. No, it does not.