Let $P(n)$ be a statement to be proven by induction, where $n \in \mathbb{N}$ (with possible exceptions). In the inductive step we conventionally assume a statement $P(k)$ to be true, to show that $P(k) \implies P(k+1)$. Do we have to define $k$ as being natural (or commensurate to the domain of $P(n)$), instead of it just being an integer? The whole point of the inductive step is to show that a relation holds between two consecutive integer numbers, regardless of whether there is a first number to start from, so in principle it should also be valid for negative numbers.

Likewise, would it also make sense to use induction 'in reverse', for negative numbers, that is: Prove $P(n)$ for some $n \lt 0$, then assume $P(k)$ to be true, where $k \in \mathbb{Z^-}$ (or just $\mathbb{Z}$ for that matter), then shown that $P(k) \implies P(k-1)$?

  • 1
    $\begingroup$ Remember that induction isn't useful without the induction basis, theoretically you can start from $n=-100$ but you have to start somewhere... For the other question, yes induction in reverse does make sense (again you have to start somewhere). $\endgroup$ – Yanko Oct 17 '17 at 17:56
  • $\begingroup$ as long there is a biyective function that maps the the domain of $P$ and some subset of $\mathbb{N}$ you should be ok. $\endgroup$ – 3d0 Oct 17 '17 at 18:22

Your Answer

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

Browse other questions tagged or ask your own question.