5
$\begingroup$

I would like to ask about the best way to state the induction hypothesis in a proof by induction.

Just to use a concrete example, suppose I wanted to prove that $n!\ge 2^{n-1}$ for every positive integer $n$.

Assuming that I have already verified the case $n=1$, which of the following statements of the induction hypothesis would be best to use, and, more importantly, are any of them unacceptable?

1) Let $n\in\mathbb{N}$ with $n!\ge2^{n-1}$.

2) Let $n!\ge2^{n-1}$ for some $n\in\mathbb{N}$.

3) Assume that $n!\ge2^{n-1}$ for some $n\in\mathbb{N}$.

4) Let $k!\ge2^{k-1}$.

(I realize that this is partly a matter of taste and style, and please note that I am not asking how to finish the inductive step.)

$\endgroup$
  • 3
    $\begingroup$ I'd go with (3). $\endgroup$ – Akiva Weinberger Aug 27 '15 at 20:24
  • $\begingroup$ I would also take (3)... So it is clear that it is the premise of the induction step... $\endgroup$ – Stephan Kulla Aug 27 '15 at 20:28
  • 3
    $\begingroup$ I would strongly avoid 3). To me it says assume there exists an $n$ such that $\dots$. Then $n$ has been quantified away and is no longer free. Something like suppose that $k$ is a natural number such that $\dots$ seems fine. $\endgroup$ – André Nicolas Aug 27 '15 at 20:30
  • $\begingroup$ It is important to have the word "assume", so (3). The other ones are somewhat confusing since "let" could lead the reader to think it is sufficient to find one value of $n$ or $k$ satisfying the inequality. $\endgroup$ – DirkGently Aug 27 '15 at 20:30
  • $\begingroup$ The inductive hypothesis is an assumption not a definition so (3) is the best way to state it, but you don't want to have the "for some" bit. You just want to assume $n! \ge 2^{n-1}$. $\endgroup$ – Rob Arthan Aug 27 '15 at 20:34
8
$\begingroup$

The Principle of Mathematical Induction says that for all "properties" $P$, $$\left(P(0)\land\forall k\in \mathbb N\left(P(k) \implies P(k+1)\right)\right)\implies \forall n\in \mathbb N(P(n)).$$

So you're basically asking how to write the $\forall k\in \mathbb N\left(P(k)\implies P(k+1)\right)$ bit.

It's a universal statement. It's common to start those by "Let $k\in \mathbb N$". Then you want to prove the conditional statement $P(k)\implies P(k+1)$. It's common to prove these by starting with "suppose $P(k)$ holds" (or some variation).

Wrapping it up, I'd write "Let $k\in \mathbb N$ and suppose that $P(k)$" or "Let $k\in \mathbb N$ be such that $P(k)$ holds" or some variation of this. This includes (1) and to some extent (4). I wouldn't use (2) or (3) because the word "some" strongly suggests existential quantification which isn't even present in the formulation of the Principle of Mathematical Induction used in this answer (which is the most common anyway).

$\endgroup$

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.