### Pascal's Triangle

For a computer programmer, an interesting way to understand Pascal's triangle is to look at it as describing strings of n bits, where n is a row of the triangle.

The first and the last elements in the row, which are always one, are the number of ways to have all bits zero or all bits one, which is naturally just one way. The second element and the second-to-last element are the number of ways to have one bit on, and the number of ways to have all but one bit on. These are always going to be equal to the length of the string, or, in other words, the row number. That is because if your string is, say, three bits, you can have bit zero on, bit one on, or bit two on: three ways to have one bit turned on:

``` ```
``` 100            010           001 ```
``` ```

And so on.

This of course very easily makes clear that the numbers in row n will add up to 2n: that is how many numbers you can represent with a string of n bits!

1. And now, for extra fun, prove that the number of ways of turning on exactly k out of n bits satisfies the recurrence relation that defines Pascal's triangle.

1. Yes indeed.