2
$\begingroup$

I never got a clear answer to this question in college. What happens in an induction proof if the assumption is wrong? For example, suppose we try to prove that $n^5$ > n! for n >= $2$ so we start out by stating that when n = $2$ it is true and in our proof, we assume that $n^5$ > n! and then try to show that it is also true for the n+1 case? Will something show up to invalidate the proof? If so where and how? Will it show us that the inequality will fail when n is $8$ or more or will it tell us it will fail but not inform us exactly where?

This might be an overly simple example so my more generic point is someone very sophisticated in math might be able to "hide" a flaw in their proof such that only another sophisticated math person might catch it, but to a not so obvious inequality like this one.

To me, it seems ok in an induction proof to show a specific case that works such as for n = $2$ and then try to prove it is true for all n, but to me is it NOT ok to assume that $n^5$ > n! for some arbitrary n because that is what we are trying to prove.

Obviously $n^5$ > n! will fail when n is $8$ or larger ($32,768$ is not larger than $40,320$).

$\endgroup$
  • $\begingroup$ "to me is it NOT ok to assume that $n^5$ > n! for some arbitrary n because that is what we are trying to prove." You don't assume $\forall n(P(n))$. You take an arbitrary $n\in \mathbb N$ and then assume $P(n)$, from this you can conclude $\forall n\in \mathbb N(P(n)\implies P(n))$, but never $\forall n\in \mathbb N(P(n))$. $\endgroup$ – Git Gud Oct 27 '14 at 20:36
  • $\begingroup$ You ask: "Will something show up to invalidate the proof?". The short answer is "yes". But then you ask "If so where and how?" So now I fall back on the longer anwer which is: the induction statement "if $n^4 > n!$ then $(n+1)^4 > (n+1)!$" is false, so if you show me what proof you have in mind, I (with enough work) should be able to you where it is invalid. But I cannot predict ahead of time where the invalidity of your proof will occur. I can't even predict where my calculus students will go wrong on their exams; their errors provide infinite amounts of amusement to me. $\endgroup$ – Lee Mosher Oct 27 '14 at 20:51
  • $\begingroup$ @LeeMosher Please share. $\endgroup$ – Git Gud Oct 27 '14 at 20:56
  • $\begingroup$ Would it help you if instead of "assuming $n^5 > n!$" we used the language "what if we assumed $n^5 > n!$ for some $n$" ? $\endgroup$ – DanielV Oct 27 '14 at 21:00
  • $\begingroup$ @DanielV That would be an incorrect use of the natural language as a translation of the beginning of the proof of $\forall n\in \mathbb N(P(n)\implies P(n+1))$. $\endgroup$ – Git Gud Oct 27 '14 at 21:01
2
$\begingroup$

If what you're assuming is wrong, then either the induction step or the initial condition is simply not possible to prove.

$\endgroup$
  • 1
    $\begingroup$ This is not the case--often, it is possible to prove $P(n)$ implies $P(n+1)$ even when $P(n)$ is never true! In fact, when $P(n)$ is false, $P(n) \implies P(n+1)$ is a tautology. By the principle of explosion, if you assume a falsehood, you can prove anything. $\endgroup$ – 6005 Aug 6 '15 at 20:25
  • $\begingroup$ @6005 Good point, I have updated the answer. $\endgroup$ – Alice Ryhl Aug 6 '15 at 20:26
1
$\begingroup$

In your example, trying to prove that $n^5 > n!$ (which is not true for all n), if we took for example $n = 100$, then $(n+1)^5$ would only be about five percent larger than $n^5$, while $(n+1)!$ would be 101 times larger than $n!$, so clearly the induction step would fail.

However, assume that I claim "for every $n ≥ 0$, $n! < 0$". This is of course false, but the induction step works: If this claim is true for an $n ≥ 0$, that is if $n! < 0$, then we also have $(n+1)! = (n+1)n! < 0$, therefore the claim is true for n+1 as well.

For an induction proof, you must prove that the claim $A (n_0)$ is true for some $n_0 ≥ 0$, and you must prove that A (n) implies A (n+1) for all $n ≥ n_0$, and then A (n) is true for all $n ≥ n_0$. Sometimes you can't prove the initial step A (n) for any n, sometimes the induction step fails.

$\endgroup$
  • $\begingroup$ This is not correct. For $n=100$, it is actually true that $n^5 > n! \rightarrow (n+1)^5 > (n+1)!$. That is because of vacuous implication. There is only 1 case for which $P(n) \implies P(n+1)$ is false, and that is $n=7$. $\endgroup$ – DanielV Aug 6 '15 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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