Xrfgtjtk

-4 $begingroup$ The following is from How to Prove It: A Structured Approach, 2nd edition, by Daniel J. Velleman, page 289. To see why strong induction works, it might help if we first review briefly why ordinary induction works. Recall that a proof by ordinary induction enables us to go through all the natural numbers in order and see that each of them has some property $P$ . The base case gets the process started, and the induction step shows that the process can always be continued from one number to the next. But note that in this process, by the time we check that some natural number $n$ has the property $P$ , we've already checked that all smaller numbers have the property. In other words, we already know that $∀k < nP(k)$ . The idea behind strong induction is that we should