2
$\begingroup$

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?
$\endgroup$
  • 2
    $\begingroup$ 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))$. $\endgroup$ – Git Gud Jun 6 '14 at 7:00
3
$\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$
1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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