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 N1. 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 N1th row.
Also, lets assume the 3'rd number in the N1th 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 N1'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 N1'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 20140902 11:20:21 