Results 1 to 3 of 3

Math Help - pascals triangle

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    51

    pascals 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Aug 2007
    From
    USA
    Posts
    3,110
    Thanks
    2
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    To prove this claim by induction, we need to connect the ( 2^n-1)th and ( 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 {n-1\choose k} + {n-1\choose k-1} = {n\choose k}, then we cannot limit the claim only to rows number 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 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.)



    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 28th 2008, 07:02 PM
  2. Polynomial Expansion Using Pascals Triangle
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 3rd 2008, 08:29 AM
  3. Pascals triangle...?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 1st 2008, 05:20 AM
  4. Replies: 27
    Last Post: April 27th 2008, 10:36 AM
  5. Pascals Law
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: April 23rd 2008, 09:57 AM

Search Tags


/mathhelpforum @mathhelpforum