trying to prove that all the elements in a row of pascals triangle are odd if and only if n=2^k -1

I wrote out the rows mod 2 but i dont see how that leads me to a proof of this.. im missing some piece of the idea

Printable View

- Jan 26th 2011, 02:08 PMstumped765pascals triangle
trying to prove that all the elements in a row of pascals triangle are odd if and only if n=2^k -1

I wrote out the rows mod 2 but i dont see how that leads me to a proof of this.. im missing some piece of the idea - Jan 26th 2011, 06:29 PMTKHunny
1) Rather screaming for induction, isn't it?

2) For k = 0, we have n = 0. Is that the first row? 1 - yup, odd only

3) For k = 1, we have n = 1. 1, 1 - yup, odd only.

4) For k = 2, we have n = 3. Can you get here from there? - Jan 27th 2011, 11:10 AMemakarov
To prove this claim by induction, we need to connect the ($\displaystyle 2^n-1$)th and ($\displaystyle 2^{n+1}-1$)th rows. It is not immediately clear how to do this, e.g., how to produce the latter from the former. Alternatively, if we use Pascal's rule $\displaystyle {n-1\choose k} + {n-1\choose k-1} = {n\choose k}$, then we cannot limit the claim only to rows number $\displaystyle 2^n-1$; the claim has to be strengthened to describe each row in such a way that it would still imply the required conclusion for rows number $\displaystyle 2^n-1$.

This is very much like loop invariants in programming. We may know what we would like the loop to produce in the end. However, to*prove*that it does so, we have to describe not only the desired final result, but also each intermediate iteration. This description has to make clear why it is preserved from one iteration to the next and why it implies the final result. Such strengthening of the induction hypothesis is ubiquitous in many areas of discrete mathematics.

Wikipedia says that Pascal's triangle resembles Sierpinski triangle. (They become the same only in the limit because Pascal's triangle grows infinitely in size while Sierpinski triangle grows infinitely in depth, so to speak.)

http://lh6.ggpht.com/_SNa3egOo9rk/TU...l-triangle.png

In this picture, I denote even numbers by 0 and odd numbers by 1. Suppose that we have the top part of the triangle that ends in a row of 1's. Then the triangle of twice the height is obtained by making two copies of the top triangle and filling the middle with 0's. Indeed, the row after all 1's will be 1 0 0 ... 0 0 1. It is easy to see that in the bottom left triangle, there is a growing diagonal (i.e., the right side) of 1's that goes down and right. Therefore, the bottom left triangle will be a copy of the top one. A similar thing happens to the bottom right triangle. There won't be another row of all 1's until the two bottom triangles are completed.