Why doesn't induction extend to infinity? (re: Fourier series)

Question

While reading some things about analytic functions earlier tonight it came to my attention that Fourier series are not necessarily analytic. I used to think one could prove that they are analytic using induction

1. Let $P(n)$ be some statement parametrized by the natural number $n$ (in this case: the $n$th partial sum of the Fourier series is analytic)
2. Show that $P(0)$ is true
3. Show that $P(n-1)\Rightarrow P(n)$
4. (Invalid) conclusion: $P(n)$ continues to be true as we take the limit $n\to\infty$^*

Why exactly is the conclusion not valid here? It seems very strange that even though $P(n)$ is true for any finite $n$, it ceases to be valid when I remove the explicit upper bound on $n$. Are there circumstances under which I can make an argument of this form?

---

Example of invalid proof: Define the truncated Fourier series $F_n(x)$ as the partial sum

$$F_n(x) = \sum_{k=0}^{n} A_k\sin\biggl(\frac{kx}{T}\biggr) + B_k\cos\biggl(\frac{kx}{T}\biggr)$$

where $A_k$ and $B_k$ are the Fourier coefficients for some arbitrary function $f$. Using the facts that $\sin(t)$ and $\cos(t)$ are analytic, and that any linear combination of analytic functions is analytic:

1. $P(n)$ is the statement "$F_n(x)$ is analytic"
2. $F_0(x)$ is clearly analytic because it is a linear combination of sine and cosine functions

3. $F_n(x)$ can be written as the linear combination

   $$F_{n}(x) = F_{n-1}(x) + A_n\sin\biggl(\frac{nx}{T}\biggr) + B_n\cos\biggl(\frac{nx}{T}\biggr)$$

   So if $F_{n-1}(x)$ is analytic, $F_n(x)$ is analytic.

4. $F(x) \equiv \lim_{n\to\infty} F_n(x)$ is analytic. But $F(x)$ is the Fourier series for $f$; therefore, the Fourier series for $f$ is analytic.

---

^*I'm assuming that $P(n)$ is a statement about some sequence which is parametrized by $n$ and for which taking the limit as $n\to\infty$ is meaningful

Answer 1

A trivial case where $P(n)$ is true for all $n\in\mathbf N$ but $P(\infty)$ is false is the statement "$n$ is finite".

Answer 2

Here is a quote from B. Russell's Introduction to mathematical philosophy, pages 27-28, that I think describes well this limitation of induction:

Mathematical induction affords, more than anything else, the essential characteristic by which the finite is distinguished from the infinite. The principle of mathematical induction might be stated popularly in some such form as "what can be inferred from next to next can be inferred from first to last." This is true when the number of intermediate steps between first and last is finite, not otherwise. Anyone who has ever watched a goods train beginning to move will have noticed how the impulse is communicated with a jerk from each truck to the next, until as last even the hindmost truck is in motion. When the train is very long, it is a very long time before the last truck moves. If the train were infinitely long, there would be an infinite succession of jerks, and the time would never come when the whole train would be in motion. Nevertheless, if there were a series of trucks no longer than the series of inductive numbers..., every truck would begin to move sooner or later if the engine persevered, though there would always be other trucks further back which had not yet begun to move.

There are contexts in which a statement $P(n)$ can be proved for all $n\in\mathbb N$ by induction, and has a counterpart $P(\infty)$ that is false. In other contexts, $P(\infty)$ may be true. But even then, induction on $\mathbb N$ does not prove the $P(\infty)$ case.

Getting back to limits of functions, note for example that:

• A finite sum of continuous functions is continuous.

• A pointwise convergent series of continuous functions need not be continuous.

• But, a uniformly convergent series of continuous functions is continuous.

So in this case, going from finite sums to infinite series requires new tools, different types of convergence, to obtain the desired properties. As for real analytic functions, I don't know what can be said along these lines. For complex analytic functions there are nicer results, such as the fact that a locally uniformly convergent sequence of complex analytic functions is complex analytic. In the real case, to give a stark contrast, every continuous function on a bounded interval is a uniform limit of polynomials (as analytic as you can get), but there are continuous functions that are differentiable nowhere. Similarly, a continuously differentiable function of period $2\pi$ is the uniform limit of its Fourier series, but continuously differentiable functions need not even be twice differentiable, let alone analytic.

Answer 3

An example where "$P(n)$ for all $n$" does not imply $P(\infty)$, not from the realm of analysis:

Let $P(n)$ be "the set $\cup_{k=1}^n [\frac1k, 1]$ is closed." Clearly it is true for every positive integer $n$, since the union is $[\frac1n,1]$.

But $\cup_{k=1}^\infty [\frac1k, 1] = (0, 1]$ is not closed, so $P(\infty)$ is false.

Answer 4

With all of these counter-examples, perhaps it would be important to mention that there is a version of induction which "extends to infinity". It is called Transfinite induction.

Transfinite induction can be used to prove some pretty surprising things: for instance, it can be used to show that there exists a subset of $\mathbf R^2$ which intersects every line in exactly 2 points. Or that $\mathbf R^3-\{0\}$ can be partitioned into disjoint lines.

Answer 5

How about this?

• $\dfrac 12$ is not an integer.

• $\dfrac 12 + \dfrac 14$ is not an integer.

• $\dfrac 12 + \dfrac 14 + \dfrac 18$ is not an integer.

• $\sum_{i=1}^n \dfrac{1}{2^i}$ is not an integer.

Therefore $\displaystyle \lim_{n \to \infty}\sum_{i=1}^n \dfrac{1}{2^i} = 1$ is not an integer.

Answer 6

I have an example from the realm of geometry. Consider a following sequence of triangles. Take any triangle and find midpoints of two of its sides and connect them. They will form a smaller triangle. This way you obtain an infinite sequence of triangles of decreasing sizes.

However, the limit of the sequence - a single point - is not a triangle. So for any finite $n$, $A_n$ is a triangle but the limit of $A_n$ as $n$ grows is not.

Answer 7

Here is another example: Can an infinite sum of irrational numbers be rational?

By induction, you can show that the sum of any finite number of terms is irrational, yet the infinite sum is rational.

Answer 8

Here is another example illustrating this: $\cap_{i=1}^n{B_i}\neq\emptyset$.

But $\cap_{i=1}^\infty{B_i}=\emptyset$

$B_1=\{1,2,...\}\\ B_2=\{2,3,...\}...\\ B_n=\{n,n+1,...\}$

Then:

$\cap_{i=1}^n{B_i}=B_n$

Yet:

$\cap_{i=1}^\infty{B_i}=\emptyset$

Since: Let $x\in \cap_{i=1}^\infty{B_i}$

Then $x\in B_x\implies x\notin B_{x+1}\implies x\notin \cap_{i=1}^\infty{B_i}$