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.

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 \ge 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 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!

share|improve this question
29  
Who told you they are "no-go"? If it makes sense then it probably works. (In fact, it does here.) –  NotNotLogical May 28 at 0:18
5  
You can use variations on induction. There's a classic proof that the arithmetic mean >= geometric mean using induction twice, first from n elements to 2n elements, and then from x elements to x-1 elements. Proving the base for 1 allows you to each any integer. –  Ricbit May 28 at 0:18
7  
This can be useful even if the increment is bigger than 1. Imagine an increment of 2. If your base case is 1, this gives you 1, 3, 5... all odd numbers. But now all you have to do is show the base case of 2 and you get all the evens as well. So if big increments make the proof easier, then show it by all means. Just make sure that you fully cover the required set with your increments and base cases. –  Cruncher May 28 at 13:59
3  
I don't know where you live, but in my country math teachers are not usually mathematicians. They (hopefully!) know the answers within the limits of the curriculum, but not necessarily outside of it. –  Harry Johnston May 29 at 4:18
3  
From my own experience, many high-school math teachers (but there are wonderful exceptions) do not bother to understand what they teach, in the sense that they cannot prove many things including simple identities. Hence they are in no position to determine what is correct and what is not. –  user21820 May 29 at 4:29

13 Answers 13

up vote 14 down vote accepted

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.

share|improve this answer
1  
This is exactly what I was thinking: if we assume that the teacher was talking sense then this is pretty much certain to be what was meant. If we admit that the teacher might just be flat wrong, then it's possible something else was meant :-) –  Steve Jessop May 29 at 14:38
1  
Aha, viewing the induction I've been taught as a theorem rather than a general technique elucidates my teacher's explanations quite well. Thank you very much! @SteveJessop - I have doubts that many high school math teachers have an understanding of induction comparable to those who've posted here- induction, apparently, is rare in a high school precalc curriculum to begin with, and we took only a very cursory look at the topic, so please don't assume my math teacher is incompetent in the slightest! :) –  theycallmezeal May 30 at 5:10

It does work 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.

share|improve this answer
6  
Plus, you never see the "+0.1" increment because what would be the class of numbers you are demonstrating the property for? The reals cannot be attained simply by adding a constant, so basically you only use induction for countable sets, and so you just need "+1" to get wherever you need ;-) –  Ant May 28 at 17:54
6  
Actually, induction works fine for uncountable sets too. For induction you need a relation between a proposition and some "children" propositions. For example, with induction over the integers you can think of P(n+1) being a child of P(n). For induction to work you need a relation that satisfies a bunch of properties and there are plenty of uncountable sets that have suitable relations on them. en.wikipedia.org/wiki/Transfinite_induction (In practice you often you need the axiom of choice to show a suitable relation exists.) –  Dan Piponi May 28 at 19:41
    
@DanPiponi wow, cool.. Thanks! :-) –  Ant May 28 at 21:09
1  
@Ant: But don't call "transfinite induction" simply "induction" because it is strictly stronger and cannot be reduced to an ordinary induction. –  user21820 May 29 at 4:32
1  
@user18921: The property of satisfying transfinite induction is a strictly weaker property because the technique of transfinite induction is strictly stronger: every proof by ordinary induction can be "reduced" to a proof by transfinite induction, but the reverse is not true. –  ruakh May 30 at 6:13

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.

share|improve this answer

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}$.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
1  
This works even when there are several starting points and successor constructions, and that is called structural induction –  vonbrand May 28 at 2:14
    
This answer is basically completely wrong. Because firstly, the injectivity of $S$ has nothing to do with induction. Secondly, $P$ containing an element that is not the successor of any other element is irrelevant; for example, we can do induction on $\mathbb{Z}_n$ by proving $\forall n \;\;P(n) \rightarrow P(Sn)$ and $\exists n Pn$. Thirdly, induction is a much, much more general concept than just the induction principle for the natural numbers. See also, structural induction and/or my answer. Fourthly, the only Peano system satisfying... –  goblin May 28 at 8:29
    
... full-blown second-order induction is $\mathbb{N}$, so I don't see how this is any more abstract than the OP's question suggests. Also fifthly I just disagree with the general contention that abstraction and rigor are the same thing. There exists highly abstract mathematics that is not very rigorous, and there also exists highly concrete mathematics that is very rigorous. –  goblin May 28 at 8:30
    
you forgot that it is not allowed to have an infinie descending chain in your order relation. Otherwise, induction is going to break down. In fact, you don't need a successor function, you only need a well-founded relation en.wikipedia.org/wiki/Well-founded_relation The induction described in the linked wikipedia article is about the most general form i know of. –  kutschkem May 28 at 11:50

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$.

share|improve this answer
    
For a non-trivial example, see this proof of the AM-GM inequality. –  Brad May 28 at 0:50
    
In my opinion it's better not to use this example because it could be done via a normal 'add one term at a time' induction. –  user21820 May 29 at 4:34

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.

share|improve this answer

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.

share|improve this answer

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".

share|improve this answer

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.

share|improve this answer
    
There's other minor details such as the definition of "admitting a proof," but they are technicalities. The particular version I am using here is actually a First Order Logic proof, which is the most generally accepted form of proofs. Others such as Second Order Logic can actually turn out to be unprovable! –  Cort Ammon May 28 at 18:23
1  
Here's a MathJax tutorial :) –  Shaun May 28 at 18:40
    
Thanks! I'll have to update it. A few blackboard-font characters and a proper prime symbol do amazing things to clarify. –  Cort Ammon May 28 at 19:13
1  
Mathematical induction is emphatically not based on group theory. –  goblin May 29 at 7:57
    
What on earth are you talking about? States? Transforms? "Reachable"? And what does any of this have to do with group theory? –  Jack M May 30 at 10:35

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.

share|improve this answer

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

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.