Principle of induction variant

36 Views Asked by At

Let $a\leq b$ be two natural numbers. Let $P(n)$ be some statement involving $n$. Does the formula $$P(b)\ \land\ (\forall n)(a\leq n<b\ \land\ (\forall m)(n<m\implies P(m))\implies P(n))$$ imply $$(\forall n)(n\in[a,b]\implies P(n))?$$

2

There are 2 best solutions below

0
On

Hint: put $Q(n) \equiv P(b - n) \lor n > b - a$ and apply what is called course of values, or complete or strong induction to $Q(n)$.

0
On

In $P(b)\ \land\ (\forall n)(a\leq n<b\ \land\ (\forall m)(n<m\implies P(m))\implies P(n)) $ you have $(\forall m)(n<m\implies P(m)) $.

This implies unbounded $m$.

Do you mean $(\forall m)(n>m\implies P(m)) $?