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

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

-
What does $\lim_{n\to\infty}P(n)$ mean? Boolean statements do not form a metric space, at least not one that makes sense in this context. The problem is not with $\lim_{n\to\infty}P(n)$ (as this is not what you are looking at) but that just because every term in a sequence has a certain property (which you can prove by induction), we cannot assume that the limit has this property (nor do I see any reason to think we could). –  Alex Becker Jan 11 '12 at 8:22
@David : The result is true for any $n$ however large, but it is not necessarily true for $\infty$ because $\infty$ is not a natural number. So I fail to understand where there is a dilemma here. I guees looking at definition of uniform convergence of function sequences gives a good idea of how we interpret and use the concept of infinity. –  Rajesh D Jan 11 '12 at 8:28
@Alex: yeah, I know I was being a little loose with the notation. By saying "$\lim_{n\to\infty}P(n)$ is true" I didn't literally mean taking the limit of the boolean statement, but rather that $P(n)$ continues to be true in the limit as $n$ goes to infinity. Of course $P(n)$ needs to be some sort of statement for which it is meaningful to take that limit. As for your last sentence, I think you've identified my issue: it seems very natural to me that if every term in a sequence has a property, then so does the limit, and I'm looking for an understanding of why that isn't true. –  David Z Jan 11 '12 at 8:46
@David : You may sort out the issue without taking any example, but i think reading about uniform and nonuniform convergence of function sequences will do a lot good Please –  Rajesh D Jan 11 '12 at 9:07

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.

-

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

-
+1, no that is not the trivial case but the main point of induction. The assumptions for induction is that the statement is true for finite case. Once that the statement is no longer about a finite case the assumption is false and any result true or false can be derived. –  Arjang Jan 11 '12 at 11:45

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.

-

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.

-
Do you have a link to those two proofs? You've piqued my curiosity. –  JessicaK Dec 12 '13 at 1:20
Dear @JessicaK: You can find a proof of the second one in this pdf (last section) –  Bruno Joyal Dec 12 '13 at 3:44

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.

-