Induction assuming n-1 In induction, I always thought that one assumed that some statement was true for n and then showed it's true for $n+1$. But in one proof I am trying to understand, I think that they assume that it's true for $n-1$, and then show it's true for $(n-1)+1 = n$. 
Is this ok? Are you allowed to assume that something is true for $n-1$ and then show it's true for $n$? This seems wrong to me because if one has a base case of $n$, and then assumes it's true for $n-1$, and then proceeds to prove that it's true for $n$, then one has only proved something that we already knew, namely that it's true for $n$. 
$$T(n)=2T(n-1)+1;\quad T(0)=0$$
I want to prove that this recurrence is really 
$$T(n)=2^n -1$$
Base case: $$T(0) = 0 = 2^0-1$$
Induction step:
\begin{align*}
T(n) &= 2*(2^{n-1} -1) +1 \\
     &= 2^n -1
\end{align*}
On line 1 of the inductive step, did the author assume it's true for $n-1$? 
Link:
https://courses.engr.illinois.edu/cs573/fa2010/notes/99-recurrences.pdf
 A: You seem to be worrying about the explicit algebraic formulation, but not understanding how/why induction works. I'll try to explain without using mathematical symbols, in order to clarify.
Induction works as follows. You prove two things.


*

*Prove it for the base case

*Prove that if it is true for some case, then it must be true for the next case.


Why does this work? Let's say, for concreteness, the base case is 0. Then, by (1), it (whatever we are trying to prove) is true for 0. By (2), the fact that it is true for zero implies that it is true for 1. Again by (2), the fact that it is true for 1 implies that it is true for 2. Again by (2), the fact that it is true for 2 implies that it is true for 3. The process continues.
Now the question is, how do we formalize the statement of (2)? The answer is to replace "some case" and "the next case" by numbers. If we assign "some case" the number $n$, then "the next case" would be the number $n+1$. This is how you seem to be thinking about it.
If, on the other hand, we assign "some case" to be the number $n-1$, then "the next case" would be $n$. If we think about it this way, maybe a better way to write (2) would have been:


*Prove that it is true for this case whenever it is true for the previous case.


In plain english, we can understand that the two versions of (2) are the same, but people get caught up in the symbols when they try to translate it into math.
A: It doesn't matter if you do the induction step from $n$ to $n+1$ or from $n-1$ to $n$. This is already clear from the fact that $n$ is an arbitrary natural number.
All that matters is that you prove that cou can do the "next number" as well. Imagine proofs by induction like walking up stairs. You need to prove that you can start somewhere and then that you can go from an arbitrary step to the next one.
A: Yes it is totally fine. Induction is based on well ordering property of Natural numbers. So main requirement is for it to have the least element, and it doesn't matter how you build your cases logically after that. Either n+1 or n-1
