On proofs by induction The traditional structure of a proof by induction goes like this:


*

*basis: we show that the statement holds for the initial natural number $n$

*Inductive step: We show that if the statement holds for $n$ then it holds for $n+1$.
My question is:
Would it work if we changed the order of the inductive step: We show that if the statement holds for $n+1$ $\underline{then}$ it holds for n
 A: That doesn't quite work. I think this is a misunderstanding on how induction works. 
So for regular induction as you said what we do is:


*

*Prove the statement holds for some integer $k$

*Prove that the statement holds for $n+1$ if it holds for $n$


Now this works because since the statement holds for $k$ it would then hold for $k+1$ and then since the statement holds for $k+1$ this means it holds for $k+2$ and so on and thus the statement holds for all integers $n$ such that $n \geq k$.
Now what you're suggesting is:


*

*Prove the statement holds for some integer k

*Prove the if the statement holds for $n$ if it holds for $n+1$


Now this would work a bit differently because since the statement holds for $[k-1]+1$ this means the statement then holds for $k-1$ and then we know that the statement holds for $[k-2]+1$ which means that it holds for $k-2$, and so. the outcome would be that you proved that the statement holds for all integers $n$ such that $n \leq k$.
Now notice that if you're able to prove both of the methods above then you have proved that the statement holds for all integers.
