Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I do not understand the following from my lower grades. No one cleared my doubt properly with good examples. Why we need to learn Mathematical induction is I know very well. But, in which cases we treat or need to learn weak and strong induction. I really dont know. Why to learn weak and strong induction. Where it is really applicable. Please discuss with good example.

share|improve this question
    
1  
@Austin Mohr I don't think this is a duplicate of that thread, it seems like gama is asking for where we apply induction, and how to know whether we need week or strong rather than how it works. –  Tom Oldfield Dec 11 '12 at 4:16
1  
It is a perfectly legitimate question. –  André Nicolas Dec 11 '12 at 4:22
1  
You may find math.stackexchange.com/questions/108297/…? informative. But what are the "shades" referred to in the title of this question? –  Gerry Myerson Dec 11 '12 at 5:49

1 Answer 1

up vote 3 down vote accepted

The answer is simply that you use one that works. You don’t choose ahead of time which form to use; you use the one that gives you the strength of hypothesis needed to make your proof work.

Sometimes the hypothesis $P(n)$ simply isn’t strong enough to let us derive $P(n+1)$, but we can derive $P(n+1)$ if we assume $P(n)$ and $P(n-1)$. Sometimes we have to assume $P(k)$ for all $k$ such that $n_0\le k\le n$ in order to be able to infer $P(n+1)$. (Here $n_0$ is the initial value for the induction.) In practice you might as well simply assume that $P(k)$ holds for $k=n_0,\dots,n$ when trying to prove $P(n+1)$; if it turns out that you don’t actually need that strong a hypothesis, no harm has been done. In other words, when attacking a new proof, always remember that you can use the full strength of strong induction, though in many cases you won’t need to do so.

It’s unfortunate that so-called strong and weak induction are so often taught as different things, when in fact they are just very slightly different special cases of a considerably more general concept that covers transfinite induction and structural induction as well. Roughly speaking, it’s a method that applies whenever the setting is such that it’s meaningful to talk about a minimal counterexample to the theorem that you’re trying to prove. In the case of induction over the integers, a minimal counterexample is simply the smallest $n$ for which $P(n)$ is false. You can think of a proof by induction as a proof that no such minimal counterexample can exist. You suppose that $n$ is a minimal counterexample, and you get a contradiction. Sometimes the contradiction can be obtained just from the hypothesis that $P(n-1)$ is true; sometimes you find that you need a bit more $-$ the truth of both $P(n-1)$ and $P(n-2)$, for instance, or even of all $P(k)$ for $n_0\le k<n$. Since you’re assuming that $n$ is a minimal counterexample, however, you are assuming that $P(k)$ is true for $n_0\le k<n$, so you can use as much of that assumption as you need in order to get your contradiction.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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