${3^n\choose k}$ is divisible by $3$?

Question

How can I prove that ${3^n\choose k}$ is divisible by $3$ for all positive integer values of $n$? (where $k$ is any positive integer smaller than $3^n$) Can you use induction? Thanks.

Answer 1

Hint: Notice that $$\binom{3^n}{k}=\sum_{a+b+c=k}\binom{3^{n-1}}{a}\binom{3^{n-1}}{b}\binom{3^{n-1}}{c}$$summing over all valid ordered triples $(a,b,c)$ of non-negative integers.

Answer 2

I just want to demonstrate the relevance of if $p$ is prime and $0<t<p$ then $p$ divides $\displaystyle \binom p t$

Consider $$\begin{split}(x+y)^p & =\sum_{k=0}^p \binom p k x^{p-l} y^{k} \\ & =x^p+\binom p 1x^{p-1}y+\binom p 2x^{p-2}y^2+\cdots+\binom{p}{p-1}xy^{p-1}+y^p\\ & = x^p + y^p \mod p \end{split}$$

Hence $$\begin{split} (x+y)^{p^n} &= \left((x+y)^p\right)^{p^{n-1}} \\ &= \left(x^p+y^p \mod p\right)^{p^{n-1}}\\ &= (\left(x^p+y^p \mod p\right)^p)^{p^{n-2}}\\ &= \left(x^{p^2}+y^{p^2} \mod p\right)^{p^{n-2}}\\ & \vdots\\ & = x^{p^n}+y^{p^n} \mod p \end{split}$$

But also $$\begin{split} (x+y)^{p^n} & =\sum_{k=0}^{p^n} \binom{p^n}{k} x^{p^n-l} y^{k} \\ & =x^{p^n}+\binom{p^n}{1}x^{p^n-1}y+\binom{p^n}{2}x^{p^n-2}y^2+\cdots+\binom{p^n}{p^n-1}xy^{p^n-1}+y^{p^n}\\ & = x^{p^n}+y^{p^n} \mod p \end{split}$$

Therefore $p$ divides $\displaystyle\binom{p^n}{k}$ for all $k$ with $0<k<p^n$

Answer 3

This is a consequence of Lucas's Theorem:

$${a \choose b} \equiv \prod {a_j \choose b_j} \pmod p$$

for prime $p$, where $a = \sum_{j = 0}^n a_j ~p^j$ and $b = \sum_{k = 0}^n b_j~ p^j$.

The original question is thus equivalent to showing (for $a=3^n$) that $\exists j.{a_j \choose k_j} \equiv 0 \pmod p$.

So just to show that there is a pair such that $k_j > a_j$ which is observable from the ternary representation of $3^n$ and $k$.

Answer 4

Looking at the fractional expansion of the binomial coefficient, you can cancel out factors of 3 in the $(3n+1)^\text{th}$ value in the numerator with the $(3n)^\text{th}$ value in the denominator, for example:

$${3^3 \choose k} = \begin{array} {c} 27 & 26 & 25 & \color{red}{24} & 23 & 22 & \color{blue}{21} & 20 & 19 & \color{green}{18} & 17 & 16 & \color{orange}{15} & \dots & 27 - (k - 1) \\ \hline 1 & 2 & \color{red}{3} & 4 & 5 & \color{blue}{6} & 7 & 8 & \color{green}{9} & 10 & 11 & \color{orange}{12} & 13 & \dots & k \end{array}$$

So you get $\pi_3(\text{Numerator}) - \pi_3(\text{Denominator}) = \pi_3(3^n) - \pi_3(k) > 0$.