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?

Relevance
• atsuo
Lv 6
5 months ago

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 .