Using generating functions to prove that the only sequences which are their own sequence of running averages are the constant sequences

Here's a problem that occurred to me yesterday: consider a sequence of real numbers a₀, a₁, a₂, ... . Let b_k = (a₀ + a₁ + ... + a_k)/(k+1) be the average of the first (k+1) of the a_i. When is a sequence equal to its own sequence of averages? That is, if we see a bunch of numbers, when is it true that every number we see is the average of all the numbers we've seen so far?

Of course the answer is the constant sequences. But can we prove this using generating functions?

It turns out we can. If we have

f(z) = a₀ + a₁ z + a₂ z² + ...

then

f(z)/(1-z) = a₀ + (a₀ + a₁)z + (a₀ + a₁ + a₂) z^2 + ... = b₀ + 2b₁ z + 3b₂ z^2 + ...

and let's call the right-hand side here g(z). What can we do to g(z) to transform it into

h(z) = b₀ + b₁ z + b₂ z² + ... ?

Well, a linear operator that takes the function (of z) z^k to the function (of z) z^k/(k+1) could be applied to g in order to get h. Clearly this is related to integration. In fact the operator

I φ(z) = (1/z) ∫₀^z φ(s) ds

does the trick. So we have

h(z) = I g(z) = (1/z) ∫₀^z f(s)/(1-s) ds.

But remember that we wanted the generating function h of the averages to be just the generating function f of the original sequence. So this gives

f(z) = (1/z) ∫₀^z f(s)/(1-s) ds

and this is in fact a differential equation. Multiply through by z and differentiate both sides to get

z f'(z) + f(z) = f(z)/(1-z).

A bit of rearranging gives

f'(z)/f(z) = 1/(1-z)

and we recognize that the left-hand side is the derivative of log f(z). Integrating both sides gives

log f(z) = log(1-z) + C

where C is a constant of integration, and finally we get f(z) = e^C/(1-z). But this is just the generating function of a constant sequence.

Heuristic derivation of the Prime Number Theorem

One way of stating the Prime Number Theorem is that the "probability" that a large number near x is prime is 1/log(x). (Here, as always, all logs are natural.)

A heuristic derivation of the prime number theorem, Frank Morgan, via Andrew Gelman, with some embellishment by me: let P(x) be the "probability" that a large integer x is prime. Then how do P(x+1) and P(x) compare? Say x is prime, which it is with "probability" P(x); it "divides" x+1 (and all larger numbers) with probability 1/x. (Of course, this doesn't actually make sense; the idea is that we're modeling the numbers divisible by x as a random set with density 1/x, which should have the same large-scale properties.) Other than this, x and x+1 are equally "likely" to be prime. So the function P satisfies

(*) P(x+1) = P(x) [P(x) (1 - 1/x)] + (1 - P(x)) P(x)

since x+1 is "prime" with probability P(x) (1-1/x) if x is "prime", and P(x) otherwise. Divide through by P(x) to get

P(x+1)/P(x) = P(x) (1-1/x) + (1-P(x))
P(x+1)/P(x) = 1 - P(x)/x.

Now, P(x+1) can be approximated by P(x) + P'(x), so we have

1 + P'(x)/P(x) = 1 - P(x)/x
P'(x)/P(x) = -P(x)/x

which has the general solution P(x) = 1/(C + log x).

This is a bit of a lie. For one thing, the difference equation (*) actually seems to have solutions that differ from those of the differential equation by a constant factor, which seems to depend on the initial conditions. (This amounts to changing the base.) For another thing, the assumption that x+1 might be divisible by x is, um, stupid if we're actually talking about prime numbers. (It's probably possible to rephrase this heuristic derivation as a rigorous result about random sets, though.) Still, it gets the prime number theorem to within a constant factor, which isn't bad for such a simple argument.

A surprise from differential equations

A problem which circulated among the grad students here at Penn today, which came up while somebody was teaching differential equations:

Consider the differential equation dy/dx = (y-1)². Separate variables and integrate both sides as usual; you get y(x) = 1 - 1/(x+C), where C is determined by the initial condition. Take the limit as x goes to infinity, and you get lim_{x -> ∞} y(x) = 1, regardless of C.

But now notice that dy/dx is positive for all y. (We're working over the reals here.) So if the initial condition is of the form y(x₀) = y₀ for some y₀ > 1, then we start at 1 and keep going upwards; how can the limit be 1?

Of cousre there's a mistake somewhere in here. But where is it? (I know the answer, but it took annoyingly long to figure out.)

edit: the differential equation was wrong.

N ways to solve a differential equation

Mark Dominus writes about how to solve the differential equation (f(x))² + (f^'(x))² = 1, which arises in the analysis of LC-circuits.
Go ahead, try it. There are at least four distinct solutions given there (bearing in mind the usual caveats about distinctness of solutions); I won't give any of them. If you want to know how I solved it, read Dominus' post, which ends with:

I would like to add a pithy and insightful conclusion to this article, but I've been working on it for more than a week now, and also it's almost lunch time, so I think I'll have to settle for observing that sometimes there are a lot of ways to solve math problems.

That's something definitely worth remembering.

As to why I ended up using a power series approach, which you'll see explained in the link: I'd been teaching the solution of differential equations by power series at the time, so it seemed natural to do that rather than to look for some kind of trick.