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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.