# Induction - Examples where the induction step is correct but the base case is always wrong [duplicate]

I'd like to present to my students some induction examples that always satisfy the inductive step but never the base case. It could be for natural numbers, graphs or anything else.

## marked as duplicate by bof, Milo Brandt, dustin, user147263, Daniel W. FarlowMar 10 '15 at 0:27

• Am I missing something? I don't really see too much value in examples of induction arguments where the base case is clearly false. Since the inductive step is $P(k)\to P(k+1)$ and is always true for a false hypothesis, it would seem to be more valuable to consider fallacious induction arguments where there's a subtle flaw in the induction step. Or am I wrong? – Daniel W. Farlow Mar 9 '15 at 17:57
• @crash I think the OP is looking for something where $P(k+1)$ "mathematically follows" from $P(k)$ rather than just being logically implied. For example, It is the 30th of February $\iff$ I'm a penguin wouldn't count because it is of little teaching value. – k_g Mar 9 '15 at 20:24
• @k_g How, then, would you start off with a false base case? The first implication would be vacuously true, just as the one you mentioned. – Daniel W. Farlow Mar 9 '15 at 20:49
• @crash I think the point is something that (while obviously vacuously true) is not obviously vacuously true. – k_g Mar 9 '15 at 20:59
• @k_g I don't understand that comment. See my answer as to why I made the first comment I made (I elaborate on my comment at the beginning of my answer). What I outline at the beginning of my answer is probably what the people who deemed my comment helpful were thinking (I imagine so, at least). – Daniel W. Farlow Mar 9 '15 at 21:18

Some simple examples:

• $2.5 + k$ is a natural number for all $k \in \mathbb N$

• $\int_1^{\infty} \frac{1}{xn} dx<\infty$ for all $n\in \mathbb N$

• $\mathbb R^{2^n}$ is countable for all $n\in \mathbb N$

• 7 divides $10^n$

The following example might also be interesting for you:

Its an example where the induction step goes wrong.

Statement: All horses have the same color

1) Base case: This is obviously true

2) Induction step: Lets consider $(n+1)$ horses. If we remove one horse, then the induction hypotheses tells us that the remaining $n$ horses have the same color. Now we put the horse back and remove another one. Applying the induction hypotheses once again yields that all $(n+1)$ horses have the same color. However this argumentation does not work for $n=1$ to $n=2$ because we need one horse which "connects" both horses.

• @MarcvanLeeuwen Thanks! Fixed now. – Marm Mar 9 '15 at 14:19
• All mice are grey? I can't see how one would have a base case or an inductive case for mice math... – AvZ Mar 9 '15 at 14:23
• I believe that the "all horses have the same color " argument is flawed not only because the base case fail. The first thing that strike is: What exactly is $P(n)$ that you're trying to prove? If it is "the first $n$ horses have the same color", then your inductive step is flawed. If it is "All grouping of $n$ horse is such all the horses have the same color", then it's true that $P(2)$ implies $P(n)$ for all $n$, but $P(2)$ is already equivalent to "all horses have the same color" so you don't really need the inductive step – Ant Mar 9 '15 at 17:27
• @Ant The statement $P(n)$ is "In every set of $n$ horses, every horse has the same colour." – David Richerby Mar 9 '15 at 21:57
• The number of edits on this answer has triggered a system flag. See this recent Meta thread for discussion/tips/whatnot about why this is frowned upon, and what can you do to avoid the problems. – Jyrki Lahtonen Mar 10 '15 at 5:27

Let me expand on why I made the comment on your question (and I will follow this up with (1) what I think is a meaningful example to your question and (2) an example of a subtle flaw in an induction proof).

Reason for comment: Notice that any statement that is never true will satisfy your conditions for an example. That is, we would have the following for some statement $P(n)$:

• Base case: $P(m)$ is false. [This is clearly the case because we have chosen a statement $P(n)$ that is false for all of $n$.]
• Inductive step: $P(n)\to P(n+1)$ is always true because $P(n)$ is always false. [This is because an implication is only false when the hypothesis is true and the conclusion is false.]

Can you now see why I said such examples are likely to be of little value?

Example for your question: The most meaningful (this is admittedly a horridly subjective term) example I could think of off the top of my head was the following, where $P(n)$ denotes the following statement for all $n\in\mathbb{N}$: $$P(n) : \text{The nth prime number is odd.}$$ Well, the base case $P(1)$ is clearly false (the first prime number, $2$, is not odd). Almost all implications of the form $P(n)\to P(n+1)$ are true and not in a vacuous way (that is, the only vacuous implication will be when $P(1)\to P(2)$).

Subtly flawed induction proof: Try to find the flaw in the following "proof" that $a^n=1$ for all nonnegative integers $n$, whenever $a$ is a nonzero real number.

Base case: $a^0=1$ is true by the definition of $a^0$.

Inductive step: Assume that $a^m=1$ for all nonnegative integers $m$ with $m\leq k$. Then notice that $$a^{k+1}=\frac{a^k\cdot a^k}{a^{k-1}}=\frac{1\cdot 1}{1}=1.$$ Can you spot the flaw? If not, here it is (hover cursor over grayed out area to reveal answer):

The flaw occurs in the inductive step where we implicitly assume that $n\geq 1$ in order for us to talk about $a^{n-1}$ in the denominator; otherwise, the exponent is not a nonnegative integer, meaning we cannot apply the inductive hypothesis. We checked the base case only for $n=0$; thus, we are not justified in assuming that $n\geq 1$ when we try to prove the statement for $n+1$ in the inductive step. It is exactly at $n=1$ that the proposition breaks down.

• This is soooooo good! Thanks for it! It'll go in my Discrete Mathematics problem sessions! :) – yo' Mar 9 '15 at 22:10
• @yo' Thanks! Glad you liked it. :) – Daniel W. Farlow Mar 10 '15 at 0:20

All natural numbers are greater than 1.

$2+4+6+8+\cdots+2n$ is odd for any natural number $n$.

$n(n+1)$ is always odd.

So we need a false statement of some sort. A simple example could be a "proof" that $\mathbb{N}=\{1\}$. If $n=n-1$, then $n+1=n-1+1=n$. But of course there is no base case to use here.

If you want to talk graphs, you could say something like, a tree $T$ on $n$ vertices has $n$ edges. Suppose you have a tree $T$. Find a leaf, remove it to obtain a tree on $n-1$ vertices (and so $n-1$ edges). Thus $T$ has $n$ edges.

You can then use the above to "show" that for every planar graph with $v$ vertices, $e$ edges and $f$ faces, one has $v-e+f=1$. Suppose this is true for all planar graphs with fewer than $e$ edges. If $G$ is a tree, then $G$ has one face and so $v-e+f= n-n+1=1$.

If $G$ has a cycle, remove one edge from it. Then the resulting graph has one fewer edge and one fewer face, so $v-(e-1)+(f-1)=1$ and so $v+e-f=1$.

for an example $n(n+1)$ is always odd... if you assume $k(k+1)$ is odd then $(k+1)(k+2)=k(k+1)+2(k+1)$ but odd+even= odd so by induction it is true...but for $n=1$ it is not true...

Prove FLT false: $\ \forall n\in\Bbb N\!:\ (2^n a)^k + (2^n b)^k = (2^n c)^k,\, k\ge 3\$ is solvable for $\,a,b,c\in\Bbb N$