Prove that $P(n)$ can be proven by strong induction if and only if it can be proven by regular induction.

Question

If $P(n)$ can be proven by strong induction, I know we can strengthen the inductive hypothesis to prove it by regular induction, right? But how would I do this?

Answer 1

To prove $P(n)$ by strong induction, define a new predicate $\widetilde{P}(n)$ by: \begin{eqnarray} \widetilde{P}(0) &=& P(0)\\ \widetilde{P}(n + 1) &=& \widetilde{P}(n) \wedge P(n + 1) \qquad n \ge 1 \end{eqnarray} and prove $\widetilde{P}(n)$ by regular induction.