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.
Subscribe to:
Post Comments (Atom)
6 comments:
Sledgehammer, meet nut. :)
Let me fix that for you...
Nuclear arsenal of hyper advanced alien civilization askign about R(6,6) meet nut.
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 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.
In the last equation a minus is missed:
log f(z) = -log(1-z) + C
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?)
Post a Comment