Mathematical Induction over two numbers

Question

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.

Answer 1

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

Answer 2

Personally I find combinatorial proofs to be the most satisfying when proving things about binomial coefficients. Interpret $$\binom n k$$ as the number of $k$-element subsets of $\{1,2,\dots,n\}$. One way to show that there an even number of subsets would be to group them up into pairs.

If you'd like to figure out how to do that for yourself stop here, otherwise read on:

Pair the set $\{a_1,\dots,a_k\}$ with the set $\{n+1-a_1,\dots,n+1-a_k\}$. Show that each set is paired with exactly one other and---crucially---that no set is paired with itself! (That last bit is where the parities of $n$ and $k$ will come into play.)

Answer 3

I do not think that you are covering the base case(s) and the induction correctly! Suppose you manage to prove the inductrion step $P(p,q)\implies P(p+1,q)$. Now you only have $P(1,1)$, so how would this ever get you to other values of $q$?

---

Instead, I would suggest proving in general that $P(p,1)$ is true, and from those (base cases) move on to prove that: $$ P(p,q)\implies P(p,q+1) $$

---

Proving $P(p,1)$ is quite simple: $1\cdot 2\cdot...\cdot p$ is even for $p>1$.

Answer 4

Alternative approach: Use Legendre's formula.

Given that $~n~$ is even, and that $~0 < k < n ~: ~k ~$ is odd.

To prove:

$$\sum_{i=1}^\infty \left\lfloor \frac{n}{2^i} \right\rfloor > \left\{ ~\sum_{i=1}^\infty \left\lfloor \frac{k}{2^i} \right\rfloor ~\right\} + \left\{ ~\sum_{i=1}^\infty \left\lfloor \frac{n-k}{2^i} \right\rfloor ~\right\}. \tag1 $$

(1) above can be proven column by column, be examining each value of $~i,~$ in turn.

---

$\underline{i = 1}$

Since $~n~$ is even, there exists a positive integer $~j~$ such that $~\displaystyle n = 2j \implies \left\lfloor \frac{n}{2^1} \right\rfloor = j.$

Since $~k~$ is odd, there exists a non-negative integer $~r~$ such that $~\displaystyle k = 2r+1 \implies \left\lfloor \frac{k}{2^1} \right\rfloor = r.$

Since $~n~$ is even and $~k~$ is odd, $~n-k~$ is odd.
Therefore, there exists a non-negative integer $~s~$ such that $~\displaystyle n-k = 2s+1 \implies \left\lfloor \frac{n-k}{2^1} \right\rfloor = s.$

Further, you have that $~2j = n = k + (n-k) = (2r + 1) + (2s+1) \implies ~$
$2j = 2(r + s + 1) \implies j > (r + s).$

Therefore, when evaluating the assertion in (1) above, you have that strict inequality holds when $~i = 1.~$

---

$\underline{i \geq 2}$

Therefore the entire problem is reduced to showing that for all $~i \in \Bbb{Z_{\geq 2}},~$ you have that

$$\left\lfloor \frac{n}{2^i} \right\rfloor \geq \left\lfloor \frac{k}{2^i} \right\rfloor + \left\lfloor \frac{n-k}{2^i} \right\rfloor. \tag2 $$

However, the assertion in (2) above is an immediate consequence of the (easily proven) lemma that given any $~x,y,z \in \Bbb{Z^+},~$ that

$$\left\lfloor \frac{x+y}{z} \right\rfloor \geq \left\lfloor \frac{x}{z} \right\rfloor + \left\lfloor \frac{y}{z} \right\rfloor. \tag3 $$

That is, the assertion in (3) is easily proven by assuming that $~x,y~$ can each be expressed as

• $~x = Mz + u ~: ~M \in \Bbb{Z_{\geq 0}}, ~u \in \{0,1,\cdots,z-1\},$

• $~y = Pz + v ~: ~P \in \Bbb{Z_{\geq 0}}, ~v \in \{0,1,\cdots,z-1\},$

and seeing where this leads.