New math problem
Let C(n) be the number of ways to write n as the sum of consecutive non-negative integers. The terms from C(0) to C(10) are 1, 2, 1, 3, 1, 2, 3, 2, 1, 3, 3. Find an ordinary generating function for C(n) in closed form, in terms of elementary functions if possible. Prove that the series 1/C(n) diverges. When about the series 1/(n C(n)). What is the ( Read more... )
sum_n C(n) z^n = 1 + sum_{k=1}^\infty z^{k(k+1)/2} / (1-z^k)
Proof: the sums which consist of one element are ∅, 1, 2, 3, 4, ...; these have OGF 1 + z + z^2 + ... = 1/(1-z).
The sums which consist of two elements are 1+0, 2+1, 3+2, ...; counting these by what they add up to, they have OGF z + z^3 + z^5 + z^7 + ... = z/(1-z^2).
Proceed like this for sums consisting of k elements, for each k. The 1 in front comes because I didn't count the empty sum.
That's sort of in terms of elementary functions. Now I claim that getting information about C(n) is "trivial", which is a lie. (I should note that if it were true, I wouldn't be able to get a PhD in this stuff.)
As for the order-of-magnitude estimates, I'm going to consider the "average value" of C(n) -- that is, let D(n) = C(1) + ... + C(n) and find an asymptotic form for D(n). There are n one-term sums which add up to at most n, (n-1)/2 two-term sums, (n-3)/3 three-term sums, and in general (n-Δ(k))/k k-term sums adding up to at most n. (Ignore rounding error, because I'm lazy.) We want to add up the number of k-term sums adding up to at most n, for k at most sqrt(2n) which is the maximal number of terms such a sum can have. Approximating Δ(k) by k^2/2, this sum can be approximated by the integral
\int_0^{\sqrt{2n}} (n-k^2/2)/k dk
which is, in turn, asymptotic to (n log n)/2. This agrees with some code I wrote that doesn't ignore the rounding error. So D(n) is asymptotic to (n log n)/2, and therefore C(n) is "on average" (log n)/2. If you go back to the claim that we're just counting odd divisors, then you can guess this; numbers near n have on average log n divisors, and half of them are odd. There's probably some nice upper bound for the number of odd divisors of a number less than n, but I don't feel like thinking about it.
Reply
Leave a comment