${3^n\choose k}$ is divisible by $3$? 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.
 A: 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$
A: 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$.
A: 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.
A: 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$.
