Editing Binomial coefficient (section)

=== Recursive formula ===
One method uses the [[recursion|recursive]], purely additive formula
<math display="block"> \binom nk = \binom{n-1}{k-1} + \binom{n-1}k</math> for all integers <math>n,k</math> such that <math>1 \le k < n,</math>
with boundary values
<math display="block">\binom n0 = \binom nn = 1</math>
for all integers {{math|1=''n'' ≥ 0}}.

The formula follows from considering the set {{math|{{mset|1, 2, 3, ..., ''n''}}}} and counting separately (a) the {{mvar|k}}-element groupings that include a particular set element, say "{{mvar|i}}", in every group (since "{{mvar|i}}" is already chosen to fill one spot in every group, we need only choose {{math|''k'' − 1}} from the remaining {{math|''n'' − 1}}) and (b) all the ''k''-groupings that don't include "{{mvar|i}}"; this enumerates all the possible {{mvar|k}}-combinations of {{mvar|n}} elements. It also follows from tracing the contributions to ''X''<sup>''k''</sup> in {{math|(1 + ''X'')<sup>''n''−1</sup>(1 + ''X'')}}. As there is zero {{math|''X''<sup>''n''+1</sup>}} or {{math|''X''<sup>−1</sup>}} in {{math|(1 + ''X'')<sup>''n''</sup>}}, one might extend the definition beyond the above boundaries to include <math>\tbinom nk = 0</math> when either {{math|''k'' > ''n''}} or {{math|''k'' < 0}}. This recursive formula then allows the construction of [[Pascal's triangle]], surrounded by white spaces where the zeros, or the trivial coefficients, would be.