Intereting Posts

How to Double integrals
Prove that 2 students live exactly five houses apart if
How prove this $\prod_{1\le i<j\le n}\frac{a_{j}-a_{i}}{j-i}$ is integer
Why exponential function on p-adic numbers is meaningless?
Sum of power functions over a simplex
Polarization: etymology question
Game theory – self study
Can mathematical inductions work for other sets?
Real life examples for eigenvalues / eigenvectors
The limit of sin(n!)
Gambling puzzle
How to write \mathcal letters by hand?
Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$
If a commutative ring is semiprime and its prime ideals are maximal then it is von Neumann regular (absolutely flat).
Locus of intersection of two perpendicular normals to an ellipse

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

- Coloring dots in a circle with no two consecutive dots being the same color
- If $p$ divides $a^n$, how to prove/disprove that $p^n$ divides $a^n$?
- Expression from generators of Special Linear Groups II
- Maximization with xor operator
- Probability for having consecutive success in an experiment
- Basic proof by Mathematical Induction (Towers of Hanoi)

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?

- Strong Induction proofs done with Weak Induction
- Prove the following (algebra of polynomials)
- Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.
- $k$-element subsets of $$ that do not contain $2$ consecutive integers
- Solve recursion $a_{n}=ba_{n-1}+cd^{n-1}$
- Proof that every odd integer is a difference of two squares
- Proof by Induction: Solving $1+3+5+\cdots+(2n-1)$
- Mathematical induction - what makes it true?
- Prove -n^2 diverges to negative infinity
- If two coins are flipped and one gets head, what is the probability that both get head?

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.

- Let $X$ be a compact metric space. If $f:X\rightarrow \mathbb{R}$ is lower semi-continuous, then $f$ is bounded from below and attains its infimum.
- formalize definition of topology
- Show that $\sum_{n = 1}^\infty n^qx^n$ is absolutely convergent, and that $\lim_{n \rightarrow \infty}$ $n^qx^n = 0$
- Definition of a nowhere dense set
- Find the sum of $-1^2-2^2+3^2+4^2-5^2-6^2+\cdots$
- Your favourite application of the Baire Category Theorem
- Why is Skolem normal form equisatisfiable while the second order form equivalent?
- Does the fact that $\sum_{n=1}^\infty 1/2^n$ converges to $1$ mean that it equals $1$?
- Inside a card deck there are 52 cards with 4 colors, 13 cards for each color
- Showing a metric space is bounded.
- Is there a characterization of groups with the property $\forall N\unlhd G,\:\exists H\leq G\text{ s.t. }H\cong G/N$?
- Can you raise a number to an irrational exponent?
- Reference request: toric geometry
- Example of a subgroup for normality
- Is there a vector space that cannot be an inner product space?