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?
Asked
Active
Viewed 39 times
0
-
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. – saulspatz Oct 09 '19 at 21:09
-
"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)$? – Bram28 Oct 09 '19 at 21:13
2 Answers
2
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.
J.G.
- 115,835
1
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)$.