In the section of [counting](https://steemit.com/mathematics/@sinbad989/a-gentle-introduction-to-mathematics-counting) we have determined the number k-subsets of a set of size n, denoted by ![](https://steemitimages.com/DQmaKkDQLbbiokJ164ZqGsW3iuS1gW5kPJ9cprt8x6f2rRX/image.png)  which is expressed in terms of binomial coefficients. **Binomial coefficient** is a powerful tool in mathematics. 

# Pascal’s Triangle
<hr>

Binomial coefficients can be arranged into a triangular array – known as Pascal’s triangle:
 <center>![](https://steemitimages.com/DQmUtB1jxuEk8dRexC29hLYovioYCQ3hrzmnmiFkFPGx6zs/image.png)</center>
The power of this triangle is it can be used to calculate powers of binomials. 

### Binomials
A binomial is a polynomial with two terms. What if you want to determine the nth power of a binomial, for instance the ![](https://steemitimages.com/DQmQ6qy9m5rfYbcq58S8rnCx2QU2RBP8t7FMv1uUTKdiFQ6/image.png). An example is to find the 6th power of ![](https://steemitimages.com/DQmQ6qy9m5rfYbcq58S8rnCx2QU2RBP8t7FMv1uUTKdiFQ6/image.png) .

We can start by finding the squared of  ![](https://steemitimages.com/DQmQ6qy9m5rfYbcq58S8rnCx2QU2RBP8t7FMv1uUTKdiFQ6/image.png) which is equal to ![](https://steemitimages.com/DQmSWqGj2CqZFq2rkdDoXoYepkmxSywnyy1JiA6D1HbZYno/image.png) . From which, we can determine the cubed power,
<center>![](https://steemitimages.com/DQmRhPuxfiRLwRWu9hEeaF2JiBziMmyfVPSMejVx96ip9WS/image.png)</center>

To determine the value of the last product we use the table method: 
<center>![](https://steemitimages.com/DQmW5ELebrzUuHb3XMScrjmFnDZhgL7gxULvgYsgzVvLgV7/image.png)</center>

This gives us, <br> ![]<center>(https://steemitimages.com/DQmcgRLdNNGQypkX6fXjnCwaKsfRzR9QeAhrzJTiaMYGZmv/image.png)</center>

Finally, we use this third power to determine the sixth power, thus
<center>![](https://steemitimages.com/DQmehMD18i1o7pdVeiFnks5r8bAH3YW9LMaedfdtYGM21Qe/image.png)</center>

We can use table method again for the last product:
<center>![](https://steemitimages.com/DQmNeTx6vro1m1XgE4N2tzEa2XzgiMdarDZurv9uqGki33f/image.png)</center>

This will give us the final answer as: 
<center>![](https://steemitimages.com/DQmUqCfpns6mB4TMwXjf7fEyoyEjYFJPGVXimseA1wtTpYq/image.png)![](https://steemitimages.com/DQmYaxF4tCiGB2vPr5KRXqSB3MUNDwS3LtQvtMxumg82p88/image.png)</center>

It took us a lot of work to reach this answer. Now, look at the answer above, the exponents on *x* starts at 6 and descends with each successive term down to 0. The same line of pattern holds for *y* but this time starting on the right side. Interestingly, the coefficients we have shown are actually the sixth row of the Pascal’s triangle. 

Fortunately, Pascal’s triangle is also easy to extend; that is, the number in the interior of the triangle is always the sum of the two above it. Consider the 7th and 8th row of the Pascal’s triangle: 
<center>![](https://steemitimages.com/DQmVi5PyrCWZ3R1gBwNkqA292bVUnJnWCvW5MPDeF3Em89m/image.png)</center>

With this tool, it becomes easier to determine the nth power of a binomial. 
<center>![](https://steemitimages.com/DQmXXS6Mp3hRiSBGTW2dabJWLEVktCqPZqoB9k8hBUEwG4J/image.png)</center>

# Theorems regarding the Binomial Coefficients
<hr>

<center>![](https://steemitimages.com/DQmWHyiySdkohbX243PqNNZoRTTcmo98SNR9y2AcRQGju1F/image.png)</center>

### Proof 1: Combinatorial method
The number of subsets of size *k* of the set ![](https://steemitimages.com/DQmTjLMfxmtd9inqbmem7hrBcuvRcGHj4AUWCdsc44evoYA/image.png)  of size *n* is given by, ![](https://steemitimages.com/DQma8JEdJXgcTR4svcQzPVop5DfJa5tUwgwMrh9sQ8byPc2/image.png) . We can partition these k-subsets into two disjoint cases:
1. Those that contain the final number n (set B) <br> ![](https://steemitimages.com/DQmPcsEXjMXKZgtRwpjxt4yuuQA2vkCCP7zSd6CpwDt3wnf/image.png) 
1. Those that does not contain the final number n (set A) <br> ![](https://steemitimages.com/DQmZT9vu8wveJ1K8SCY7JyKVqoQq5CjahiHCNGJyJrCB9fP/image.png)

By addition rule, the size of the sum of the disjoint sets is given as, 
<center>![](https://steemitimages.com/DQmRd2srn9Jtzc1CgZ6KW7QvgDoHsy9V5CLapEppcACC3af/image.png)</center>

Set *A* is really just the set of all k-subsets of the (n-1)-set ![](https://steemitimages.com/DQmPyX3N4nGGNiktrTNqD9588DqMS8p8FN8twnn7oQpUy4p/image.png) , thus the size of set A is defined to be, 
![](https://steemitimages.com/DQmVFsEkxcdHPqgrTkFDrDw7UNZQtVB4xYeDkDSLDjbNzsH/image.png)

The set B can be obtained by adjoining the element n into a (k-1) subset of the (n-1)-set ![](https://steemitimages.com/DQmPyX3N4nGGNiktrTNqD9588DqMS8p8FN8twnn7oQpUy4p/image.png)  , thus the size of set B is given by, 
![](https://steemitimages.com/DQmfTLPSFcSRmyRwkJ2HwQmN7yQ2x6vtGoeef18BvucZ6d3/image.png)

Substituting this values to the equation, 
 <center>![](https://steemitimages.com/DQmRd2srn9Jtzc1CgZ6KW7QvgDoHsy9V5CLapEppcACC3af/image.png)</center>

will give us, 
<center>![](https://steemitimages.com/DQmQWsdQNhQwFpa83VDYnHwoWck134vgHdgyc23yej6LFHf/image.png)</center>

### Proof 2: Algebraic method
For the algebraic method, we will use the [two-column proof](https://steemit.com/mathematics/@sinbad989/a-gentle-introduction-to-mathematics-two-column-proof) so one can easily follow the arguments. 

| <center>Left-Side</center>| <center>Right-Side</center> | 
| -------- | -------- |
| <center>![](https://steemitimages.com/DQmWSPeszSt9oYt81VrMqPuaUhgXiKa639UWMZF1NypZr1P/image.png) </center>  | ![](https://steemitimages.com/DQmdf2y6w9Bd3boyycMSA6CvFd9GE7UKWgdYZiX44u6HhHj/image.png)    | 
| -     | ![](https://steemitimages.com/DQmSdjhmPJsYH8gd27bTrss4bZvFqVF7iiok4jmxmZpCtg2/image.png)     | 
| -     | ![](https://steemitimages.com/DQmefotut9eayBwQwnHMh76FC996dsDsoeVSqpyjMhzWid3/image.png)    | 
| -     | ![](https://steemitimages.com/DQmQDxDcEcRNmmLvCXBa47s3bn1CAjJfcq6YydqipZtszdP/image.png)    | 
| -    | ![](https://steemitimages.com/DQmQHeSumXrBKDopRndYLzxvphLMyUAYmM27S7z8Xh5ZYXe/image.png)   | 
|<center>![](https://steemitimages.com/DQmNYTcWJk2NTz9ZA5MNkEwr8dQYky6Ky9aN5B232hFUKTg/image.png) </center>   |![](https://steemitimages.com/DQmUb2QX6acJhbit8pYMHZH9xK2aQAvFq5pR8BKPabRJxns/image.png)   | 

<hr>

<center>![](https://steemitimages.com/DQme6XVvMDYBcKfYn7nCnjX52eH95K9V7mz5vZFjwmfTG8t/image.png) </center>

### Proof 1: Combinatorial method

Consider a committee of *k* individuals one of whom has been chosen as chairperson. Similar kind of thinking can be applied to a collection of all subsets of size k taken from ![](https://steemitimages.com/DQmTjLMfxmtd9inqbmem7hrBcuvRcGHj4AUWCdsc44evoYA/image.png), in which one of the elements is marked to distinguish it from the rest.  

We can count this collection in two ways: 
1. We select a k-subset in ![](https://steemitimages.com/DQma8JEdJXgcTR4svcQzPVop5DfJa5tUwgwMrh9sQ8byPc2/image.png) ways and then from among the k elements of the subset we could select one to be marked. This means, that there are ![](https://steemitimages.com/DQmSGe3v2uKmoP4imcLEzU43tchpAaWNyYpicDM5v8XMSq1/image.png) in our collection.
1. We could select an element in our n-set and consider it as the “marked” element of a subset. Then choose the additional k-1 elements from the remaining n-1 elements of the n-set. This implies that there are ![](https://steemitimages.com/DQmVPQE2YeSBgkUEFA7Se88PzeqyPzKokKwZT7Eqw5ZwXBV/image.png)  elements in our collection. 

Thus, 
<center>![](https://steemitimages.com/DQmd1TV3y8JhA48dpjQ1s1GwsCdjmYMV6NhNcQESzm8UM65/image.png)</center>

### Proof 2: Algebraic method

For the algebraic method, we will use the [two-column proof](https://steemit.com/mathematics/@sinbad989/a-gentle-introduction-to-mathematics-two-column-proof) so one can easily follow the arguments.

| <center>Left-Side</center>| <center>Right-Side</center> | 
| -------- | -------- | 
|  <center>![](https://steemitimages.com/DQmWJCczDVs24NwkqgXnwP4BHWPkSNugYFhtbanFaER4aJ4/image.png)  </center>   | ![](https://steemitimages.com/DQmU1FGvzyT1HzuZ7Hg8W6HfR4vQCeXdnXrG77JeZ6vYDFV/image.png)   |
| _   | ![](https://steemitimages.com/DQmYcd77ZSXJrcg19fdiTCAC4xxmsu1Vcfn53c5tgHyFjFD/image.png)    |
| _     | ![](https://steemitimages.com/DQma52wULRvRx5E9V6PcDR2QXug3ZfTRrXQ6CkpGnD3dLSi/image.png)    |
| _     | ![](https://steemitimages.com/DQmdg9RmQnvE5hzMWKc2ejdZ5LYEc3MPPyyL2iSZUv39hhf/image.png)     |
| <center> ![](https://steemitimages.com/DQmQmTWm8N7LcmzUM3Eyc3HiBVMHwtNXQFFgrtAJif8W834/image.png)   </center> | ![](https://steemitimages.com/DQmYfM2XGmNNhpkYeBJGFxngu9spfzn9bFCU8cu6mPG3PJg/image.png)    |

<hr> 

<center>
![](https://steemitimages.com/DQmZaLJBkTb9vRHqvAQ3wUcdQT6Xvdho8p6QkKDJEcREyaB/image.png)
</center>

### Proof:

The set of all subsets of ![](https://steemitimages.com/DQmeUjbr4iFPgMdTssGdGhyY2ARagbapFfGjxz8Yi9nU3bK/image.png)  , which we denote as the power set of N ![](https://steemitimages.com/DQmSuWsE6efdmcS9vBLFFjAjfBSENszzXLaXjm5CyRHpkeo/image.png),   can be partitioned into n+1 sets based on the sizes of the subset. 

<center>![](https://steemitimages.com/DQmaDE8eT34kRT1XMSti8D3agaVVaRqrj9fkrXURA6QiJhg/image.png)</center>

where ![](https://steemitimages.com/DQmYkVfRcCTbTxzE1AiPRNbZSpUgYn7a4nvgsZCc9tA5A7Y/image.png) is a subset of the set  N and that k is the size of the subset S, in symbolic form: 
<center>![](https://steemitimages.com/DQmYjKjZKvC9Cw1s1VwQvqyKZn6t1q7KFBYZXsmSkDbF4Gs/image.png)</center>

Two things to remember:
1. No subset of N can appear in two different parts of the partition (every ![](https://steemitimages.com/DQmYkVfRcCTbTxzE1AiPRNbZSpUgYn7a4nvgsZCc9tA5A7Y/image.png)  size is unique)
1. Every subset of N appears in one of the parts of the partition (sizes of subsets are all in the range from 0 to n).

The addition principle tells us that the size of the power set is,
<center>![](https://steemitimages.com/DQmW8QC713KfUCTkfxpaSS998j4kPmXiCzxUbVkvdSAJ8i7/image.png)</center>

From previous [sections](https://steemit.com/mathematics/@sinbad989/a-gentle-introduction-to-mathematics-the-principle-of-mathematical-induction), we have shown that ![](https://steemitimages.com/DQmNfm1BK8eGKpTHdmrXo8jDcuYaAKpgnBL4uaNManXd6Mm/image.png), and we know that ![](https://steemitimages.com/DQmTjtwricPvBEnHVSaxGkxz22LHQEv377mTdMUo4USqQ94/image.png), therefore

<center>![](https://steemitimages.com/DQmNyinkfEKtaRRsRhn7JqA7Sahfh7NHuK371ENZ68x6DYe/image.png)</center>


<hr>


### This will somehow serve as the summary of our story: 
<center>
![](https://steemitimages.com/DQmcZ4wM2V2fFTYr5p8e8xwir4Pr3bNG8zcQvFPLZ6ssvSm/image.png)
</center>
Substituting x=y=1 to Theorem 7.4.4, we have Theorem 7.4.3,
 <center>
![](https://steemitimages.com/DQmPzNcoaHVtyWGnqp3aaC1uDv3SfjthhxtngKyYKSuqEQA/image.png)
</center>

Note that there is another proof without referring to the binomial theorem. This proof is **"like swatting a fly with a sledgehammer."**

<br>
<br>
<sup>Disclaimer: this is a summary of section 7.4 from the book A Gentle Introduction to the Art of Mathematics: by Joe Fields, the content apart from rephrasing is identical, most of the equations are screenshots of the book and the same examples are treated.</sup>

1. [A Gentle Introduction to the Art of Mathematics by Joe Field](https://github.com/valjen/book_collection)

<hr>

<center> Thank you for reading ...
![](https://steemitimages.com/DQmfWLieGjcAAkK1rBHrXgmQyZiVbPsAeQugBuSV39rXxE4/image.png)
![](https://steemitimages.com/DQmNXXLQdbXpB1WuRn2YErhQLznZVCdUW3kc7sutPWxA8vv/image.png)
</center>