Proofs of Universal Statements: Mathematical Induction · Strengthening the Statement

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Before proving, let's see if this sum is indeed less than one—at least for \(n=500\).

from itertools import accumulate
import matplotlib.pyplot as plt

plt.plot([*accumulate(1 / (i * (i + 1)) for i in range(1, 500))])
plt.savefig('inverse_squares.png')

It is evident that as \(n\) grows, the sum approaches one. We cannot simply prove the required statement by induction: if we only know that a certain number is less than one, it might still become greater than one after adding the next term. To prove that this cannot happen, we need to know by how much our number is less than one. This is exactly what needs to be “embedded” in the strengthened statement. For example, we can prove that the sum will be no more than \(1-1/(n+1)\). Then the step will be easily proven.

For the curious 🤓

In fact, the sum we need is even equal to \(1-1/(n+1)\): experienced people will quickly notice this by understanding that each term should be rewritten as \(1/i-1/(i+1)\), after which almost everything cancels out (or, as it is sometimes said, telescopes).