1

I was solving this problem in Terence Tao's book about analysis and i got stuck trying to prove this by mathematical induction.

2.2.5 -> Prove the following proposition:

(Strong principle of induction) 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' \leq m$, then $P(m)$ is also true. Then we can conclude that $P(m)$ is true for all natural numbers $m \geq m_0$.

He gives the hint to define $Q(n)$ to be the property that $P(m)$ is true for all $m_0 \leq m \leq n$

I begun doing a induction on $n$ with $m_0$ as a base case, but when i got to prove that given that $Q(k)$ implies $P(k)$ then to prove that $ Q(k+\!\!+)$ implies $P(k+\!\!+)$ i got stuck. The $+\!\!+$ is the increment operator that is basicaly a succesor function.

Felipe Dilho
  • 167
  • Related: https://math.stackexchange.com/questions/984910/prove-weak-induction-implies-strong-induction ; https://math.stackexchange.com/questions/2374467/how-to-complete-proof-of-strong-induction-from-weak-induction/2375066#2375066 – Bram28 Sep 25 '17 at 19:56

1 Answers1

0

(I). You have a mis-statement in the sentence "Suppose that for each $m>m_0,$...." where you should have written $m_0\leq m'<m$ rather than $m_0\leq m'\leq m.$

(II). Suppose (by method of contradiction) that $\neg P(m)$ for some $m>m_0.$ Let $m_1$ be the least $m>m_0$ such that $\neg P(m).$ Then $$(1).\quad \neg P(m_1)$$ and also $$(2).\quad\forall m'\; (m_0\leq m'<m_1\implies P(m')\;).$$ But the hypothesis is that $(2)\implies P(m_1),$ so we have a contradiction.

DanielWainfleet
  • 57,985