We've learned that we can use induction to show that a statement holds for all natural numbers (or for all natural numbers above n). The steps are:
- prove that the statement holds for a base number b
- assuming that the statement holds for n, show that it holds for n+1.
This way we have proved that the statement holds for any integer $\ge b$
Can we take this a bit further to prove that the statement holds for ALL integer values? To my understanding, all we have to do is to try to prove:
$3$. assuming that the statement holds for n, show that it holds for n-1.
However I've never seen any articles on this, or any exercises being solved this way?
- Is this because my logic is not correct?
- Is this because "prove that this holds for all integers" can always be solved with a simpler way than using induction twice?
2 Answers
$\begingroup$If we have some sort of proposition $P(n)$ and we have proved that $P(n)$ is true for every $n \in \mathbb{N}$ by induction then we can proceed to create a new proposition $P'(n) = P(-n)$ and prove that for every $n \in \mathbb{N}$ thus showing that $P(n)$ is actually true for every $n \in \mathbb{Z}$. The steps to prove $P'(n)$ is to show that the base case $P'(0)$ is true and then proceed to show that $P(-n)$ true implies that $P(-(n+1)) = P(-n-1)$.
I personally have never used this but have seen it used in certain places.
Your logic appears correct, it's quite possible that a simpler way exists but this generally depends on what you're proving.
$\endgroup$ $\begingroup$As an example, if $f(n+2) = 5 f(n+1) - 6 f(n)$ for all integers $n$, and $f(0) = 0$ and $f(1) = 1$, then $f(n) = 3^n - 2^n$ for all integers $n$. You cannot avoid using induction twice, once upwards and once downwards.
$\endgroup$
