Editing Binomial coefficient (section)

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