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


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.

13 September 2011

The quadratic equation, Dr. Seuss style

I've been busy, but here's a quick one: The quadratic equation, Dr. Seuss style, by Katie Benedetto. My favorite stanza:

Each value there was, well she renamed each one
Claiming that nice names would make this more fun.
“Variables, well, they’re whatever we wish
So like one, two, red, blue, I’ll call this one “fish”!

This is the antidote to if the IRS had discovered the quadratic formula.