Lesson 3

At the first glance, this may seem counterintuitive, but sometimes to prove a statement by induction, it needs to be strengthened first. A natural question arises: “How can this be? If we cannot prove the statement itself, why would we be able to prove a stronger statement?” The explanation is that this allows us to use a stronger induction hypothesis in the proof.

Let's provide a clear example. Suppose we are proving that, for any integer \(n \ge 1\), the sum \(1+3+5+\dotsb+(2n-1)\) is a perfect square. In this form, the statement cannot be proven by induction. To make the proof work, we first strengthen it to: “the sum equals \(n^{2}\)” (and not just the square of some integer).