AngouriMath

Symbolics for .NET


Table of contents

AngouriMath

Navigation
Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

BinomialIdentities

← Back to list of classes

Description

Summary

The binomial sums of chapter 8 of Sullivan and Mackey's An Introduction to Proofs that are not the binomial theorem itself, in closed form: a polynomial in the index
beside the coefficient (Prop 8.4.4, sum(k binomial(n, k), k, 0, n) is
n 2^(n - 1)), Vandermonde's convolution (Prob 8.9.16,
sum(binomial(a, i) binomial(b, k - i), i, 0, k) is binomial(a + b, k)) and
its square case (Prob 8.9.34, sum(binomial(n, k)^2, k, 0, n) is
binomial(2n, n)), the summation identity (Thm 8.4.6,
sum(binomial(i, k), i, 0, n) is binomial(n + 1, k + 1)), the sums over
the even or the odd indices (Ex 8.3.11, each 2^(n - 1) for n >= 1), the
trinomial revision summed (Prob 8.9.15, sum(binomial(n, i) binomial(n - i, k - i), i, 0, k) is 2^k binomial(n, k), and §8.4.5's sum(binomial(n, i) binomial(i, k), i, k, n),
2^(n - k) binomial(n, k)), the parallel summation (Prob 8.9.19,
sum(binomial(r + i, i), i, 0, n) is binomial(r + n + 1, n)) and Vandermonde along
the upper indices (Prob 8.9.18, sum(binomial(j, a) binomial(m - j, b), j, 0, m) is
binomial(m + 1, a + b + 1)).

Remarks

A polynomial beside the coefficient is read in the falling factorial basis,
k^m = sum_j S(m, j) k (k - 1) ... (k - j + 1) with the Stirling numbers of the second
kind, because k (k - 1) ... (k - j + 1) binomial(n, k) is
n (n - 1) ... (n - j + 1) binomial(n - j, k - j) -- the chairperson identity
applied j times -- so sum_k k^(j falling) binomial(n, k) x^k y^(n - k) is
n^(j falling) x^j (x + y)^(n - j) by the binomial theorem on what is left. Exact for
every whole n >= 0 and every x, y; the empty range below zero is
the piecewise PolynomialSummation attaches.
Vandermonde holds as an identity in a and b for whole a, b >= 0 and a whole k >= 0, the terms outside 0 <= i <= min(a, k) being zero, so the
range may be written to k, to a, or to b where the second coefficient
is binomial(b, k - i). The square is the case a = b = k = n with
binomial(n, k) = binomial(n, n - k). The summation identity is Pascal's rule
telescoped. Part of #1409.

Members

























Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online