Intereting Posts

Proving $\sum\limits_{i=0}^n i 2^{i-1} = (n+1) 2^n – 1$ by induction
Is it possible that $(x+2)(x+1)x=3(y+2)(y+1)y$ for positive integers $x$ and $y$?
Simple to state yet tricky question
Is my Riemann Sum correct?
What are k-cycles?
Calculate $\int_0^1\frac{\log^2(1+x)\log(x)\log(1-x)}{1-x}dx$
When is there a ring structure on an abelian group $(A,+)$?
Show $T$ is compact
The length of an interval covered by an infinite family of open intervals
Matrix diagonalizable or not
Difference between ZFC & NBG
How to prove that there are finitely many $n$ such that $f(1+1/n) = \frac{1}{n+1}$?
Another way to express $\text{cis } 75^\circ + \text{cis } 83^\circ + \text{cis } 91^\circ + \dots + \text{cis } 147^\circ$
Real roots of a polynomial of real co-efficients , with the co-efficients of $x^2 , x$ and the constant term all $1$
Prove that $2^n +1$ in never a perfect cube

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?

- Prove by induction that for all $n$, $8$ is a factor of $7^{2n+1} +1$
- Prove that $1 + 4 + 7 + · · · + 3n − 2 = \frac {n(3n − 1)}{2}$
- Terminology re: continuity of discrete $a\sin(t)$
- Prove $n^2 > (n+1)$ for all integers $n \geq 2$
- How to prove that $\mathrm{Fibonacci}(n) \leq n!$, for $n\geq 0$
- Computing RSA Algorithm
- Prove that $\sum_{k=0}^n\frac{1}{k!}\geq \left(1+\frac{1}{n}\right)^n$
- If $n\ge2$, Prove $\binom{2n}{3}$ is even.
- Size of a union of two sets
- Can someone give me an example of a challenging proof by induction?

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.

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

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.

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.

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.

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.

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$

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.

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.

- Conjugacy Class in Symmetric Group
- Distance between triangle's centroid and incenter, given coordinates of vertices
- A module as an external direct product of the kernel and image of a function
- Prove this inequality: $\sum{\frac{1}{(x+2y)^2}} \geq\frac{1}{xy+yz+zx}$
- Convergence of the sum of two infinite series only at $x=\frac12$?
- Are there infinitely many primes next to smooth numbers?
- Sanity check on example 6.5 from “Counterexamples in probability and real analysis” by Wise and Hall
- The cone minus its apex deformation retracts onto its basis
- Cohomology group of free quotient.
- Proof that $\mathbb{R}^+$ is a vector space
- Showing the sum of a C* subalgebra and ideal is itself a C* subalgebra
- Prove $\lim_{x\to-2}\frac{x+8}{x+3}=6 $ using $\epsilon-\delta$
- Combinatorial Proof of Multinomial Theorem – Without Induction or Binomial Theorem
- If a function is bounded almost everywhere, then globally bounded?
- How can I prove that all rational numbers are either terminating decimal or repeating decimal numerals?