Editing Binomial coefficient (section)

=== Sums of the binomial coefficients ===
The formula
{{NumBlk2|:|<math> \sum_{k=0}^n \binom n k = 2^n</math>|∗∗}}
says that the elements in the {{mvar|n}}th row of Pascal's triangle always add up to 2 raised to the {{mvar|n}}th power. This is obtained from the binomial theorem ({{EquationNote|∗}}) by setting {{math|1=''x'' = 1}} and {{math|1=''y'' = 1}}. The formula also has a natural combinatorial interpretation: the left side sums the number of subsets of {1, ..., ''n''} of sizes ''k'' = 0, 1, ..., ''n'', giving the total number of subsets. (That is, the left side counts the [[power set]] of {1, ..., ''n''}.) However, these subsets can also be generated by successively choosing or excluding each element 1, ..., ''n''; the ''n'' independent binary choices (bit-strings) allow a total of <math>2^n</math> choices. The left and right sides are two ways to count the same collection of subsets, so they are equal.

The formulas
{{NumBlk2|:|<math>\sum_{k=0}^n k \binom{n}{k} = n 2^{n-1}</math>|6}}
and
: <math>\sum_{k=0}^n k^2 \binom n k = (n + n^2)2^{n-2}</math>
follow from the binomial theorem after [[derivative|differentiating]] with respect to {{mvar|x}} (twice for the latter) and then substituting {{math|1=''x'' = ''y'' = 1}}.

The [[Chu–Vandermonde identity]], which holds for any complex values ''m'' and ''n'' and any non-negative integer ''k'', is
{{NumBlk2|:|<math> \sum_{j=0}^k \binom m j \binom{n-m}{k-j} = \binom n k</math>|7}}
and can be found by examination of the coefficient of <math>x^k</math> in the expansion of {{math|1=(1 + ''x'')<sup>''m''</sup>(1 + ''x'')<sup>''n''−''m''</sup> = (1 + ''x'')<sup>''n''</sup>}} using equation ({{EquationNote|2}}). When {{math|1=''m'' = 1}}, equation ({{EquationNote|7}}) reduces to equation ({{EquationNote|3}}). In the special case {{math|1=''n'' = 2''m'', ''k'' = ''m''}}, using ({{EquationNote|1}}), the expansion ({{EquationNote|7}}) becomes (as seen in Pascal's triangle at right)
{{Image frame|width=395
|content=
<math>
\begin{array}{c}
 1 \\
 1 \qquad 1 \\
 1 \qquad 2 \qquad 1 \\
 {\color{blue}1 \qquad 3 \qquad 3 \qquad 1} \\
 1 \qquad 4 \qquad 6 \qquad 4 \qquad 1 \\
 1 \qquad 5 \qquad 10 \qquad 10 \qquad 5 \qquad 1 \\
 1 \qquad 6 \qquad 15 \qquad {\color{red}20} \qquad 15 \qquad 6 \qquad 1 \\
 1 \qquad 7 \qquad 21 \qquad 35 \qquad 35 \qquad 21 \qquad 7 \qquad 1
\end{array}
</math>
|caption=Pascal's triangle, rows 0 through 7. Equation {{EquationNote|8}} for {{math|1=''m'' = 3}} is illustrated in rows 3 and 6 as <math>1^2 + 3^2 + 3^2 + 1^2 = 20.</math>
}}
{{NumBlk2|:|<math> \sum_{j=0}^m \binom{m}{j} ^2 = \binom {2m} m,</math>|8}}
where the term on the right side is a [[central binomial coefficient]].

Another form of the Chu–Vandermonde identity, which applies for any integers ''j'', ''k'', and ''n'' satisfying {{math|1=0 ≤ ''j'' ≤ ''k'' ≤ ''n''}}, is
{{NumBlk2|:|<math>\sum_{m=0}^n \binom m j \binom {n-m}{k-j}= \binom {n+1}{k+1}.</math>|9}}
The proof is similar, but uses the binomial series expansion ({{EquationNote|2}}) with negative integer exponents.
When {{math|1=''j'' = ''k''}}, equation ({{EquationNote|9}}) gives the [[hockey-stick identity]]
: <math>\sum_{m=k}^n \binom m k = \binom {n+1}{k+1}</math>
and its relative
: <math>\sum_{r=0}^m \binom {n+r} r = \binom {n+m+1}{m}.</math>

Let ''F''(''n'') denote the ''n''-th [[Fibonacci number]].
Then
: <math> \sum_{k=0}^{\lfloor n/2\rfloor} \binom {n-k} k = F(n+1).</math>
This can be proved by [[mathematical induction|induction]] using ({{EquationNote|3}}) or by [[Zeckendorf's theorem|Zeckendorf's representation]]. A combinatorial proof is given below.

==== Multisections of sums ====
For integers ''s'' and ''t'' such that <math>0\leq t < s,</math> [[series multisection]] gives the following identity for the sum of binomial coefficients:
: <math>\binom{n}{t}+\binom{n}{t+s}+\binom{n}{t+2s}+\ldots=\frac{1}{s}\sum_{j=0}^{s-1}\left(2\cos\frac{\pi j}{s}\right)^n\cos\frac{\pi(n-2t)j}{s}.</math>

For small {{mvar|s}}, these series have particularly nice forms; for example,<ref>{{harvtxt|Gradshteyn|Ryzhik|2014|pp=3–4}}.</ref>
: <math> \binom{n}{0} + \binom{n}{3}+\binom{n}{6}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{n\pi}{3}\right) </math>
: <math> \binom{n}{1} + \binom{n}{4}+\binom{n}{7}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{(n-2)\pi}{3}\right) </math>
: <math> \binom{n}{2} + \binom{n}{5}+\binom{n}{8}+\cdots = \frac{1}{3}\left(2^n +2 \cos\frac{(n-4)\pi}{3}\right) </math>
: <math> \binom{n}{0} + \binom{n}{4}+\binom{n}{8}+\cdots = \frac{1}{2}\left(2^{n-1} +2^{\frac{n}{2}} \cos\frac{n\pi}{4}\right) </math>
: <math> \binom{n}{1} + \binom{n}{5}+\binom{n}{9}+\cdots = \frac{1}{2}\left(2^{n-1} +2^{\frac{n}{2}} \sin\frac{n\pi}{4}\right) </math>
: <math> \binom{n}{2} + \binom{n}{6}+\binom{n}{10}+\cdots = \frac{1}{2}\left(2^{n-1} -2^{\frac{n}{2}} \cos\frac{n\pi}{4}\right) </math>
: <math> \binom{n}{3} + \binom{n}{7}+\binom{n}{11}+\cdots = \frac{1}{2}\left(2^{n-1} -2^{\frac{n}{2}} \sin\frac{n\pi}{4}\right) </math>

==== Partial sums ====
Although there is no [[closed formula]] for [[partial sum]]s
: <math> \sum_{j=0}^k \binom n j</math>
of binomial coefficients,<ref>{{citation | last = Boardman | first = Michael | issue = 5 | journal = [[Mathematics Magazine]] | jstor = 3219201 | doi = 10.2307/3219201 | mr = 1573776 | quote = it is well known that there is no closed form (that is, direct formula) for the partial sum of binomial coefficients | pages = 368–372 | title = The Egg-Drop Numbers | volume = 77 | year = 2004}}.</ref> one can again use ({{EquationNote|3}}) and induction to show that for {{math|1=''k'' = 0, …, ''n'' − 1}},
: <math> \sum_{j=0}^k (-1)^j\binom{n}{j} = (-1)^k\binom {n-1}{k},</math>
with special case<ref>see induction developed in eq (7) p. 1389 in {{citation
 | last = Aupetit | first = Michael
 | journal = [[Neurocomputing (journal)|Neurocomputing]]
 | pages = 1379–1389
 | title = Nearly homogeneous multi-partitioning with a deterministic generator
 | volume = 72
 | number = 7–9
 | year = 2009
 | issn = 0925-2312
 | doi = 10.1016/j.neucom.2008.12.024
}}.</ref>

: <math>\sum_{j=0}^n (-1)^j\binom n j = 0</math>
for {{math|''n'' > 0}}. This latter result is also a special case of the result from the theory of [[finite differences]] that for any polynomial ''P''(''x'') of degree less than ''n'',<ref>{{cite journal|last=Ruiz|first=Sebastian|title=An Algebraic Identity Leading to Wilson's Theorem|journal=The Mathematical Gazette|year=1996|volume=80|issue=489|pages=579–582|doi=10.2307/3618534| jstor=3618534|arxiv=math/0406086|s2cid=125556648 }}</ref>
:<math> \sum_{j=0}^n (-1)^j\binom n j P(j) = 0.</math>
Differentiating ({{EquationNote|2}}) ''k'' times and setting ''x'' = −1 yields this for
<math>P(x)=x(x-1)\cdots(x-k+1)</math>,
when 0 ≤ ''k'' < ''n'',
and the general case follows by taking linear combinations of these.

When ''P''(''x'') is of degree less than or equal to ''n'',
{{NumBlk2|:|<math> \sum_{j=0}^n (-1)^j\binom n j P(n-j) = n!a_n</math>|10}}
where <math>a_n</math> is the coefficient of degree ''n'' in ''P''(''x'').

More generally for ({{EquationNote|10}}),
: <math> \sum_{j=0}^n (-1)^j\binom n j P(m+(n-j)d) = d^n n! a_n</math>
where ''m'' and ''d'' are complex numbers. This follows immediately applying ({{EquationNote|10}}) to the polynomial {{tmath|1=Q(x):=P(m + dx)}} instead of {{tmath|P(x)}}, and observing that {{tmath|Q(x)}} still has degree less than or equal to ''n'', and that its coefficient of degree ''n'' is ''d<sup>n</sup>a<sub>n</sub>''.

The [[series (mathematics)|series]] <math display="inline">\frac{k-1}{k} \sum_{j=0}^\infty \frac 1 {\binom {j+x} k}= \frac 1 {\binom{x-1}{k-1}}</math> is convergent for ''k'' ≥ 2. This formula is used in the analysis of the [[German tank problem]]. It follows from <math display="inline">\frac{k-1}k\sum_{j=0}^{M}\frac 1 {\binom{j+x} k}=\frac 1{\binom{x-1}{k-1}}-\frac 1{\binom{M+x}{k-1}}</math> which is proved by [[mathematical induction|induction]] on ''M''.