There is endless number of surprising features in a
Pascal's Triangle.
One of them is the following theorem,
for you to prove:
The number of odd entries in row N of Pascal's Triangle is 2
k.
Bonus: How does k relate to the number of ones in the binary expansion of the number N?
We will prove the following - Given the bonary expansion of N, every index in the row (out of N) that can be expressed by switching off some of the 1 bits in N's binary expansion denotes an odd number in the row.
Touching upon the bonus question before the proof - this also shows that K=2^(number of 1's in N's binary exapnsion)
Proof - Assume by induction that this holds true for N-1. Lets show that every odd number in the N'th row is denoted by an index number that can be expressed as explained above - and only these indices are odd.
Each index containes an odd number iff one of the number above it is odd and the other is even. For the sake of simplicity, lets assume we are looking at the index 4 in the Nth row - thus the indices above it are 3,4 in the N-1th row.
Also, lets assume the 3'rd number in the N-1th row is even and the 4th is odd - the other case is not much different.
Showing that the 4'th bit in Nth expansion is 1 completes the proof.
We know that in the N-1's expansion, bit 3 is 0 and 4 is 1.
To move to N's expansion, all we have to do is add 1 to N-1's expansion. Following the laws of binary addition, we see that adding 1 can not change the 4'th bit, as the 3'rd one is 0.
Thus the 4th bit is indeed 1 in N's binary expansion which completes the proof
|
|
Posted by Omri
on 2014-09-02 11:20:21 |
Solution
