# Formal definition of Mathematical Induction & Strong Induction

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!!

• To explain why this is the definition: if $p(1)$ is true, then $p(2)$ is true (since $p(n) \Rightarrow p(n+1)$). If $p(2)$ is true, then $p(3)$ is true. If ... Apr 12 '13 at 1:17
• in fact it's wrong you feel like this is wrong then you say it is wrong only if you can give the proof Apr 12 '13 at 1:18
• @Xiaolang, Im not sure I understand what you mean :/ Apr 12 '13 at 1:22
• i mean you should give more your thought to let us know instead of just say "it's wrong" .we had problem helping you don't know where you are incorrect Apr 12 '13 at 1:24
• i think the definition is natrual and just like what George V.Williams said...it can be expanded to any integer $n \in N$ Apr 12 '13 at 1:31

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.

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

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