Estimating a Cumulative Sum

Summary

This article explores the asymptotic estimation of the cumulative sum of unlabeled rooted trees. By leveraging the known asymptotic behavior of the sequence $t(n)$ (OEIS A000081), we derive an asymptotic formula for its cumulative sum $c(n)$ (OEIS A087803). The derivation relies on the property that for rapidly increasing sequences, the sum is dominated by its final terms.

Background

In previous discussions, we defined two sequences: * $t(n)$: The number of unlabeled rooted trees with $n$ nodes. * $c(n)$: The cumulative sum of $t(n)$, defined as: $$c(n) = \sum_{i=1}^n t(i)$$

The sequence $c(n)$ is significant in numerical analysis, representing the number of constraints on an $n$-step Runge-Kutta method.

Asymptotic Derivation

The sequence $t(n)$ follows the asymptotic form: $$t(n) \sim C \frac{\alpha^n}{n^{3/2}}$$ where $C \approx 0.4399$ and $\alpha \approx 2.9557$.

To estimate $c(n)$, we assume that the cumulative sum of the asymptotic estimates provides a valid asymptotic estimate for the sum itself. Because the sequence grows exponentially, the final terms contribute the most to the total sum. The derivation proceeds as follows:

\[ \begin{align*} c(n) &= \sum_{n=1}^N t(n) \\ &\sim \sum_{n=1}^N C \frac{\alpha^n}{n^{3/2}}\\ &= C \frac{\alpha^N}{N^{3/2}} \sum_{k=0}^{N-1} \alpha^{-k}\left(1 - \frac{k}{N} \right)^{-3/2} \\ &\sim C \frac{\alpha^N}{N^{3/2}} \sum_{k=0}^\infty \alpha^{-k} \\ &= C \frac{\alpha^N}{N^{3/2}} \frac{\alpha}{\alpha-1} \\ &= C \frac{\alpha^{N+1}}{(\alpha-1)N^{3/2}} \end{align*} \]

Verification

We can visualize the convergence of this approximation by comparing it to the exact values provided by the OEIS.

import numpy as np
import matplotlib.pyplot as plt

# A000081 values (truncated for brevity)
A000081 = [0, 1, 1, 2, 4, ...]  
A087803 = np.cumsum(A000081)

def approx(n):
    C = 0.43992401257102530
    a = 2.95576528565199497
    return C * a**(n+1) * n**(-3/2) / (a - 1)

n = np.arange(len(A087803))
ratio = A087803 / approx(n)

plt.plot(n[1:], ratio[1:])
plt.plot(n, 0*n + 1, '--')
plt.xlabel("$n$")
plt.ylabel("exact/approx")
plt.show()

The resulting plot demonstrates that as $n$ increases, the ratio of the exact cumulative sum to our asymptotic estimate approaches 1, confirming the validity of the derivation.

Source: This post originally appeared on John D. Cook's blog.