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.