Question on induction technique

Question

When one uses induction (say on $n$) to prove something, does it mean the proof holds for all finite values of $n$ or does it always hold when even $n$ takes $\pm\infty$?

Answer 1

If n is a natural number, n can never take $\infty$ because $\infty$ is not a natural number. So the proven statement only is actually proven for finite values of n. When people say "it holds as n goes to $\infty$", what they are saying is that the statement holds for arbitrarily large natural numbers, which are still finite.

Answer 2

Regular inductive proofs work only over $\mathbb{N}$, the set of natural numbers. The proof that "inductive proofs work" depends on the well-ordering property of $\mathbb{N}$, and $\infty \not\in \mathbb{N}$. As people in the comments have pointed out, induction can be extended to other well-ordered sets as well. Regardless, it is meaningless to ask if a statement holds at $\infty$.

Answer 3

We want induction want to show that $n$ and $n+1$ satisfy the equation. However $n$ can only be defined by the set of all natural numbers $\mathbb{N}$ and can hold for only finite values. Thus, it cannot be taken to $\infty$ because $\infty$ is infinite and $n$ is finite. This also depends on the well-ordering property. In addtion, we can note that $\infty\notin\mathbb{N}.$

Answer 4

It is meaningless to say that "$n$ takes $\pm \infty$" so long as $n\in \mathbb{N}$ simply because $\pm \infty \not \in \mathbb{N}$. So if $n$ is finite then the Induction Principle says that the integer $n$ can be reached starting from $1$ (if the Induction Basis exists) in finitely many steps, however large. Hence one claims that for all $n\in \mathbb{N}$ the proposition holds, which as a corollary gives us the conclusion that the proposition holds for all finite $n$ since any finite $n$ is a member of $\mathbb{N}$.

Answer 5

As others have already shown, the proof will only hold for finite $n$. To provide a simple example, take the following theorem:

Let $A$ be a set and $a \notin A$. There is no bijection between $A$ and $A ∪ \{a\}$

This is true for finite sets and can easily be shown by induction on $|A|$, but is false for infinite sets.

Answer 6

Mathematical induction is based on two properties of the natural numbers. They are the Well-Ordering property (each non-empty subset of the natural numbers has a least element) and the fact that each element has a successor.

If we wish to establish that a proposition $P(n)$ is true for each $n \in \mathbb{N}$ such that $n \geq n_0$, we must first establish that $P(n_0)$ holds, which establishes that the set $S = \{n \in \mathbb{N}|~P(n)~\text{holds}\} \neq \emptyset$. We then show that $P(n) \Rightarrow P(n + 1)$, which demonstrates that if $n \in S$, then its successor $n + 1 \in S$. Since $n_0 \in S$, the fact that $P(n) \Rightarrow P(n + 1)$ for each $n \in S$ allows us to conclude that $n_0, n_0 + 1, n_0 + 2, \ldots \in S$. Therefore, $S = \{n \in \mathbb{N}|~n \geq n_0\}$. However, it does not demonstrate that $\infty \in S$ since $\infty$ is not the successor of any natural number.