Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I am trying to understand why induction is valid. For instance why would this 'proof' not be valid under the principle of proof by induction ? :
$$ \sum_{k=1}^{\infty} \frac{1}{k} \lt \infty$$ because using induction on the statement $$S(n) = \sum_{1}^{n} \frac{1}{k} \lt \infty$$ - "$S(1) < \infty$ is true and "$S(n) < \infty$" implies "$S(n+1) < \infty$" since $S(n+1) \lt S(n) + \frac{1}{n}$
With induction, you can only prove $S(n)$ is true for all positive integers $n$. However, even though $S(n)$ is true for arbitrarily large $n$, the statement "$S(\infty)$" does not follow from induction because $\infty$ is not a positive integer.
The same proof shows that the set of all positive integers is finite:
\begin{align} & \{1\} \text{ is finite.} \\ & \{1,2\} \text{ is finite.} \\ & \{1,2,3\} \text{ is finite.} \\ & \{1,2,3,4\} \text{ is finite.} \\ & \qquad \vdots \\ & \text{and so on.} \\ \text{Therefore } & \{1,2,3,4,\ldots\} \text{ is finite.} \end{align}
By induction you have proved that for all $n\in\mathbb Z^+$, $\displaystyle\sum_{k=1}^n\frac 1 k$ is finite, which is true. This is not the same as proving that $\displaystyle\sum_{k=1}^\infty\frac 1 k$ is finite...
I would add to the other comments that when you take the limit $<$ changes into $\le$. So by taking the limit you would get $\sum_{k=1}^\infty\frac{1}{k}\le\infty$, which is not particularly useful.
Other answers make the valid point that you can only deduce $( \forall n \in \mathbb N :P(n) )$ by induction, but not $ P(\infty) $ (though see footnote1). There is, however, another problem in your case:
Your “$ P $” does not have the same meaning in “$ P(n)$” (where $ n\in \mathbb N $) as it does in “$ P(\infty) $”.
This is confusing, as the notation is the same, but an infinite sum is defined as a limit while a finite sum is defined inductively. Because of this, induction tells us nothing about $ P(\infty) $.
1 You can sometimes deduce $P(\omega)$ when using transfinite induction, but that is a different technique and a different story.
A lot of people are talking about the meaning of $P(\infty)$, which I believe is something of a red herring: usually the symbol $\infty$ is a notational convenience, and has no meaning as a formal object.
In particular:
$\sum_{n=0}^\infty x_n$ means $\lim_{m\rightarrow\infty}\sum_{n=0}^m x_n$, where again, the limit towards $\infty$ has a precise mathematical meaning not involving the symbol $\infty$.
$x<\infty$ simply means that there is some $C\in\mathbb{R}$ such that $x<C$. Alternately, for an increasing sequence $x_n$, $\lim_{n\rightarrow\infty}x_n<\infty$ means that there is a $C\in\mathbb{R}$ such that $x_n<C$ for every $n$.
Now if you try to prove that there is some $C$ such that for every $m$, $\sum_{n=0}^m \frac{1}{n}<C$, you'll run into trouble: certainly there is some such $C$ for each $m$, but there is no $C$ that works uniformly for every $m$. Indeed, if $x<C$, then $x+\frac{1}{m}$ could very well be above $C$.
