Notation for the variable in the inductive step?

Question

Induction is usually used for statements like this:

$\forall n \in \mathbb{N}:~P(n)$

In the inductive step we assume that $P$ is true for some "arbitrary but fixed" $n$ or $k$. Is there a good and hopefully short mathematical notation for "Let $n$ or $k$ be an arbitrary but fixed integer"? I thought writing

$\forall n \in \mathbb{N}:~P(n)$ or

$\forall k \in \mathbb{N}:~P(k)$

in the induction hypothesis means "arbitrary but fixed" but that is the same statement we are trying to proof. So we were told in class writing this is incorrect.

Maybe my understanding of "forall" and "arbitrary but fixed" is wrong but if they are the same then why can't we write $\forall n \in \mathbb{N}:~P(n)$? And if "forall" and "arbitrary but fixed" aren't the same why can we just redefine n (I read switching the variable is just for clarity but you could use n twice Why do we use another variable in the inductive step of mathematical induction?)?

Thanks.

Answer 1

The principle of induction is that you can prove a statement of the form $\forall n \in \mathbb N : P(n)$ by proving $$P(0) \wedge \forall k \in \mathbb N: (P(k) \implies P(k+1))$$ instead (or shifted versions of this to start your natural numbers with $1$ and so on). So you still have a statement that is universally quantified over the natural numbers but it’s a different statement (namely $P(k) \implies P(k+1)$ instead of $P(n)$). This new proof is often significantly easier.

Now, to prove something of the form $\forall x \in X : (P(x) \implies Q(x))$ (where $Q(x) :\equiv P(x + 1)$ in this case), we assume that we have an element $x$ that satisfies $P(x)$ and we show that in this context, $Q(x)$ is satisfied as well. This context of assumptions has no formal notation in traditional mathematics but it is written in natural language instead. (An exception might fields that study proofs and systems of reasoning but even there natural language is generally used for the meta theory.) The benefit of this is a better flow of the text and more flexibility in the amount of details you give.

For induction in particular, the right way is to clearly mark your induction hypothesis, (i.e. that $k \in \mathbb N$ and $P(k)$), often by simply writing “Induction hypothesis” in front of it. Added later: Also note that you need to show $\forall k \in \mathbb N: (P(k) \implies P(k+1))$ when using induction which does not have $\forall k \in \mathbb N : P(k)$ as a sub-statement (the parentheses are placed differently), so $\forall k \in \mathbb N : P(k)$ makes no sense as the induction hypotheses.

Answer 2

When you write $\forall n P(n),$ then $n$ is an arbitrary but variable natural number: you are, literally, making a statement for all natural numbers at once. When you write “suppose $k$ is such that $P(k)$ holds”, you are only assuming $P$ for one number. It is in this sense that $k$ is “fixed.”