All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Bonjour, Pascal ! (Posted on 2013-04-10)
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 2k.

Bonus: How does k relate to the number of ones in the binary expansion of the number N?

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 1 of 2
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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: