0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I guess you would probably end up proving the statement for cases of $n\leq1$ $\endgroup$ – Lazy Lee Jun 5 '17 at 8:10
  • $\begingroup$ 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. $\endgroup$ – drhab Jun 5 '17 at 9:16
  • $\begingroup$ 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. $\endgroup$ – nerak99 Jun 6 '17 at 7:00
1
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SilasLock Jun 5 '17 at 8:17
  • $\begingroup$ Thanks SilasLock, that is exactly what I was asking. $\endgroup$ – nerak99 Jun 5 '17 at 8:18

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.