1
$\begingroup$

Generally, for induction proofs, we prove the property for a base case and then assume it holds for an arbitrary $n$ representative of some notion of $size$ for the object constructed, with the natural numbers being the most common object in the discourse. We then prove the property for $n+1$.

Alternatively, we have proofs where we assume that the property holds for $\forall k : k < n$ and then prove for $n$.

But, can we assume for the property holds for $n$, then prove it holds for $n - 1$?

$\endgroup$
  • $\begingroup$ Sure. Backwards Induction is a standard technique (used very often in Finance, for example). Of course you only prove your result for $k≤n$ this way, but still. $\endgroup$ – lulu Jun 9 '17 at 14:03
1
$\begingroup$

There are several different proof schemes by induction (so-called strong induction, forward-backward induction, transfinite induction, etc.). The most basic problem with your idea, which I'll denote by $P(n) \Rightarrow P(n-1)$, is that this only proves $P(k)$ for all $k \leq n$, where you know $P(n)$ is true. In this scheme, $P(n)$ acts as your "base case", and this backwards induction step allows you to prove $P(k)$ for all $k \leq n$.

There is a scheme called forward-backward induction, where you have "infinitely many base cases": suppose you have a sequence $n_i$ ($i \in \mathbb{N}$) such that you know $P(n_i)$, and for any $k$, you can find an $i$ such that $k \leq n_i$. Then if you know the backward inductive step that $P(n) \Rightarrow P(n-1)$, then you can find $P(k)$ for any $k$, since $k \leq n_i$ and $P(n_i)$ for some $i$. This is how one proof of Cauchy-Schwarz goes: let $P(n)$ be the statement that Cauchy-Schwarz works for $n$ numbers. We show three things: $$ P(1) $$ $$ P(2^n) \Rightarrow P(2^{n+1}) $$ $$ P(n) \Rightarrow P(n-1) $$ The first two items show that $P(2^n)$ always holds. The second item is the backwards induction that allows you to show that $P(k)$ holds for any $k$, since we may always find some $2^n \geq k$.

There is another interpretation to your idea that is common as well: the method of infinite descent (first widely used and attributed to Fermat). This is a proof by contradiction and here is the set up. Let $P(n)$ for all $n \in \mathbb{N}$ be the statement(s) I want to prove. We show that whenever $P(n)$ does not hold, we can find some $k < n$ (notice the strictly less than) such that $P(k)$ does not hold. Suppose $P(n)$ does not hold for some $n \in \mathbb{N}$. Then by the previous supposition we can find an infinite strictly descending sequence in $\mathbb{N}$, which is impossible. Euclid actually used this idea to show that every composite number is divisible by some prime (try messing around with this, it's pretty neat!). Anyway, this is sort of like your idea that $P(n) \Rightarrow P(n-1)$, in a more general framework.

| cite | improve this answer | |
$\endgroup$

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.