# Induction with negative step

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:

1. prove that the statement holds for a base number b
2. 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?
-
It's because if you want to prove $\forall n\in \mathbb Z(P(n))$ and you proved $\forall n\in \mathbb N(P(n))$, then, $\forall n\in \mathbb Z(P(n))$ follows from $\forall n\in \mathbb N(P(-n))$ in conjunction with $\forall n\in \mathbb N(P(n))$. – Git Gud Jun 6 '14 at 7:00

## 2 Answers

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.

-

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.

-