20 September 2011

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 a0, a1, a2, ... . Let bk = (a0 + a1 + ... + ak)/(k+1) be the average of the first (k+1) of the ai. 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) = a0 + a1 z + a2 z2 + ...

then

f(z)/(1-z) = a0 + (a0 + a1)z + (a0 + a1 + a2) z^2 + ... = b0 + 2b1 z + 3b2 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) = b0 + b1 z + b2 z2 + ... ?

Well, a linear operator that takes the function (of z) zk to the function (of z) zk/(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) ∫0z φ(s) ds

does the trick. So we have

h(z) = I g(z) = (1/z) ∫0z 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) ∫0z 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) = eC/(1-z). But this is just the generating function of a constant sequence.

6 comments:

Michael Albert said...

Sledgehammer, meet nut. :)

jonathan said...

Let me fix that for you...

Nuclear arsenal of hyper advanced alien civilization askign about R(6,6) meet nut.

Charles said...

This needs to be added to your "Generating Functions are Awesome" talk. Right this second. Hell, I use partitions of integers sometimes, and this seems cooler than that stuff as an example...

Michael Lugo said...

Michael and Jonathan: you're right, but I never claimed this was the most efficient method. Charles: I haven't given that talk in a while.

(A)natema said...

In the last equation a minus is missed:
log f(z) = -log(1-z) + C

joe random said...

How is any of this generating function witchcraft justified without falling back to an elementary proof that the sequence is constant? (Ie. you might want to assume f(z) has a non-zero radius of convergence, but why?)