Joe asked in Science & MathematicsMathematics · 5 months ago

Combinatorics And Even Numbers?

I am studying combinatorics and specifically the Pascal triangle. Basically, I am trying to show some patterns are true.

My question is, how can we show that all binomial coefficients of form, in combination notation where nCk is "n choose k", (2^m + r)C(1 + r), ... , (2^m + r)C(2^m - 1) are even, where r = 0, ... , 2^m - 2.

I've tried plugging it into the combination formula and have tried making several arguments however I cannot seem to pinpoint any particularly good rationale for this.

Any help?

2 Answers

Relevance
  • atsuo
    Lv 6
    5 months ago
    Favorite Answer

    We want to prove

    "(2^m+r)C(1+r), (2^m+r)C(2+r), ... , (2^m+r)C(2^m-1) are all even" ---(#0)

    If m = 0 then only one term (1+r)C(r+1) = 1 exists , so (#0) does not stand .

    Therefore , I think m = 1, 2, 3, ...

    Let r = 0 .

    (#0) becomes "(2^m)C(1), (2^m)C(2), ... , (2^m)C(2^m-1) are all even" ---(#1)

    When m = 1 then 2^m-1 = 1 so only one term (2)C(1) = 2 exists . Therefore (#1) stands .

    Next , assume that (#1) stands when m = k . That is ,

    "(2^k)C(1), (2^k)C(2), ... , (2^k)C(2^k-1) are all even" ---(#2)

    And when m = k+1 , the terms in (#1) become

    (2^(k+1))C(1), (2^(k+1))C(2), ... , (2^(k+1))C(2^(k+1)-1) ---(#3)

    Think that 2^k items are labelled "A" and other 2^k items are labelled "B" ,

    and we choose w (1≦w≦2^(k+1)-1) items from these 2^(k+1) items .

    If we choose p A_items and (w-p) B_items then (2^k)C(p)*(2^k)C(w-p) ways exist .

    So check the value of (2^k)C(p)*(2^k)C(w-p) when w varies .

    When 1≦w≦2^k-1 , at least one of p or w-p satisfies 1≦p≦2^k-1 or 1≦w-p≦2^k-1 .

    So (2^k)C(p)*(2^k)C(w-p) is even by (#2) .

    When w = 2^k ,

    If p=0 then w-p=2^k , so (2^k)C(p)*(2^k)C(w-p) = 1*1 = 1 .

    If 1≦p≦2^k-1 then (2^k)C(p)*(2^k)C(w-p) is even by (#2) .

    If p=2^k then w-p=0 , so (2^k)C(p)*(2^k)C(w-p) = 1*1 = 1 .

    And we can think the sum of two terms when p=0 and when p=2^k as one even term .

    When 2^k+1≦w≦2^(k+1)-1 , at least one of p or w-p satisfies 1≦p≦2^k-1 or

    1≦w-p≦2^k-1 . So (2^k)C(p)*(2^k)C(w-p) is even by (#2) .

    So (2^(k+1))C(w) = [The sum from p=0 to w] (2^k)C(p)*(2^k)C(w-p) is even

    for 1≦w≦2^(k+1)-1 . That is , (#1) stands when m = k+1 .

    Therefore (#1) stands for m ≧ 1 , this means (#0) stands when r = 0 .

    Next , assume that (#0) stands when r = k . That is ,

    "(2^m+k)C(k+1), (2^m+k)C(k+2), ... , (2^m+k)C(2^m-1) are all even" ---(#4)

    And when r = k+1 , the terms in (#0) become

    (2^m+k+1)C(k+2), (2^m+k+1)C(k+3), ... , (2^m+k+1)C(2^m-1) ---(#5)

    We know (u)C(v) = (u-1)C(v-1) + (u-1)C(v) , so the terms in (#5) become

    (2^m+k+1)C(k+2) = (2^m+k)C(k+1) + (2^m+k)C(k+2) ---(#6)

    (2^m+k+1)C(k+3) = (2^m+k)C(k+2) + (2^m+k)C(k+3) ---(#6)

    ...

    (2^m+k+1)C(2^m-1) = (2^m+k)C(2^m-2) + (2^m+k)C(2^m-1) ---(#6)

    By (#4) , the terms in the right sides of equations of (#6) are all even .

    (The terms (2^m+k)C(k+3) and (2^m+k)C(2^m-2) in (#6) are not shown in (#4) ,

    but they exist in (#4) .)

    So the terms in (#5) are all even , therefore (#0) stands when r = k+1 .

    Therefore (#0) stands when r ≧ 0 .

    • Login to reply the answers
  • 5 months ago

    Even terms are in bold.

    These lines follow lines that are entirely formed of odd terms.

    All odd term lines are lines 0, 1, 3, 7, 15, ... which are 2^n - 1 for all non-negative integers n.

    So the all even (apart from the terminal 1s) lines are 1, 2, 4, 8, 16, ... which are 2^n for all non-negative integers n.

    Attachment image
    • Login to reply the answers
Still have questions? Get your answers by asking now.