Editing Double counting (proof technique) (section)

===Forming committees===
One example of the double counting method counts the number of ways in which a committee can be formed from <math>n</math> people, allowing any number of the people (even zero of them) to be part of the committee. That is, one counts the number of [[subset]]s that an <math>n</math>-element set may have. One method for forming a committee is to ask each person to choose whether or not to join it. Each person has two choices – yes or no – and these choices are independent of those of the other people. Therefore there are <math>2\times 2\times \cdots 2 = 2^n</math> possibilities. Alternatively, one may observe that the size of the committee must be some number between 0 and <math>n</math>. For each possible size <math>k</math>, the number of ways in which a committee of <math>k</math> people can be formed from <math>n</math> people is the [[binomial coefficient]]
<math display=block>{n \choose k}.</math>
Therefore the total number of possible committees is the sum of binomial coefficients over <math>k=0,1,2,\dots,n</math>. Equating the two expressions gives the [[Identity (mathematics)|identity]]
<math display=block>\sum_{k=0}^n {n \choose k} = 2^n,</math>
a special case of the [[binomial theorem]]. A similar double counting method can be used to prove the more general identity<ref>{{harvnb|Garbano|Malerba|Lewinter|2003}}; {{harvnb|Klavžar|2006}}).</ref>
<math display=block>\sum_{k=d}^n {n\choose k}{k\choose d} = 2^{n-d}{n\choose d}</math>