0
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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 ... $\endgroup$ Apr 12 '13 at 1:17
  • $\begingroup$ in fact it's wrong you feel like this is wrong then you say it is wrong only if you can give the proof $\endgroup$
    – Xiaolang
    Apr 12 '13 at 1:18
  • $\begingroup$ @Xiaolang, Im not sure I understand what you mean :/ $\endgroup$
    – nicefella
    Apr 12 '13 at 1:22
  • $\begingroup$ 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 $\endgroup$
    – Xiaolang
    Apr 12 '13 at 1:24
  • 1
    $\begingroup$ i think the definition is natrual and just like what George V.Williams said...it can be expanded to any integer $n \in N$ $\endgroup$
    – Xiaolang
    Apr 12 '13 at 1:31
2
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

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

These links should answer your question.

$\endgroup$
2
  • $\begingroup$ I read the wikipedia link, it wasn't helpful. Thank you though, the link from Univ of Cal is great thanks :) $\endgroup$
    – nicefella
    Apr 12 '13 at 1:21
  • $\begingroup$ Please try to describe as much here as possible in order to make the answer self-contained. Links are fine as support, but they can go stale and then an answer which is nothing more than a link loses its value. $\endgroup$
    – robjohn
    Jun 5 '13 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.