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
Asked
Active
Viewed 47 times
0
-
I guess you would probably end up proving the statement for cases of $n\leq1$ – Lazy Lee Jun 05 '17 at 08: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 05 '17 at 09: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 06 '17 at 07:00
2 Answers
1
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$.
SilasLock
- 638
0
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...
Wuestenfux
- 20,964
-
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 05 '17 at 08:17
-