0

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$?

Community
  • 1
Piquito
  • 29,594
  • 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): http://math.stackexchange.com/q/1472200/50951 – AJMansfield Oct 09 '15 at 17:22
  • 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. – taninamdar Oct 09 '15 at 17:24
  • @AJMansfield: I glad to know your question. – Piquito Oct 09 '15 at 17:25
  • @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) – Piquito Oct 09 '15 at 18:02

1 Answers1

1

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.$$

DanielWainfleet
  • 57,985
  • 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. – Piquito Oct 09 '15 at 19:40