Stating the induction hypothesis

477 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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