Module summation 

Symbolic summation and products. Symbolic summation and products: Faulhaber, telescoping, hypergeometric, infinite sums, and closed-form products.

This module is the backend behind Ex::summation and Ex::product_over. It works on &mut Arena + ExprId and is also used by eval() when it encounters a Sum node (via the thin shim in calculus::sum_eval).

Summation strategies

For Σ_{k=lo}^{hi} f(k) the dispatcher tries, in order:

1. Empty / enumerable ranges — concrete integer bounds with at most MAX_ENUMERATION_TERMS terms are summed directly (exactly).
2. Constant body — f independent of k gives f·(hi − lo + 1).
3. Rational functions of k — partial fractions, then each pole family c/(k+β)^m is summed with harmonic numbers / digamma, and integer-shifted poles telescope exactly (Σ 1/(k(k+1)) = 1 − 1/(n+1)).
4. Telescoping g(k) − g(k+d) for two-term bodies.
5. Linearity — sums of terms are summed term-by-term; terms that cannot be summed are kept as an unevaluated Sum.
6. Polynomials in k (any degree, symbolic coefficients allowed) via Faulhaber’s formula with exact Bernoulli numbers.
7. Binomial identities (Σ C(n,k) = 2ⁿ, Σ k·C(n,k) = n·2ⁿ⁻¹, Σ C(n,k)² = C(2n,n), Σ C(n,k) xᵏ = (1+x)ⁿ, …). Geometric exponents may carry a symbolic k-free offset, so the binomial theorem Σ C(n,k) pᵏ (1−p)ⁿ⁻ᵏ = 1 closes for symbolic n and p.
8. Geometric / arithmetico-geometric Σ P(k)·rᵏ with symbolic r (a Piecewise covers r = 1).
9. Gosper’s algorithm for hypergeometric terms (including C(k+c, k)-type binomials with k in both arguments).

For infinite upper bounds the engine additionally recognises p-series (ζ(2m) in closed form), alternating p-series (η, Dirichlet β), convergent geometric series, the negative-binomial series Σ P(k)·C(k+c,k)·xᵏ ((1−x)^{−(c+1)} for P = 1, any c), and a table of classical power series (Σ xᵏ/k! = eˣ, Σ (−1)ᵏ x²ᵏ⁺¹/(2k+1)! = sin x, Σ xᵏ/k = −ln(1−x), …), and proves divergence where it can.

Symbolic ratios. Convergence of an infinite geometric-type series is decided only for a numeric ratio. There is no |r| < 1 assumption, so Σ_{k≥0} rᵏ, Σ k (1−p)ᵏ⁻¹ p or Σ C(k+c,k) xᵏ with a symbolic ratio stay unevaluated (SymPy returns a Piecewise over Abs(r) < 1 instead). Sums whose ratio is numeric but whose other parameters are symbolic (Σ C(k+c,k) (1/3)ᵏ = (2/3)^{−c−1}) do close.

Values without an elementary closed form use the dedicated nodes: Σ 1/k³ = ζ(3) (Zeta), Σ (−1)^k/(2k+1)² = G (Catalan).

Constants

MAX_ENUMERATION_TERMS

Maximum number of terms that will be summed / multiplied by direct enumeration when both bounds are concrete integers.