Exercise 2.2.5 (Strong principle of induction)

Question

Prove Proposition 2.2.14. (Hint: Define $Q(n)$ to be the property that $P(m)$ is true for all $m_0 \leq m < n$; note that $Q(n)$ is vacuously true when $n < m_0$.)\par 

	extbf{Proposition 2.2.14} Let $m_0$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m \geq m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0 \leq m' < m$, then $P(m)$ is also true. (In particular, this means that $P(m_0)$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m \geq m_0$.

Issa Rice · Accepted Answer

extbf{How to think about the exercise.} I want to say more, but I'm feeling tired after writing up the proof, so here are some quick comments, mostly intended as notes to myself for when I return to this exercise later:
\begin{itemize}
\item For this kind of exercise, I find my verbal ability to start to fail me, and I just can't keep in my mind all the nested "if ... then ..." statements and so on. The good news is that you can sort of solve these exercises entirely symbolically and automatically, while barely understanding anything.
\item I should also say something about why this is called \emph{strong} induction. (basically the hypothesis contains more assumptions, which makes the statement stronger)
\item I should give an example of a problem where using strong induction makes the proof go through but where using regular induction makes it impossible.
\item In the proof below I showed at one point that $n \geq m_0$. This is like splitting by the cases $n\geq m_0$ and $n < m_0$ (where the latter ends in contradiction so we don't need to worry about it). There is an alternative way to split by cases, which is $n{{+}\!{+}} \geq m_0$ and $n{{+}\!{+}} < m_0$. In the latter case, $Q(n{{+}\!{+}})$ is automatically true as Tao writes in the hint. In the former case, we have to further break into $n\geq m_0$ (use $Q(n) 	o P(n)$) or $n{{+}\!{+}} = m_0$ (so we want to show $Q(m_0)$, but this is vacuously true).
\item There are a lot of questions on math SE asking about this exercise. It would be nice if I can go through them in detail at some point to make sure that this post covers all of the common points of confusion.
\end{itemize}

extbf{Model solution.} Let $Q(n)$ to be the property that $P(m)$ is true for all $m_0 \leq m < n$. Given this definition of $Q$, we can restate the hypothesis for $P$ as follows: for each $m \geq m_0$, if $Q(m)$ is true then $P(m)$ is also true. To go a little more slowly, we know from the statement of \href{./exercise_2-2-5}{Proposition 2.2.14} that $P$ has the following property:
\begin{itemize}
\item For each $m \geq m_0$: if $P(m')$ is true for all $m_0 \leq m' < m$ then $P(m)$ is also true.
\item We can use $Q$ to rewrite the above bullet point as follows:
\item For each $m\geq m_0$: if $Q(m)$ is true then $P(m)$ is also true.
\end{itemize}

We will prove by induction that $Q(n)$ is true for all natural numbers $n$.\par

We first want to show $Q(0)$, which says that $P(m)$ is true for all $m_0 \leq m < 0$. This is vacuously true since there is no natural number strictly less than zero: $m <0$ means $m \leq 0$ and $m
e 0$. So we have some natural number $a$ such that $0 = m+a$, but this means $m=0$ by Corollary 2.2.9, which contradicts the fact that $m
e 0$. So $P(m)$ is true for all such numbers, because none exist.\par

Now suppose inductively that we have shown $Q(n)$ is true. We want to show that $Q(n{{+}\!{+}})$ is true, i.e. we want to show that $P(m)$ is true for all $m_0 \leq m < n{{+}\!{+}}$. So let $m$ be a natural number and suppose $m_0 \leq m < n{{+}\!{+}}$. Our goal is to show that $P(m)$ is true.\par

Since $m_0 \leq m < n{{+}\!{+}}$, we claim that either $m_0 \leq m < n$ or $m = n$. This is because $m < n{{+}\!{+}}$ implies $m{{+}\!{+}} \leq n{{+}\!{+}}$ by Proposition 2.2.12(e) which implies $m \leq n$ by Proposition 2.2.12(d). We know $m = n$ or $m 
e n$; in the latter case we thus have $m < n$, so $m_0 \leq m < n$. Thus we see that either $m_0 \leq m < n$ or $m = n$.\par

Since $Q(n)$ is true, we know that $P(m)$ is true for all $m_0 \leq m < n$. Thus in the case where $m_0 \leq m < n$, we already know that $P(m)$ is true.\par

To complete the proof we must show that $P(m)$ is true in the case $m=n$, i.e. we must show that $P(n)$ is true. Since $m_0 \leq m < n{{+}\!{+}}$, by transitivity of order $m_0 < n{{+}\!{+}}$, so $m_0{{+}\!{+}} \leq n{{+}\!{+}}$ which means $m_0 \leq n$. Since $m_0 \leq n$ we can use the hypothesis for $P$, which says that if $Q(n)$ is true then $P(n)$ is also true. Since $Q(n)$ is true by inductive hypothesis, we see that $P(n)$ is true as desired.\par

This completes the induction, and we have that $Q(n)$ is true for all natural numbers $n$. Our original goal was to show that $P(m)$ is true for all natural numbers $m \geq m_0$. So let $m \geq m_0$. Then we know that $Q(m{{+}\!{+}})$ is true. Since $m_0 \leq m < m{{+}\!{+}}$, we see that $P(m)$ is true as required.\par

Source: \href{https://issarice.com/}{Issa Rice's blog}.

Khagan Gulusoy · Answer

ewcommand{ adius}{0.6cm} \begin{figure}[H] \centering \begin{tikzpicture} % Normal induction \draw[thick, blue] (0,0) node{$P(0)$} circle (0.5cm); \draw (1.5, 0) circle ( adius); ode at (3,0) {$\ldots$}; \draw (4.5, 0) circle ( adius); \draw [thick, red] (6, 0) node{$P(n)$} circle ( adius); \draw [thick, violet](7.5, 0) node{$P(n++)$} circle (0.8cm); ode at (9,0) {$\ldots$}; \draw (10.5, 0) circle ( adius); \draw (12, 0) circle ( adius); \draw [decorate,decoration = {brace,amplitude=10pt}] (5.5,0.75) -- (6.5,0.75); \draw[->, bend left=30] (6, 1.25) to (7.5, 1); \end{tikzpicture} \caption{Normal Induction} \end{figure} \begin{figure}[H] \centering \begin{tikzpicture} % Strong induction \draw[thick, blue] (0,0) node{$P(m_0)$} circle ( adius); \draw[thick, red] (1.5, 0) node{$P(m^{\prime})$} circle ( adius); ode[red] at (3,0) {$\ldots$}; \draw[thick, red] (4.5, 0) node{$P(m^{\prime})$} circle ( adius); \draw[thick, violet] (6, 0) node{$P(m)$} circle ( adius); ode at (7.5, 0) {$\ldots$}; \draw (9, 0) circle ( adius); \draw (10.5, 0) circle ( adius); \draw [decorate,decoration = {brace,amplitude=10pt}] (-0.5,0.75) -- (5,0.75); % Draw the slightly curved arrow \draw[->, bend left=30] (2.25, 1.25) to (6, 1); %-0.5+((0.5+5)/2) \end{tikzpicture} \caption{Strong Induction} \end{figure} \begin{proof} The trick is to define $Q(n)$ to be a property that $P(m)$ is true for all $m_0 \leq m < n.$ This way, we have wrapped up $n - m_0 - 1$ properties $P(m)$ into one property $Q(n)$. This allows us to prove $Q(n)$ using induction. \begin{itemize} \item (Base case) We first verify the base case $n = m_0,$ i.e. $Q(m_0)$. In other words, we have to prove $P(m)$ is true for all $m$ such that $$m_0 \leq m < m_0.$$ But there's no natural number $m$ such that $m_0 \leq m$ and $m< m_0$ hold simultaneously (by \href{./exercise_2-2-4}{trichotomy of natural numbers}), and therefore, the base case is vacuously true. \item (Induction Hypothesis) Now suppose inductively that $Q(m)$ is true for some natural number $m$. In other words, $P(m^{\prime})$ is true for all $m_0 \leq m^{\prime} < m$. ewline Notice how induction hypothesis also implies that $P(m^{\prime})$ is also true for $m^{\prime} = m$ (because we assumed it in the theorem). \item (Induction Step) We now prove $Q(m++).$ Thus, we have to prove the following: $$P(m^{\prime}) ext{ is true for all } m_0\leq m^{\prime} < m++.$$ The statement we have to prove is equivalent to the following statement: $$P(m^{\prime}) ext{ is true for all } m_0\leq m^{\prime} \leq m.$$ $m_0\leq m^{\prime} \leq m$ means that $m_0 \leq m^{\prime}< m$ or $m^{\prime}= m,$ which is $P(m).$ If $m_0 \leq m^{\prime}< m,$ $P(m^{\prime})$ is true by induction hypothesis. If $m^{\prime}= m,$ $P(m^{\prime})$ is again true, because $P(m)$ is also true by the theorem assumption (as discussed earlier). %But this is true by extit{induction step}, and therefore, we can conclude that strong induction is true for all natural numbers. \end{itemize} Thus, we can conclude that strong induction holds for all natural numbers. \end{proof}

Exercise 2.2.5 (Strong principle of induction)

Answers

Comments

Comments

Exercise 2.2.5 (Strong principle of induction)

Answers

Comments

Comments

Add answer