Why doesn't mathematical induction work backwards or with increments other than $1$?

Question

From my understanding of my topic, if a statement is true for $n=1$, and you assume a statement is true for arbitrary integer $k$ and show that the statement is also true for $k+1,$ then you prove that the statement's true for all $n\geq 1$. Makes sense.

However - why can't I do this backwards? If I show the statement is true for $k-1,$ aren't I showing that if the statement is true for $n=1,$ it's likewise true for $n=0,n=-1,n=-2,\ldots$?

Also, why can't I prove the statement is true for $k+0.1$, and prove the statement true for $n=1.1,1.2,1.3,\ldots$? Both of these scenarios, in my mind, seem to follow the same logic as the "proper" definition of mathematical induction - but apparently they're no-go. Can someone please explain why?

Thank you!

Edit: The consensus seems to be that yes, even though it's abnormal, induction as I've stated above it is logically sound. Which raises the question - why has my math teacher said this is wrong? Is it as I suspect, where she didn't want me straying from the proper definition of $k+1$ induction and possibly confusing myself (or losing points on the test), or is there something else that makes the above fundamentally flawed?

Thanks!

Answer 1

It does work in both ways that you suggested. Typically induction problems are stated so that you want to prove $P(n)$ for all natural numbers $n$. Then you start with $P(1)$ and go from $n$ to $n+1$. However, if you wanted to prove it for negative integers instead you would start with $P(-1)$ and go from $n$ to $n-1$. Of course, you can just change the variable $m:=-n$ and reduce the second case to the first. The same goes for your other example with $m:=10(n-1)$. Since 'backwards' and 'fractional' induction reduce to the standard induction they are equally justified.

Answer 2

I'm going to be brave and disagree with most of the other answers. (Exception: I agree with, and have upvoted, Dan Piponi's answer; but I think that that answer buries the lede.)

You've been given a theorem in class, along these lines:

Let $P(n)$ be a statement about $n$, with these properties:

1. $P(1)$ is true.
2. For all $k \in \mathbb{N}$, if $P(k)$ is true then $P(k+1)$ is true.

Then $P(n)$ is true for all $n \in \mathbb{N}$.

and your teacher wants you to write proofs using that theorem.

Using your mathematical intuition, you have correctly divined that there are many other, similar theorems, such as one theorem to cover "all integers $m \le 1$" by starting with $1$ and counting backward, and one theorem to cover "all numbers of the form $1+\frac{p}{10}, p \ge 0$". But those theorems aren't "givens"; they don't appear in your textbook, and your teacher hasn't taught them to you. When you're asked to write a proof for class, it is a tacit requirement that your proof depend only on a certain set of preexisting results that it's O.K. for you to use — the axioms and theorems you're given in class, plus (probably) mechanical algebra and arithmetic. Without that tacit requirement, you could "prove" everything by simply stating that it's a correct statement and therefore proven. So I think your teacher is right to expect you to use the canonical formulation of induction you've been given in class, rather than other similar theorems.

That said, your modified theorems can be proven fairly straightforwardly as corollaries of regular mathematical induction. Dan Piponi's answer shows how to do that for one of your theorems. So you can use your modified theorems, but only as an intermediate step: first you prove the modified theorem, then you use it to prove what you are actually asked to prove. But this is probably unnecessary busy-work; you might as well just combine the two steps, and write your proof directly in terms of the theorem you've been given.

Answer 3

Consider your first example of counting down:

Suppose property $Q(n)$ holds for $n=1$. Suppose also that $Q(n)$ implies $Q(n-1)$.

Define a new property $P$ by $P(n)$ if and only if $Q(2-n)$.

We supposed $Q(1)$ so we know $P(1)$. Suppose $P(n)$. That implies $Q(2-n)$. We deduce $Q(2-n-1)$ which is $Q(2-(n+1))$. And that implies $P(n+1)$.

So we can use induction to find that $P(n)$ holds for all $n\ge 1$.

And therefore Q(n) holds for all $n\le 1$.

So counting down works fine. But if you haven't yet proved it works you need to prove it at least once from the usual induction argument.

A similar line of reasoning shows that your second example works fine too.

Answer 4

Even in the natural numbers, you can argue backwards.

Proposition. Suppose that $A \subseteq \mathbb{N}$ has the property that every $a \in A$ either equals $0$, or else satisfies $a-1 \in A$. Then $A$ is downward closed. (Meaning that for all $a \in A$ and $b \in \mathbb{N},$ if $b<a$ then $b \in A$.)

I don't think its hugely useful, though. Thankfully, a more useful variant of "backwards" induction holds for the integers:

Proposition. Suppose that $A \subseteq \mathbb{Z}$ has the property that every $a \in A$ satisfies $a-1 \in A$. Then $A$ is downward closed. (Meaning that for all $a \in A$ and $b \in \mathbb{Z},$ if $b<a$ then $b \in A$.)

By the way, a good way of looking at induction is via free algebras.

Claim. Let $T$ denote an equational theory, $X$ denote a set, and write $Z$ for the $T$-algebra freely generated by $X$. Suppose also that $A$ denotes a subset of $Z.$ Then if

1. $X \subseteq A$ and
2. $A$ is a $T$-subalgebra (of $Z$)

then $A$ covers the entirety of $Z$.

For example, we can think of $\mathbb{Z}$ as the object freely generated by $X=\{0\}$ with respect to the equational theory with two unary operations $S$ and $P$, subject to the axioms $S(P(n))=n$ and $P(S(n))=n$. It follows (by the preceding claim) that if $A$ is a subset of $\mathbb{Z}$ that is closed under $S$ and $P$ and includes $0$, then $A$ covers the entirety of $\mathbb{Z}$.

Answer 5

You can also have steps larger than one, i.e., to show that all numbers at least 12 can be represented by summing 3s and 7s: \begin{align} 12 &= 3 + 3 + 3 + 3 \\ 13 &= 7 + 3 + 3 \\ 14 &= 7 + 7 \end{align} Now you can construct $12 + 3 k$ for any $k \ge 0$, and similar for the other two. As they interleave, they cover all numbers promised.

Answer 6

A more rigorous understanding of induction shows that it is much more abstract than what you seem to think it is. The way I learned it was in the context of Peano Systems, you can apply proof by induction to any set P equipped with a function S (the successor function, S(x) is the successor of x) such that:

-P contains an element that is no element's successor (often called "1", not to be confused with the natural number)

-Every element of P except "1" is a successor of another element of P

-Different elements of P have different successors

-P is closed under the successor function

Answer 7

Consider forward-backward induction. You prove it for the base case (usually $n = 1$) and then you prove that if it works for $n = k$ then it works for $n = 2k$. This means it works for $n = 1, n = 2, n = 4 ... n = 2^m$ for any positive integer $m$. Then you prove that if it works for $n = k$ it works for $n = k-1$. If the above holds then it works for any positive integer because every positive integer is less than $2^m$ for some $m$.

This exhibits induction working with multiplication and another increment (namely incrementing by $-1$).

Here is a proof of the following statement about complex numbers:

$$|z_1z_2...z_n| = |z_1||z_2|...|z_n|.$$

The case where $n=2$ can be shown with simple algebra $(|z_1z_2| = |z_1||z_2|)$. Assume it holds for $n = m.$ Now, we will show that it works for $n = 2m$. We must prove that $$|z_1z_2...z_{2m}| = |z_1||z_2|...|z_{2m}|.$$ Let $a = z_1z_2...z_{m}$ and $b = z_{m+1}z_{m+2}...z_{2m}$. It is clear that $|ab| = |a||b|$ because $a$ and $b$ are two complex numbers. From the induction hypothesis we have that $|a| = |z_1||z_2|...|z_{m}|$ and $|b| = |z_{m+1}||z_{m+2}|...|z_{2m}|$.

Substituting this into our equation we find that: $$|z_1z_2...z_{2m}| = |a||b| = \Big( |z_1||z_2|...|z_{m}|\Big)\Big(|z_{m+1}||z_{m+2}|...|z_{2m}|\Big)=|z_1||z_2|...|z_{2m}|.$$ We have shown that the formula works for $n = 2, 4, 8 ... $ using this method. Now, note that the equation still holds for any $n$ that is less than $2^k$ for $k\in\mathbb{Z}_+$. This is because we may set any given $z_j = 1$ which will remove one of the terms from both sides of the equation. Because every finite $n$ is less than $2^k$ for some $k$, the formula holds for every $n$.

Answer 8

The one thing to note is that the principle of induction is basically a trivial mapping to one particular Peano axiom, one of the axioms defining the set of natural numbers. Your examples are simple mappings to that axiom but not trivial.

Your teacher does not want to see you skip over simple steps. "But that's just the same" is not a valid part of a proof. Once you make this variable change or mapping an official part of the proof (and in a math paper, pushing in the word "equivalently" in a proper place might be all that is needed, but in school you might not get off that cheaply), your teacher cannot complain.

But any kind of handwaving to get from almost-A to A is not acceptable in mathematics.

In university, nobody will bother whether your starting point is 0, 1, or actually anything integer as long as you are not doing formal logic and reasoning, and your proof is for $n \ge whatever$ with $whatever$ being what you explicitly proved as being a valid starting point.

When doing downward induction, however, you usually need to be more verbose.

Answer 9

What you're describing is really induction on $\mathbf{N}$ "in disguise." (I know some of the other answers mention this, but this goes slightly more in-depth.)

Given some property $P$, the axiom of induction says that if $P(1)$ is true, and $P(k)$ implies $P(k+1)$, then $P(n)$ is true for all natural numbers $n$. Now, if you want to use induction with some increment $c$ (such as $-1$ or $.1$, like you mentioned in your question), and starting at some number $a$, define the following sequence $$a_1 = a, a_2 = a + c, a_3 = a + 2c, \ldots, a_n = a + (n-1)c, \ldots$$ Now, if you're trying to demonstrate property $P$, define a new property $Q$, such that $Q(n)$ is true if $P(a_n)$ is true, and false otherwise. Now, show that $Q(1)$ is true (meaning $a$ satisfies your property), and that $Q(n)$ implies $Q(n+1)$ (meaning if $P(a_n)$ is true, then $P(a_n + c) = P(a_{n+1})$ is true). The aforementioned axiom of induction now implies that $Q(n)$ is true for all natural numbers $n$, so your property $P$ holds for $a_1, a_2, a_3, \ldots$ which is exactly what you wanted to show.

Answer 10

Inductive arguments can be applied to any objects which can be defined inductively. They work by transforming each object x into a proof P(x).

For example, the Naturals (0, 1, 2, ...) can be defined inductively as 0 and n+1, given any Natural n. Since every Natural is some combination of these two cases, we can transform every Natural into a proof by transforming these two cases. We transform 0 into P(0) and transform n+1, given any Natural n into P(n+1), given any proof P(n). These are exactly the inductive cases you mention.

If we use different inductive cases, we must transform those cases instead. Note that this is not at all limited to numbers. Here are some examples:

• A list of objects can be inductively defined as empty or X followed-by L, given any object X and list L. We can prove P for all lists (of all objects) by proving P(empty) and P(X followed-by L), given any proof P(L).
• A tree can be inductively defined as leaf or branch A B, given any trees A and B. We can prove P for all trees by proving P(leaf) and P(branch A B), given any proofs P(A) and P(B).

Inductive definitions and proofs like this are an active area of research in Computer Science, since they form the basis of "pure functional programming".

Answer 11

You actually CAN do those things. You just have to use the more general version which proves mathematical induction to be a valid tactic. Mathematical induction derives from category theory

Really what you do is this:

1. Define an state for which your predicate is true (i.e. prove for N=1), and make a proof P for that state
2. Define a transform which turns any state into a different state (mathematical induction uses the transform N' = N + 1)
3. Demonstrate that there is a transform so that "If a proof P is valid for N, then a proof P' is valid for N'" (prove the statement for N+1 using the proof of the statement for N)
4. Demonstrate that, for all N you are interested in, those N are "reachable" by repeated application of the transform.

Mathematical induction is an example of this process. It is designed to work from N=1 with N'=N+1 only because that particular transform provably reaches every integer. What that means is that, if you can come up with a valid way to prove your statement for N+1 using N, the rules of how integers handle infinity will take care of the highly technical part of guaranteeing reachablitly by all natural numbers.

Why is this important? It is reasonably easy to make transforms which reach all natural numbers, and demonstrate a proof for them. It is much harder to make other transforms, such as ones which could reach all real numbers. If you have to prove something over all real numbers, you have to be much more careful.

As a classic example, it is easy to make proofs using mathematical induction which work for all positive rational numbers (A/B where A and B are natural numbers) and 0. However, numbers like pi are irrational. If you mistakenly apply your proof to an irrational number, it may give you the wrong result.

A common tactic to do other things, such as N=N'+0.1 or N=N-1 is to define a reversable transform for the problem into natural numbers (trivial to do for the two examples you listed). As an example, you could change N=N'+0.1 to 10N = (10N)' + 1 = 10N' + 1. Then, if you solve that problem using mathematical induction, you reverse the transform (such as dividing by 10) to provide the desired proof.

Answer 12

I just want to add to the other good answers above that in speaking of some number, when we write -n or -k, we do not say, "negative n" or "negative k". We say "the opposite of n" or "the opposite of k." The reason why we avoid saying "negative n" is because we do not know the value of n. Thus, to refer to n as negative or positive could be confusing. This matter of diction alone helps elucidate many of the answers above, particularly on the question of whether you can use the principle of mathematical induction in the opposite direction.

Answer 13

This kind of induction has both it goes backwards and has increments other than 1.

Answer 14

Suppose I gave you a set, $\mathbf T$, that is a subset of the natural numbers, $\mathbb N = \{1, 2, 3, \dots\}$. That is to say, $\mathbf T \subseteq \mathbb N$. How do we prove is that $\mathbf T = \mathbb N$? Peano showed that proving

$\quad$ (1) $1 \in \mathbf T$
$\quad$ (2) $k \in \mathbf T$ implies $k+1 \in \mathbf T$

proves that $\mathbf T = \mathbb N$. Actually it's a bit more complicated than that, but the details are not that important for what we are doing here.

Mathematical induction is built upon this principle.

Saying that $P(1)$ is true is equivalent to saying that $1 \in \mathbf T$.

Saying that $P(k)$ is true implies that $P(k+1)$ is true is equivalent to saying that $k \in \mathbf T$ implies $k+1 \in \mathbf T$.

Saying that $``P(n)$ is true for $n = 1, 2, 3, \dots"$ is equivalent to saying that $\mathbf T = \mathbb N$.

---

If you want to show that $P(n)$ is true for $n = 1.1, 1.2, 1.3, \dots $, then $\mathbf T \subseteq \{1.1, 1.2, 1.3, \dots\}$ and your goal is to prove that $\mathbf T = \{1.1, 1.2, 1.3, \dots\}$ What you need to prove is

$\quad$ (1) $1.1 \in \mathbf T$
$\quad$ (2) $k \in \mathbf T$ implies $k+0.1 \in \mathbf T$

If you can do that, then P(n) is true for $n = 1.1, 1.2, 1.3, \dots $.

---

If you want to show that $P(n)$ is true for $n = 0, -1, -2, \dots $, then $\mathbf T \subseteq \{0, -1, -2, \dots\}$ and your goal is to prove that $\mathbf T = \{0, -1, -2, \dots\}$ What you need to prove is

$\quad$ (1) $0 \in \mathbf T$
$\quad$ (2) $k \in \mathbf T$ implies $k-1 \in \mathbf T$

If you can do that, then P(n) is true for $n = 0, -1, -2, \dots $.