# Why is this 'Proof' by induction not valid?

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}$

• Read the principle of mathematical induction again. The conclusion only says $P(n)$ is true for every integer $n$, which is very different from $P(\infty)$ being true. – dezdichado Dec 21 '16 at 4:01
• This is one of my favourite mathematical errors. A thing and its limit need not have anything in common. You can build a hollow house out of solid bricks. – Eric Lippert Dec 21 '16 at 11:03
• Maybe not quite a duplicate, but strongly related Why doesn't induction extend to infinity?. – Marc van Leeuwen Dec 21 '16 at 11:45
• The question, and in particular the final line, is (also) confused about whether $S(n)$ designates a value or a proposition. – Marc van Leeuwen Dec 21 '16 at 11:49
• You also need to make very sure that you're not treating infinity like a number just because it is on the right of an inequality. By "the infinite sum is less than infinity" we are not actually comparing two numbers. This is just a convenient shorthand for there exists a number b (for "bound") such that every finite sum is less than b. – Eric Lippert Dec 21 '16 at 23:00

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.

• Also the statement $S(n)$ is meaningless for finite $n$; $<\infty$ does not say anything at all about a finite sum of real numbers. – R.. GitHub STOP HELPING ICE Dec 22 '16 at 23:33
• It's not meaningless, it's just TRUE. – Tom Church Jan 11 '17 at 18:50
• @R..: “$<\infty$ ” does not say anything in any notation with which I am familiar. More pertinent is that the definition of $S(\infty)$ is not the same as the definition of $S(n)$ for $n \in \mathbb N$. And in the latter case, of course, as Tom Church says, $S(n)$ is true. – PJTraill Oct 12 '17 at 19:34

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}

• This is a good start of an answer but I think you need to elaborate a little more on why it doesn't work. – Q the Platypus Dec 21 '16 at 6:11
• This still creeps me out because of the time when I was stupid enough to try to reason with an anti set theory crank. – Carsten S Dec 21 '16 at 15:07
• I see what you're going for, but your claim doesn't match your proof. You have shown through induction that for n > 0, {1, ..., n} has a cardinality of n. – Kjata30 Dec 21 '16 at 19:34
• @Kjata30 : I'm not following you. The idea is that if you add one more element to a finite set, you get a finite set; therefore every initial segment of the set of all positive integers is finite. – Michael Hardy Dec 22 '16 at 18:35

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

• $\lim_{n\to \infty}$ is the same as any other limit if you consider $\infty$ as an element in the one-point compactification of ${\bf N}$. You can do very similar things with nets. Personally, I think when we have a fixed sequence under consideration, it is enough to write $\lim_n$ without using the symbol $\infty$. – tomasz Dec 23 '16 at 0:29
• The same is true about $\lim_{n\to \infty} x_n<\infty$ -- you just need to consider ${\bf R}$ as a subset of its two-point compactification. If you don't, $x<\infty$ is completely meaningless: any number is less than infinity. – tomasz Dec 23 '16 at 0:31
• It's true that $\infty$ can be given meaning with enough (not that much) work, in a similar way that $dy/dx$ can be seen as an actual fraction in certain settings. I'm not sure that introducing limits in the context of the one-point compactification of $\mathbb{N}$ is the right pedagogical move though. – cody Dec 23 '16 at 14:25