- #1

issacnewton

- 1,024

- 35

- 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.

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.