Editing Binomial coefficient (section)

== Identities involving binomial coefficients ==
The factorial formula facilitates relating nearby binomial coefficients. For instance, if ''k'' is a positive integer and ''n'' is arbitrary, then
{{NumBlk2|:|<math> \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}</math>|5}}
and, with a little more work,
: <math>\binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}.</math>

We can also get
: <math>\binom {n-1}{k} = \frac{n-k}{n} \binom {n}{k}.</math>

Moreover, the following may be useful:
:<math>\binom{n}{k}\binom{k}{j} = \binom{n}{j}\binom{n-j}{k-j}=\binom{n}{k-j}\binom{n-k+j}{j}.</math>

For constant ''n'', we have the following recurrence:
: <math> \binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}.</math>

To sum up, we have
: <math>\binom {n}{k} = \binom n{n-k} = \frac{n-k+1}{k} \binom {n}{k-1} = \frac{n}{n-k} \binom {n-1}{k} </math>
: <math>= \frac{n}{k} \binom {n-1}{k-1} = \frac{n}{n-2k} \Bigg(\binom {n-1}{k} - \binom{n-1}{k-1}\Bigg) = \binom{n-1}k + \binom{n-1}{k-1}.</math>

=== 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''.

=== Identities with combinatorial proofs ===
Many identities involving binomial coefficients can be proved by [[combinatorial proof|combinatorial means]]. For example, for nonnegative integers <math>{n} \geq {q}</math>, the identity
: <math>\sum_{k=q}^n \binom{n}{k} \binom{k}{q} = 2^{n-q}\binom{n}{q}</math>
(which reduces to ({{EquationNote|6}}) when ''q'' = 1) can be given a [[double counting (proof technique)|double counting proof]], as follows. The left side counts the number of ways of selecting a subset of [''n''] = {1, 2, ..., ''n''} with at least ''q'' elements, and marking ''q'' elements among those selected. The right side counts the same thing, because there are <math>\tbinom n q</math> ways of choosing a set of ''q'' elements to mark, and <math>2^{n-q}</math> to choose which of the remaining elements of [''n''] also belong to the subset.

In Pascal's identity
: <math>{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k},</math>
both sides count the number of ''k''-element subsets of [''n'']: the two terms on the right side group them into those that contain element ''n'' and those that do not.

The identity ({{EquationNote|8}}) also has a combinatorial proof. The identity reads
: <math>\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}.</math>

Suppose you have <math>2n</math> empty squares arranged in a row and you want to mark (select) ''n'' of them. There are <math>\tbinom {2n}n</math> ways to do this. On the other hand, you may select your ''n'' squares by selecting ''k'' squares from among the first ''n'' and <math>n-k</math> squares from the remaining ''n'' squares; any ''k'' from 0 to ''n'' will work. This gives
:<math>\sum_{k=0}^n\binom n k\binom n{n-k} = \binom {2n} n.</math>
Now apply ({{EquationNote|1}}) to get the result.

If one denotes by {{math|''F''(''i'')}} the sequence of [[Fibonacci number]]s, indexed so that {{math|1=''F''(0) = ''F''(1) = 1}}, then the identity
<math display="block">\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} \binom {n-k} k = F(n)</math>
has the following combinatorial proof.<ref>{{harvnb|Benjamin|Quinn|2003|loc=pp. 4−5}}</ref> One may show by [[mathematical induction|induction]] that {{math|''F''(''n'')}} counts the number of ways that a {{math|''n'' × 1}} strip of squares may be covered by {{math|2 × 1}} and {{math|1 × 1}} tiles. On the other hand, if such a tiling uses exactly {{mvar|k}} of the {{math|2 × 1}} tiles, then it uses {{math|''n'' − 2''k''}} of the {{math|1 × 1}} tiles, and so uses {{math|''n'' − ''k''}} tiles total. There are <math>\tbinom{n-k}{k}</math> ways to order these tiles, and so summing this coefficient over all possible values of {{mvar|k}} gives the identity.

==== Sum of coefficients row ====
{{See also|Combination#Number of k-combinations for all k}}

The number of ''k''-[[Combination#Number of k-combinations for all k|combinations]] for all ''k'', <math display="inline">\sum_{0\leq{k}\leq{n}}\binom nk = 2^n</math>, is the sum of the ''n''th row (counting from 0) of the binomial coefficients. These combinations are enumerated by the 1 digits of the set of [[base 2]] numbers counting from 0 to <math>2^n - 1</math>, where each digit position is an item from the set of ''n''.

=== Dixon's identity ===
[[Dixon's identity]] is
: <math>\sum_{k=-a}^{a}(-1)^{k}{2a\choose k+a}^3 =\frac{(3a)!}{(a!)^3}</math>
or, more generally,
: <math>\sum_{k=-a}^a(-1)^k{a+b\choose a+k} {b+c\choose b+k}{c+a\choose c+k} = \frac{(a+b+c)!}{a!\,b!\,c!}\,,</math>
where ''a'', ''b'', and ''c'' are non-negative integers.

=== Continuous identities ===
Certain trigonometric integrals have values expressible in terms of binomial coefficients: For any <math>m, n \in \N,</math>
: <math>\int_{-\pi}^{\pi} \cos((2m-n)x)\cos^n(x)\ dx = \frac{\pi}{2^{n-1}} \binom{n}{m}</math>
: <math>
\int_{-\pi}^{\pi} \sin((2m-n)x)\sin^n(x)\ dx =
\begin{cases}
(-1)^{m+(n+1)/2} \frac{\pi}{2^{n-1}} \binom{n}{m}, & n \text{ odd} \\
0, & \text{otherwise}
\end{cases}</math>
: <math>
\int_{-\pi}^{\pi} \cos((2m-n)x)\sin^n(x)\ dx =
\begin{cases}
(-1)^{m+(n/2)} \frac{\pi}{2^{n-1}} \binom{n}{m}, & n \text{ even} \\
0, & \text{otherwise}
\end{cases}</math>

These can be proved by using [[Euler's formula]] to convert [[trigonometric functions]] to complex exponentials, expanding using the binomial theorem, and integrating term by term.

=== Congruences ===
If ''n'' is prime, then <math display="block">\binom {n-1}k \equiv (-1)^k \mod n</math> for every ''k'' with <math>0\leq k \leq n-1.</math>
More generally, this remains true if ''n'' is any number and ''k'' is such that all the numbers between 1 and ''k'' are coprime to ''n''.

Indeed, we have
: <math>
\binom {n-1} k = {(n-1)(n-2)\cdots(n-k)\over 1\cdot 2\cdots k}
= \prod_{i=1}^{k}{n-i\over i}\equiv \prod_{i=1}^{k}{-i\over i} = (-1)^k \mod n.
</math>