15
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ 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? $\endgroup$ – Daniel W. Farlow Mar 9 '15 at 17:57
  • $\begingroup$ @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. $\endgroup$ – k_g Mar 9 '15 at 20:24
  • $\begingroup$ @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. $\endgroup$ – Daniel W. Farlow Mar 9 '15 at 20:49
  • $\begingroup$ @crash I think the point is something that (while obviously vacuously true) is not obviously vacuously true. $\endgroup$ – k_g Mar 9 '15 at 20:59
  • $\begingroup$ @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). $\endgroup$ – Daniel W. Farlow Mar 9 '15 at 21:18
15
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @MarcvanLeeuwen Thanks! Fixed now. $\endgroup$ – Marm Mar 9 '15 at 14:19
  • $\begingroup$ All mice are grey? I can't see how one would have a base case or an inductive case for mice math... $\endgroup$ – AvZ Mar 9 '15 at 14:23
  • 1
    $\begingroup$ 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 $\endgroup$ – Ant Mar 9 '15 at 17:27
  • 2
    $\begingroup$ @Ant The statement $P(n)$ is "In every set of $n$ horses, every horse has the same colour." $\endgroup$ – David Richerby Mar 9 '15 at 21:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Mar 10 '15 at 5:27
9
$\begingroup$

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

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

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.