Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
2  
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 at 7:00

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.