By the way of Proving Theorems I have strong doubts about my in-depth knowledge of the Principle of Induction now. I clearly remember reading a reference in France about their use from $n$ to $n-1$ (to down) instead from $n$ to $n + 1$ (to up) as usual, illustrated with a practical (and correct, of course) example, but cannot locate at present such a reference I have read some time ago.

I would greatly appreciate any comment from connoisseurs to the two following points:

1) What conclusion can deduce whether to prove a property $\mathcal{R}$, induction applies as usual and only known, say that $\mathcal{R} $ is true for n = 93?

2) Suppose it is asked to prove $ 1 + 3 + 5 + \cdots + (2n-1) = n ^ 2 $ and accepting this is true for n it is shown to be true for n-1 as follows:

$$1 + 3 + 5 +....+\space (2n-1) = n ^ 2$$ means $$1 + 3 + \cdots + (2 (n-1) -1) + (2n-1) = n^2$$ which implies $$1 + 3 + \cdots + (2 (n-1) -1)=n^2-2n+1=(n-1)^2$$

What conclusión can be deduced from this? n is arbitrary; what is missing to complete the proof for all $n$?

  • $\begingroup$ I asked a very similar question about 15 minutes ago (except in my case I know what I can conclude, I just don't know how to prove it): math.stackexchange.com/q/1472200/50951 $\endgroup$ – AJMansfield Oct 9 '15 at 17:22
  • $\begingroup$ I suppose it only proves that something is true for values $\le n$. For example, $P(n) = n^6 \ge 6^n$ is true for $2 \le n \le 6$. And assuming $2 \le n \le 6$, you can prove that $P(n) \implies P(n-1)$. However, $P(7)$ is clearly false. $\endgroup$ – taninamdar Oct 9 '15 at 17:24
  • $\begingroup$ @AJMansfield: I glad to know your question. $\endgroup$ – Piquito Oct 9 '15 at 17:25
  • $\begingroup$ @taninamdar: Thanks for your comment. I guess this "down" way is censed to be useful when n is reasonably in order to use for m<n. Not when one search for an obvious counterexample but for proving something suspected to be true. What about the point 2)?, please. (Sorry by English without Google translator) $\endgroup$ – Piquito Oct 9 '15 at 18:02

Pierre de Fermat (early 17th century) called the "downward" induction method the method of "infinite descent".The point is that if the sentence $S(n)$ were false for some $n$, there would be a least such $n$, which we will call $n_0$. Now if you have proved that $$\sim S(n) \to \sim S(n-1) \text{ whenever } n>1$$" then you know that "$n>1\to n \ne n_0$." This gives you " if $n_0$ exists then $n_0=1$." But if $n_0$ exists,we have $\sim S(n_0)$, so if $n_0$ exists then $n_0=1$ and $\sim S(1).$ ..... THEREFORE if "$\sim S(1)$" is FALSE then $n_0$ does not exist and we have $\forall n S(n)$.NOTE.Showing $S(n) \to S(n-1)$ will NOT work. For example suppose that $S(n)$ is "$83>n$." A more general and more flexible method is to replace $$\sim S(n)\to \sim S(n-1) \text{ whenever } n>1$$ with $$\sim S(n)\to \exists m<n (\sim S(m))\text { whenever }n>1.$$

  • $\begingroup$ It was not in the context of this infinite descent (which, by the way, is particularly specific and largely generalized at present) I read the correct application to down of principle of induction I said in this post. Thank you. $\endgroup$ – Piquito Oct 9 '15 at 19:40

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.