Regarding proof by Induction

If I constructed a proof that worked like this, shown true for n=1. If assumed true for n=k then shown to be true for k-1 (i.e. rather than k+1) blah blah ..

Is this just no proof at all or has it got any validity?

Brian

• I guess you would probably end up proving the statement for cases of $n\leq1$ – Lazy Lee Jun 5 '17 at 8:10
• Suppose that it works for positive integers. Then we can prove that $n=1$ for every positive integer $n$: it is true for $n=1$ and the statement $n=1\implies n-1=1$ is true for every $n>1$. This because a statement like $p\implies q$ (equivalent with $\neg p\vee q$) is true whenever $p$ is false. – drhab Jun 5 '17 at 9:16
• Well since we know that n-1 is not 1 for all n>1 there must be a problem with what you are saying here. However, if you could "expand on p⟹q (equivalent with ¬p ∨ q) is true whenever p is false" [because I do not understand this] I think it says that NOT p AND q implies q (?) which I do not think is right. – nerak99 Jun 6 '17 at 7:00

The proof would be legitimate, but only if you were trying to prove statements where $n$ is less than or equal to $1$. Otherwise you're just going the wrong direction with your induction.

Ordinarily, induction works by proving that $P(0)$ is true (a base case), followed by proving that $P(n) \Rightarrow P(n+1)$ for any given $n$ (the inductive step). The reason this works is because, having proven $P(0)$, your inductive step automatically proves $P(1)$, which in turn automatically proves $P(2)$, which in turn proves $P(3)$, etc. The chain ratchets up forever.

In your example, you'd be proving that $P(n) \Rightarrow P(n-1)$ instead of the usual, "upwards facing" inductive step. But as with all induction, this is just an implication; if the premise is false, the consequent doesn't follow. From the start, the only statement you've concretely proven is the base case: $P(0)$ (or as you've written it, $P($n$)$).

By the inductive step, this in turn proves $P(-1)$, which in turn proves $P(-2)$, which proves $P(-3)$, etc. So you'd never inductively prove your usual set of results for the positive integers; you've only ever prove statements where $n$ is less than or equal to $1$.

• Thanks SilasLock, that last para was the clarification I needed. – nerak99 Jun 5 '17 at 8:40
• @nerak99 Glad I could help! =) – SilasLock Jun 5 '17 at 9:27

It has. Given the predicate $P(n)$ to be proved.

Prove $P(0)$.

Prove $P(0)\Rightarrow P(1)$. Then by modus ponens, you have proven $P(1)$.

Prove $P(0)\wedge P(1) \Rightarrow P(2)$ (strong induction) or $P(1)\Rightarrow P(2)$. Then by modus ponens, you have proven $P(2)$.

You get the pattern...

• I don't think this is what Brian/nerak99 is asking about; he's trying to find out if induction works when directed downwards on the integers, rather than the usual upwards. – SilasLock Jun 5 '17 at 8:17
• Thanks SilasLock, that is exactly what I was asking. – nerak99 Jun 5 '17 at 8:18