Prove that if $n, k \in \mathbb{N}$ and $n$ is even and $k$ is odd, then $ \binom{n}{k} $ is even. Here is what I am doing. Let $ n = 2p $ and $ k = 2q – 1 $, where $p, q \in \mathbb{N} $. Then, let $P(p, q)$ be the statement that
$$ \binom{2p}{2q-1} \text{ is even} $$
Here, I am going to fix $q$ and do induction on $p$. So, base case is $p = 1$. Consider
$$ \binom{2}{2q-1} $$
For the non zero value of the binomial coefficient, we must have $ 2q-1 \leqslant 2$. Or $ 2q \leqslant 3$. Since $ q \in \mathbb{N}$, we must have $ q = 1$. Then,
$$ \binom{2}{2q-1} = \binom{2}{1} = 2 $$
So, for $p=1$, $P(1, q)$ is true. Now, suppose that $ p \geqslant 1 $ be arbitrary in $\mathbb{N}$. Suppose that $P(p, q)$ is true. i.e.
$$ \binom{2p}{2q-1} \text{ is even} $$
Now, I have to prove that
$$ \binom{2(p+1)}{2q-1} \text{ is even} $$
And, this is where I am stuck now.
Best Answer
$$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$ $$=\binom{n-2}{r}+2\binom{n-2}{r-1}+\binom{n-2}{r-2}$$ So if $\binom{n-2}{r}$ and $\binom{n-2}{r-2}$ are even that's enough. So to prove $\binom{2(p+1)}{2q-1}$ is even you need that $\binom{2p}{2q-1}$ and $\binom{2p}{2q-3}$ are even, which are covered by $P(p,q)$ and $P(p,q-1)$.
Others have objected to the way the base case was handled. This can be changed easily: We can prove the base case $P(q,q)$ for each induction on $p$, as $\binom{2q}{2q-1}=2q$ is even. This gives us $P(p,q)$ for $p \ge q$ which is every case we care about.
However I don't think there is any issue with starting the induction at the base case $\binom{0}{2q-1}$, as the induction on $p$ holds regardless of whether $q$ is between $0$ and $p$. You just define everything outside of the usual Pascal's triangle to be $0$ and the formulae still hold.