0
$\begingroup$

If I prove a Proposition which I assume holds for all $n \in N $ and I show the statement is true for n=0 and then I want to show it for it n+1. Can I also use that the statement is true for n-1? Or do I have to add n=1 to the base case and then say that the statements hold for two consecutive numbers?

$\endgroup$
  • $\begingroup$ You can either assume that the statement is true for $n$ and prove it is true for $n+1$ of you can assume it is true for all natural number $\leq n$ and prove it true for $n+1$. The two methods are equivalent. $\endgroup$ – saulspatz Oct 9 '19 at 21:09
  • $\begingroup$ "Can I also use that the statement is true for n-1?" -> I'm not sure what you mean .. are you trying to prove that $P(n+1)$ on the basis of $P(n-1)$ (in addition to $P(n)$)? Or are you trying to go from $P(n-1)$ to $P(n)$ instead of going from $P(n)$ to $P(n+1)$? $\endgroup$ – Bram28 Oct 9 '19 at 21:13
1
$\begingroup$

It sounds like you want to use $\varphi(n-1)\land\varphi(n)\to\varphi(n+1)$ as your inductive step, in which case yes, you need the first two values for $n$ in your base step. But depending on what you're trying to prove, you might find strong induction helps too.

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

Given that you have proved the truth of $P(0)$ and are trying to prove the truth of $P(n)$ then you can assume that all $P(i)$ are true for $0\le i\le n-1$.

The only "issue" arises with $n=1$ when you can, of course, only assume $P(0)$.

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