Formal definition of Mathematical Induction & Strong Induction

Question

I have been reading some notes on Induction and Strong Induction and fully understand how they work. However I was interested in a formal/mathematical way of expressing their definition and was wondering if it is correct!

For regular induction I have in my notes:

let $p(n)$ be a proposition such that: $p(1)$ holds and for all $n \in N$, $p(n)$ $\implies p(n+1)$. Then $p(n+1)$ holdes for all $n \in N$.

Is this correct? I understand induction but I feel like this definition is wrong :/

Also if it is correct, how can I build on it to make a definition for Strong Induction? Thank you!!

Answer 1

Ordinary induction need not start at $1$; it can start at any integer, positive, negative, or $0$. It’s the following principle:

Let $n_0$ be any integer, and let $P(n)$ be a proposition (about integers) such that $P(n_0)$ is true, and for each $n\ge n_0$, if $P(n)$ holds, then so does $P(n+1)$; then $P(n)$ holds for all integers $n\ge n_0$.

Here your induction hypothesis is $P(n)$, and the induction step consists in proving that $$P(n)\to P(n+1)\;.$$

Strong induction is the following principle:

Let $n_0$ be any integer, and let $P(n)$ be a proposition (about integers) such that $P(n_0)$ is true, and for each $n\ge n_0$, if $P(k)$ holds for all integers $k$ such that $n_0\le k\le n$, then so does $P(n+1)$; then $P(n)$ holds for all integers $n\ge n_0$.

Here the induction hypothesis is $P(n_0)\land P(n_0+1)\land\ldots\land P(n)$, and the induction step consists in proving that

$$P(n_0)\land P(n_0+1)\land\ldots\land P(n)\to P(n+1)\;.$$

In both cases the conclusion is that $P(n)$ holds for all integers $n\ge n_0$; one cannot conclude anything about the truth or falsity of $P(n)$ for integers $n<n_0$.

The two principles are logically equivalent: each can be proved from the other.

Answer 2

http://mathcircle.berkeley.edu/BMC4/Handouts/induct/node6.html

http://en.wikipedia.org/wiki/Mathematical_induction#Complete_induction

These links should answer your question.