If p is even and q is odd, then ##\binom{p}{q}## is even

[issacnewton]

Homework Statement

Prove that if $p, q \in \mathbb{N}$ and $p$ is even and $q$ is odd, then $\binom{p}{q}$ is even.

Relevant Equations

Mathematical Induction

If $p$ is even and $q$ is odd, then $p = 2m$ and $q = 2n - 1$, for some $m, n \in \mathbb{N}$. Let $P(m,n)$ be the statement that $\binom{2m}{2n-1}$ is even. Now, I am going to use mathematical induction here. My plan is to prove $P(1, n)$ and $P(m, 1)$ as base cases. For the inductive case, I want to assume $P(m-1, n)$ and $P(m, n-1)$ and prove $P(m, n)$. With this plan, I will prove $P(m, n)$ for all two dimensional grid of $m$ and $n$.

For $P(1, n)$, letting, $m=1$, the binomial coefficient is

$$ \binom{2}{2n-1} $$

So, $0 \leqslant 2n-1 \leqslant 2$. Since $2n-1$ is odd, I must have $2n-1 = 1$. Hence

$$ \binom{2}{2n-1} = \binom{2}{1} = 2 $$

which is even. Hence $P(1, n)$ is true. Now, for $P(m, 1)$, letting $n=1$, the binomial coefficient is

$$ \binom{2m}{1} = 2m$$

which is even. So, $P(m, 1)$ is also true. Next, for the inductive case, I assume that $P(m-1, n)$ and $P(m, n-1)$ are true. So,

$$ \binom{2m - 2}{2n-1} \text{ is even} $$
$$ \binom{2m}{2n-3} \text{ is even} $$

And I want to prove that

$$ \binom{2m}{2n-1} \text{ is even} $$

I tried using the recurrence relation here.

$$ \binom{2m}{2n-1} = \binom{2m-1}{2n-1} + \binom{2m-1}{2n-2 } $$

But I don't quite get how to proceed from here. This problem may be done with induction on one variable but I wanted to learn induction on two variables, which is more difficult. There are probably other ways to traverse the 2D grid of m , n. But, I wanted to start with this approach.

 

[fresh_42]

I would try to perform an induction on $n$ for any fixed number $p=2m$ because it has the nicer formula:
$$
\binom{p}{q}=\dfrac{p-q+1}{q}\cdot \binom{p}{q-1}
$$
For $n=1$ we get $\displaystyle{\binom p 1 =p=2m}\;$ that is even. The formula gives
\begin{align*}
\binom p q &=\binom{p}{2n-1}=\dfrac{2m-(2n-1)+1}{2n-1}\cdot \binom{p}{q-1}\\[6pt]
&=\dfrac{2m-(2n-1)+1}{2n-1}\cdot\dfrac{2m-(2n-2)+1}{2n-2}\cdot\binom{p}{q-2}
\end{align*}
Does that help? And please check whether I had a typo in the formulas.

 

[Euge]

You need to show separately that if $P(m-1, n)$ is true, then $P(m,n)$ is true, and if $P(m,n-1)$ is true, then $P(m,n)$ is true. First, suppose $P(m-1,n)$ is true. Then, as you claimed, $\binom{2m-2}{2n-1}$ is even. Continue the recurrence: $$\binom{2m-1}{2n-1} = \binom{2m-2}{2n-1} + \binom{2m-2}{2n-2}, \quad \binom{2m-1}{2n-2} = \binom{2m-2}{2n-2} + \binom{2m-2}{2n-3}$$ Then $$\binom{2m}{2n-1} = \binom{2m-2}{2n-3} + 2\binom{2m-2}{2n-2} + \binom{2m-2}{2n-1}$$ In the right hand side of this equation, the last two term terms are even (the last term is even by the induction hypothesis). By the binomial identity $n\binom{n-1}{k-1} = \binom{n}{k}$, we get $(2m-1)\binom{2m-2}{2n-3} = (2n-2)\binom{2m-1}{2n-2}$ is an even number, so since $2m-1$ is odd, then $\binom{2m-2}{2n-3}$ is even. Thus $\binom{2m}{2n-1}$ is the sum of three even numbers, which is even.

I leave it to you to show that if $P(m,n-1)$ is true, then $P(m,n)$ is true.

Just an aside -- the binomial identity $n\binom{n-1}{k-1} = k\binom{n}{k}$ gives a short proof of the statement: If $p$ is even and $q$ is odd, then the equation $(p+1)\binom{p}{q} = (q+1) \binom{p+1}{q+1}$ shows that $(p+1)\binom{p}{q}$ is even, so $\binom{p}{q}$ is even (since $p+1$ is odd). This argument was used in the induction step above.

 

[Orodruin]

You need to show separately that if $P(m-1, n)$ is true, then $P(m,n)$ is true, and if $P(m,n-1)$ is true, then $P(m,n)$ is true.

This is not necessarily true. If one can show by other means that $P(m,1)$ is true for any $m$, then it is sufficient to show that $P(m,n-1)$ implies $P(m,n)$.

Since
$$
{2m \choose 1} = 2m,
$$
$P(m,1)$ is true by construction and no inductive step on $m$ is necessary.

 

[issacnewton]

Euge, Once I prove $P(m,1)$ and $P(1, n)$ and prove the implication

$$ P(m-1, n) \wedge P(m, n-1) \Longrightarrow P(m,n) $$

I can span whole two dimensional grid of $(m,n)$. Is that not correct approach ?

 

[anuttarasammyak]

This not mathematical induction but in relation with Legendre formula　,https://en.wikipedia.org/wiki/Legendre's_formula
we expect
$$\sum_{i=1}^\infty \lfloor \frac{p}{2^i} \rfloor > \sum_{i=1}^\infty \lfloor \frac{p-q}{2^i} \rfloor + \sum_{i=1}^\infty \lfloor \frac{q}{2^i} \rfloor$$
which might be easier to prove.

 

[Euge]

Euge, Once I prove $P(m,1)$ and $P(1, n)$ and prove the implication

$$ P(m-1, n) \wedge P(m, n-1) \Longrightarrow P(m,n) $$

I can span whole two dimensional grid of $(m,n)$. Is that not correct approach ?

Yes, this is a correct approach. I thought you wanted to prove the original statement with standard two-variable induction, in which you induct along the horizontal and vertical directions. Sorry about that.

You can also induct as @Orodruin suggested or induct on along the lines $m + n = k$. There are many ways to do induction in two or more variables.

 

[issacnewton]

Thanks Euge. Can you please explain how can I do induction along the lines $m+n = k$ ? I just want to learn as many ways as possible since induction in 2 variables is not covered in introductory classes.

 

[Euge]

When $m + n = 2$, $m =1$, $n = 1$ and $\binom{2\cdot 1}{2\cdot 1-1} = \binom{2}{1} = 2$, so $P(m,n)$ is true in this case. Now assume $k > 2$ and $P(m,n)$ is true whenever $m + n < k$. If $m + n = k$, then by the induction hypothesis $\binom{2(m-1)}{2(n-1)-1} = \binom{2m-2}{2n-3}$ and $\binom{2(m-1)}{2n-1} = \binom{2m-2}{2n-1}$ are even. Thus, $\binom{2m}{2n-1} = \binom{2m-2}{2n-3} + 2\binom{2m-2}{2n-2} + \binom{2m-2}{2n-1}$ is the sum of three even numbers, which is even. Hence $P(m,n)$ is true whenever $m + n = k$.

 

[mathwonk]

since the number being computed is the number of subsets of (odd) size q in a set of (even) size p, just note that for every odd subset of an even set, the complementary set is also odd. hence the odd subsets occur in pairs.

 

[PeroK]

since the number being computed is the number of subsets of (odd) size q in a set of (even) size p, just note that for every odd subset of an even set, the complementary set is also odd. hence the odd subsets occur in pairs.

You'll need to elaborate on that. Take $p = 4, q = 3$. Using the set A, B, C, D, the subsets are:

ABC, ABD, ACD, BCD

How do they pair off in your scheme?

 

[mathwonk]

@PeroK: dohhh! oops, my mistake.
of course, in your example, the subsets of size 3 are paired with those of size 1, which are even, since p is.

which is perhaps why induction is relevant. i'll try to think more.

well p=4 is ok as above. and p=6 is ok by combining the same remark with the fact that "6 choose 3" is even since the original flawed argument works exactly when p = 2q?

hmmm...

ok, a set P is even iff it has an involution f:P-->P, f^2 = id, with no fixed points, i.e. iff the points can be paired up, (x, f(x)) with f(x)≠x.

If a set P is even with fix point free involution f:P-->P, and q is an odd number ≤ card(P) = p, then I claim f induces a fix point free involution on the set of subsets S of size q in P.

I.e. since S has an odd number q of elements, the fix point free f cannot induce an involution on S itself, so for every odd subset S, the involved set f(S) is a different set, but of the same cardinality q as S. qed.

In your example we can use the involution (AB), (CD), which pairs the subsets ABC, ABD, ACD, BCD, up with ABD, ABC, BCD, ACD. i.e. it pairs them as (ABC,ABD), (ACD,BCD).

I believe this argument is not only shorter, easier, and more insightful than an inductive argument, but now also actually correct. thank you!

Here is a version you can explain to "a person in the street": imagine a church congregation composed entirely of married couples, hence with an even number of people. Now ask how many committees one can form from this congregation having a fixed odd number q of members. These committees can also be paired up as follows: to each committee there is a "dual" committee obtained by replacing each member by that member's spouse. This dual committee cannot be the same as the original committee unless it is composed entirely of married couples, but that is impossible since the number of members q is odd. Thus the total number of such committees is even.

(The first argument proved only that the total number of committees with a (variable) odd number of members is even. Notice this argument is abstractly the same, but with a different involution, one that preserves cardinality. Moral: never give up on an argument just because it is wrong.)

You will probably believe me that I actually did give this explanation to the two people seated next to me at the pot-luck I attended tonight. ... (I seem to recall they got up and left soon afterward.)

 

[PeroK]

Here is a version you can explain to "a person in the street": imagine a church congregation composed entirely of married couples, hence with an even number of people. Now ask how many committees one can form from this congregation having a fixed odd number q of members. These committees can also be paired up as follows: to each committee there is a "dual" committee obtained by replacing each member by that member's spouse. This dual committee cannot be the same as the original committee unless it is composed entirely of married couples, but that is impossible since the number of members q is odd. Thus the total number of such committees is even.

I'm not convinced. Suppose we have 3 couples: $A_1, A_2, B_1, B_2, C_1, C_2$. We could have the subset $A_1, B_1, C_1$ and this cannot be paired with another subset using your scheme, as far as I can see.

The simplest argument that I could find is to use the basic binomial identity twice for the inductive step:
$$\binom p q = \binom {p-1} {q} + \binom {p-1} {q - 1} = \binom {p -2} {q} + 2\binom {p-2} {q-1} + \binom {p-2} {q-2}$$That identity can be justified by considering the subsets that have or have not the first element in the set.

 

[anuttarasammyak]

This not mathematical induction but in relation with Legendre formula　,https://en.wikipedia.org/wiki/Legendre's_formula
we expect
$$\sum_{i=1}^\infty \lfloor \frac{p}{2^i} \rfloor > \sum_{i=1}^\infty \lfloor \frac{p-q}{2^i} \rfloor + \sum_{i=1}^\infty \lfloor \frac{q}{2^i} \rfloor$$
which might be easier to prove.

Formula to be proved is
$$\sum_{i=1}^\infty \lfloor \frac{2(m+n-1)}{2^i} \rfloor > \sum_{i=1}^\infty \lfloor \frac{2m-1}{2^i} \rfloor + \sum_{i=1}^\infty \lfloor \frac{2n-1}{2^i} \rfloor$$
$$LHS-RHS=(m+n-1)-(m-1)-(n-1)+\sum_{i=2}^\infty \lfloor \frac{2(m+n-1)}{2^i} \rfloor - \sum_{i=2}^\infty \lfloor \frac{2m-1}{2^i} \rfloor - \sum_{i=2}^\infty \lfloor \frac{2n-1}{2^i} \rfloor$$
$$=1+[ \sum_{i=2}^\infty \lfloor \frac{2(m+n-1)}{2^i} \rfloor - \sum_{i=2}^\infty \lfloor \frac{2m-1}{2^i} \rfloor - \sum_{i=2}^\infty \lfloor \frac{2n-1}{2^i} \rfloor ]$$
[ ] part is not negative as shown below. So LHS > RHS.

x=m+a, y=n+b, 0 $\leq$ a,b < 1
$$\lfloor x+y \rfloor - \lfloor x \rfloor - \lfloor y \rfloor = \lfloor a+b \rfloor \geqq 0$$

 

[Euge]

This was buried in my answer, but for a short, non-inductive proof of the result, observe that $(p+1)\binom{p}{q} = (q+1)\binom{p+1}{q+1}$ is even because $q + 1$ is; since $p+1$ is odd, we deduce $\binom{p}{q}$ is even.

 

[mathwonk]

@PeroK: I don't understand your objection. According to the rule for forming the dual committee, the subset A1B1C1 is dual to the subset A2B2C2, obtained by replacing each member by their spouse/partner. I.e. just change each subscript to the opposite subscript. Abstractly, just apply the global involution to each element of the subset.

 

[PeroK]

@PeroK: I don't understand your objection. According to the rule for forming the dual committee, the subset A1B1C1 is dual to the subset A2B2C2, obtained by replacing each member by their spouse/partner. I.e. just change each subscript to the opposite subscript. Abstractly, just apply the global involution to each element of the subset.

Yes, I see it now. I was thinking only one replacement for some reason.

 

[mathwonk]

ah yes, that's what happens in the somewhat atypical example of "4 choose 3" that I used as illustration. for clarity I should have said the dual of ABC is BAD = ABD,.....

 

[issacnewton]

I just wanted to present the strong induction proof as suggested by Euge in post #9. Let $k = m+n$. Here the base case is $k=2$ and $k=3$. For $k=2$, I have $m=1, n=1$ and Euge has shown that $P(1,1)$ is true. For $k=3$, I have two cases to consider.
Case 1) $m=1, n=2$

$$ \binom{2}{2(2)-1} = \binom{2}{3} = 0 \text{ using definition} $$

which is an even number.

Case 2) $m=2, n=1$

$$ \binom{2(2)}{2(1)-1} = \binom{4}{1} = 4 $$

which is also an even number. So, $P(1, 2)$ is true and $P(2, 1)$ is true, which means that the statement is true for $k=3$.
Now, let $k \geqslant 3$ be arbitrary in $\mathbb{N}$. Also, assume that $P(m,n)$ is true for $2 \leqslant s \leqslant k$. I have to show that the statement is true for $k+1$. Since $k+1 = m+n+1$, there are two cases to consider.

Case 1) Prove that $P(m+1, n)$ is true

$$ \binom{2(m+1)}{2n-1} = \binom{2m+2}{2n-1} $$

Using recurrence relation, I have

$$ = \binom{2m+1}{2n-1} + \binom{2m+1}{2n-2} $$

$$ = \binom{2m}{2n-1} + \binom{2m}{2n-2} + \binom{2m}{2n-2} + \binom{2m}{2n-3} $$

$$ \binom{2(m+1)}{2n-1} = \binom{2m}{2n-1} +2 \binom{2m}{2n-2} + \binom{2m}{2n-3} \cdots\cdots (1) $$

Since statement is true for $k=m+n$ by inductive hypothesis, $P(m,n)$ is true, so

$$ \binom{2m}{2n-1} \text{ is even} $$

first term in eq (1) is even. second term in eq (1) is even due to the multiplying factor of 2. Now, $2 \leqslant k$. So, $2 \leqslant k-1 \leqslant k$. By inductive hypothesis, the statement is true for $k-1 = m+(n-1)$. Hence $P(m, n-1)$ is true.

$$ \therefore \binom{2m}{2(n-1)-1} = \binom{2m}{2n-3} \text{ is even} $$

third term in eq (1) is even. Hence LHS in eq (1) is even

$$ \binom{2(m+1)}{2n-1} \text{ is even} $$

So, $P(m+1, n)$ is true.

Case 2) Prove that $P(m, n+1)$ is true

$$ \binom{2m}{2(n+1)-1} = \binom{2m}{2n+1} = \binom{2m-1}{2n+1} + \binom{2m-1}{2n}$$

$$ = \binom{2m-2}{2n+1} + \binom{2m-2}{2n} + \binom{2m-2}{2n} + \binom{2m-2}{2n-1} $$

$$ = \binom{2m-2}{2n+1} + 2\binom{2m-2}{2n} + \binom{2m-2}{2n-1} $$

$$ \binom{2m}{2(n+1)-1} = \binom{2(m-1)}{2(n+1)-1} + 2\binom{2m-2}{2n} + \binom{2(m-1)}{2n-1} \cdots\cdots (2)$$

second term in eq (2) is even due to multiplying factor 2. By inductive hypothesis, statement is true for $k = m+n = (m-1) + (n+1)$. So, $P(m-1, n+1)$ is true. So, first term in eq (2) is even

$$ \binom{2(m-1)}{2(n+1)-1} \text{ is even} $$

Also, $2 \leqslant k-1 \leqslant k$ and again by inductive hypothesis, statement is true for $k-1 = (m-1) + n$. Hence, $P(m-1, n)$ is true. So, third term in eq (2) is even

$$ \binom{2(m-1)}{2n-1}\text{ is even} $$

Hence LHS in eq (2) is even

$$ \binom{2m}{2(n+1)-1} \text{ is even} $$

So, $P(m, n+1)$ is true. So, statement is true for $k+1 = m+n+1$. By principle of strong induction, $P(m,n)$ is true for all $m,n \in \mathbb{N}$.

Does this look like a valid strong induction proof ?
Thanks

 

[Euge]

Hi @issacnewton, in your inductive step you assumed $k \ge 3$ and the claim holds whenever $2 \le m + n \le k$. So it is unnecessary to prove $P(m,n)$ is true whenever $m + n = 3$. Also, in your inductive step, you assume $k = m + n$, but it should be $k + 1 = m + n$, since you are trying to prove $P(m,n)$ when $m + n = k + 1$. Then note $P(m-1, n)$ and $P(m-1,n-1)$ hold by the induction hypothesis. Hence $\binom{2(m-1)}{2n-1} + \binom{2(m-1)}{2(n-1)-1} + 2\binom{2m-2}{2n-2}$ is even, i.e., $\binom{2m}{2n-1}$ is even.