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.

Learning about proof by induction, I take it that the first step is always something like "test if the proposition holds for $n = \textrm{[the minimum value]}$"

Like this:


Prove that $1+2+3+...+n = \frac{n(n + 1)}{2}$ for all $n \ge 1$.

Test it for $n = 1$:

$$n = \frac{n(n + 1)}{2} \implies 1 = \frac{2}{2}\textrm{, which holds.}$$

* The rest of the proof goes here *


So, I do it all the time (like a standard). But I never really thought about why. Why do I do such test? I can see that if the test does not hold, it cannot be proven by induction, I guess. But is there another reason we do this?

share|improve this question
2  
seems like if you want to prove something from here to infinity checking "here" is a good first step... but I don't know a formal name for that. –  Grady Player Dec 1 '13 at 1:12
    
Here - "the least element" maybe @GradyPlayer. Honestly I think that you couldn't comprehensively conclude that the expression is true for the entire set of numbers. –  Zhoe Dec 1 '13 at 1:14
    
IH: All sets of $n \ge 4$ lines on the plane intersect at a single point. If it holds true for $n\ge 4$ points, then it holds true for $n+1$ points since the first $n\ge 3$ points intersect at a point and so too do the last $n$ lines and the two intersection points must be the same point. Therefore, all lines on the plane intersect at a single point. –  Neil G Dec 1 '13 at 3:26
3  
A row of dominos can't fall if none of them are pushed. –  L. F. Dec 1 '13 at 13:17

9 Answers 9

up vote 47 down vote accepted

Imagine a pond with an infinite linear progression of lily pads. You have a frog who, if he hops on one pad, he is guaranteed to hop on the next one. If he hops on the first pad, he'll visit them all. But if he never makes the first lilypad, all bets are off.

share|improve this answer
18  
He’s up a creek without a pad? –  Brian M. Scott Dec 1 '13 at 1:27
2  
Either that or the resident cottonmouth got a springy meal. –  ncmathsadist Dec 1 '13 at 1:29
1  
@BrianM.Scott ....brilliant! –  Tom Dec 1 '13 at 1:31

We have to test the "base case" because otherwise we could "prove" things by induction that aren't true. For instance: let's "prove" that the sum of the first $n$ even numbers is odd. Certainly if $S = 2+4+\cdots+2n$ is odd, then $2+4+\cdots+2n+(2n+2) = S + 2n+2$ is also odd, since an even number plus an odd number is odd.

So by "induction", the sum of the first $n$ even numbers is odd.

Of course this is false, and the reason we got something false is that we didn't verify that the base case holds (it doesn't).

share|improve this answer
    
Nice example! It's non-trivial but clearly shows what is wrong. –  CompuChip Dec 1 '13 at 11:30

The induction proof is, in a metaphor, a game of dominos. Your goal is to make the pieces fall over, where if the $n$th domino falls, so will the $(n+1)$st. However, if you don't knock down the beginning domino, none may fall over.


An example of what goes wrong without appropriate base case...

Claim: For all $n \in \Bbb{N}=\{1, 2, 3, ...\}$, $n \geq 1000$.

Proof without base case: If $n \geq 1000$ the $n+1 > n \geq 1000$.


An example of what goes totally wrong...

Claim: For all $n \in \Bbb{N}$, $n > n$.

Proof without base case: If $n > n$, then by adding $1$ to both sides we see $n+1>n+1$. Therefore, by baseless induction, we've "proved" the claim.

share|improve this answer
    
Snicker.......... –  ncmathsadist Dec 1 '13 at 1:25
    
It might help to explain why the statement isn't true if your base case is n=1000. Other than the obvious.... how can someone know their base case is appropriate. For example, $n! \ge e^n$ (for sufficiently large $n$) however $n=0$ is a horrible base case. –  Squirtle Dec 1 '13 at 5:09

Let's take your example and modify it slightly:

Prove that $1+2+\cdots+n=\frac{n^2+n+1}{2}$ for all $n\ge 1$.

Let $P(n)$ be the statement "$1+2+\cdots+n=\frac{n^2+n+1}{2}$". Then you need to show that $P(n)$ implies $P(n+1)$. Substituting $n+1$ for $n$ we find that $$ P(n+1) =\frac{n^2+3n+3}{2} $$ Now let's establish the inductive step, that is, that we can use $P(n)$ to establish $P(n+1)$. $$ \begin{align} 1+2+\cdots+n+(n+1) &=(1+2+\cdots+n)+(n+1)\\ &= \frac{n^2+n+1}{2}+(n+1)&\text{by the inductive hypothesis}\\ &= \frac{n^2+3n+3}{2}&\text{as required} \end{align} $$ So we can conclude the highlighted statement. Sort of. Except for the fact that $P(1)$, the base case, sinply isn't true, since it asserts that $$ 1=\frac{1^2+1+1}{2} $$ As has been noted before, if you can't get the first domino to topple, none of the rest will, either.

share|improve this answer

Let's prove that all objects in the universe are the same color. We'll prove by induction that given any set of $n$ objects, all of them are the same color.

Inductive step: Given a set $\{1, ... n+1\}$ of objects, we know that $\{1, ... n\}$ are all the same color $c_1$, and that $\{2, ... n+1\}$ are all the same color $c_2$. But if $n\geq 2$ these two sets overlap, so $c_1$ and $c_2$ must be the same. Therefore $\{1, ... n+1\}$ are all the same color.

Base case: If $n=1$, it's obvious. If $n=2$, then the two elements are the same color because... er...

Base case left as an exercice to the reader.

share|improve this answer

To see why we need the base case, consider the following proposition:

Proposition: $\forall n \in \mathbb{N}, n = 0$

Proof: Assume this property holds for all $m \leq k$, and consider $n = k+1$.

= $k + 0$ (By inductive hypothesis noting that $1 \leq k$ is the smallest element of $\mathbb{N}$)

= $0 + 0$ (By inductive hypothesis)

= $0$

Hence the proposition holds for all $n \in \mathbb{N}$

QED

The problem with this proof is that I haven't actually explicitly shown there exists any integer in $\mathbb{N}$ that is equal to zero; moreover, and more importantly, I can never find such an integer. As such, given that I cannot establish the base case I cannot conclude the proposition is true.

share|improve this answer

Its common this question because the introduction to inductive proof is teached very axiomatically ("proof for n=1, then proof for n+1").

An inductive proof is where one proves that a set $A$ is inductive. A set $A$ is inductive if satisfies that

  • $1\in A$
  • $n\in A \Rightarrow n+1 \in A$

If $A$ is inductive, then $A=\mathbb N$

In your example, what it is really being proved is that $A=\{n\in N:1+2+3+...+n = \frac{n(n + 1)}{2}\}$ is inductive. That is, $A=\{n\in N:1+2+3+...+n = \frac{n(n + 1)}{2}\}=\mathbb N$

Notice that if $1\not\in A$ then we can not say that $1\in A \Rightarrow 1+1\in A$, hence $A\neq \mathbb N$

share|improve this answer
    
The definition might change if you treat $0$ as a natural number. Then $A$ is inductive if $0\in A$ –  AndrewGSM Dec 1 '13 at 1:49

The first test assures that it will be true for the minimum value (could be $0, 1, 2$ or anything). The subsequent proof that you do proves that if it is true for any natural number, it will be true for the next number as well.

So, lets say $1+2+3+...+n=\frac {n(n+1)}{2}$ is true for $n=1$ (which it is), then if you can prove that if it is true for any natural number, it will be true for the subsequent one as well, then this will be true for 2 as well. If it true for 2, it will be true for 3 and so on..

The first test is simply a starting point, that's all.

share|improve this answer

The base case part of an inductive proof shows that the statement you are trying to prove holds for some number in the series, in your example,

Prove that $1+2+3+...+n=\frac{n(n+1)}{2}$ for all $n$ greater than or equal to $1$

the first number in your proof would be $1$. But you could also show that this sequence holds for all $n$ greater than or equal to $2$ and it would be a valid proof.

In the inductive step, we show that if the statement holds for some number $P(n)$, then the statement also holds for $P(n + 1)$, the next number in the series. In the above example, you already showed that the statement holds for $n = 1$, which is some number $P(n)$, therefore if we can show that the statement is also valid for $P(n + 1)$, then we would know that the statement is valid for every number greater than $1$ by the axiom of induction.

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.