Principle of mathematical induction, negative numbers

Question

I know mathematical induction works for negative numbers. But, why it is giving me inappropriate results here?

Consider $1+2+3+\dots+n=\frac{n(n+1)}{2}$. I could prove base case by taking $n=0$. Then, after I suppose it holds for $K$, some integer, I could easily prove that it holds for $(K-1)$. So, by the principle of mathematical induction, it should hold for any integer $n$, but the actual verification fails as it isn't satisfied for $n=-1,-2$, or any other negative number.

When you say actual verification fails, what calculations did you perform? How do you define $1 + 2 + 3 + \ldots + n$ when $n = -1$? — Theo Bendit, May 24 '19 at 01:51
So, am I right in thinking, for the case $n = -2$, you summed $(-2) + (-1) = -3$, but you observed that $(-2)(-2 + 1) / 2 = 1 \neq -3$? — Theo Bendit, May 24 '19 at 01:54
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, use MathJax. — dantopa, May 24 '19 at 02:57

score 3 · Answer 1 · answered May 24 '19 at 02:36

The real question here is not about "backwards" induction - you seem to understand that correctly - but about the definition of the sum. Specifically, what does $$S(n)=1+2+3+\cdots+n$$ mean if $n=-1$? Or more generally if $n$ is any negative integer? Clearly the usual meaning,

add $1$ and $2$ and $3$ and so on until you get to $n$

makes no sense, because the sequence $1,2,3,\ldots$ will never get to $-1$.

Part of the problem here is that "and so on" is not a precise way of stating things. To define this kind of expression properly you should do it by induction:

$S(0)=0$ and for all $n>0$ we define $S(n)=S(n-1)+n$.

If you want to define $S(n)$ for negative $n$, the natural thing is to do basically the same:

$S(0)=0$ and for all integers $n$ we define $S(n)=S(n-1)+n$.

The equation can be rewritten as $S(n-1)=S(n)-n$; then we can calculate $$\eqalign{ n=0:\qquad&S(-1)=S(0)-0=0\cr n=-1:\qquad&S(-2)=S(-1)-(-1)=-(-1)\cr n=-2:\qquad&S(-3)=S(-2)-(-2)=-(-1)-(-2)\cr n=-3:\qquad&S(-4)=S(-3)-(-3)=-(-1)-(-2)-(-3)\ .\cr}$$ Note two things. First, we are not adding the terms you may have expected: the expression for $S(-3)$ involves $-1$ and $-2$ but not $-3$. Second, we do not have the sum of certain numbers but the negative of the sum: this can be "explained" by the fact that we are going backwards, by analogy with $$\int_2^1 f(x)\,dx=-\int_1^2 f(x)\,dx\ .$$ If you define $S(n)$ this way, you will find that indeed $$S(n)=\frac{n(n+1)}{2}$$ for all integers $n$. To repeat: the issue here is not the induction, but defining what $1+2+3+\cdots+n$ means if $n$ is negative. If you define it in a different way, then naturally you will get a different formula.

Alternatively, you could think of it in the following way (disclaimer: this is not going to be at all rigorous, but may be of interest). To get to say $n=-3$ from $1$, you will need to go "past infinity" and "continue from negative infinity". Then you would have $$\eqalignno{S(n) &=1+2+3+4+5+\cdots+(-5)+(-4)+(-3)&(*)\cr &=1+2\cr &=3\cr &=\frac{(-3)(-2)}{2}\cr &=\frac{n(n+1)}{2}\ ,\cr}$$ because everything in $(*)$ cancels except the $1$ and the $2$.

Thanks David.... helped me a lot! Couldn't understand 'analogy'. But it works. — user676740, May 26 '19 at 07:04

score 2 · Answer 2 · answered May 24 '19 at 02:10

There's nothing wrong with "backwards" induction over the negative integers. Regular old induction over the natural numbers involves a predicate $P(n)$ over the natural numbers (i.e. a sequence of true/false statements depending on a variable $n \in \Bbb{N}$). If you show $P(0)$ to be true, and prove for all $n$, $P(n) \implies P(n + 1)$, then you've proven $P(n)$ for all $n$; this is the principle of induction.

On the other hand, if you have a predicate $Q(m)$ for integers $m \le 0$, then we can simply define a predicate $P(n)$ over $n \in \Bbb{N}$ so that $P(n)$ is $Q(-n)$. So, if we prove $Q(0)$, then we have shown $P(0)$. If we prove $Q(m) \implies Q(m - 1)$ for all $m \le 0$, then we have shown $P(n) \implies P(n + 1)$ for all $n \ge 0$. By regular old induction, $P(n)$ is true for all $n \ge 0$, and hence $Q(m)$ must be true for all $m \le 0$.

Sorry if that was a bit technical; the short version is, backwards induction over negative integers works perfectly well, as it is a slightly obfuscated version of the normal forward induction.

Now, the other question: why is backwards induction not working in this case? Well, let's look at the forward induction proof first. In particular, the inductive step looks like this:

Suppose for some $n = k$, we have $1 + 2 + \ldots + k = k(k + 1) / 2$. Then $$1 + 2 + \ldots + k + (k + 1) = k(k + 1) / 2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2) / 2,$$ which proves the formula holds for $n = k + 1$.

Now, let's consider the backwards induction inductive step in the same way. Start by assuming $$-k + (-k + 1) + \ldots + (-1) = (-k)(-k + 1) / 2$$ for some $-k \le 0$. If we add $(-k - 1)$ to both sides, we get the correct left hand side, but the right hand side is more iffy. $$(-k - 1) + (-k) + (-k + 1) + \ldots + (-1) = (-k)(-k + 1) / 2 + (-k - 1)$$ In order for the induction to work, we would have to have $$(-k)(-k + 1) / 2 + (-k - 1) = (-k - 1)(-k) / 2$$ for all integers $-k \le 0$. This doesn't hold! Try subbing in some specific values of $k$, and you'll see that these polynomials are not the same.

This is the real reason why this particular proof is failing: the algebra simply doesn't add up.

Principle of mathematical induction, negative numbers

2 Answers2