\problemdata      
        {counting-20} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {Eric Ho} % Source (if known)
        {S02 PS8} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).

\begin{problem}
In this problem, we will prove
\begin{theorem*}[Lucas]

For all $n,k$ and prime number $p$, let the base $p$ representation of
$n$ be $(a_0,a_1,...,a_j)$ and the base $p$ representation of $k$ be
$(b_0,b_1,...,b_j)$.  Then
\[
\binom{n}{k} \equiv \binom{a_0}{b_0}\binom{a_1}{b_1}\cdots\binom{a_j}{b_j} \pmod{p}.
\]
\end{theorem*}

For example, if $n = 588, k=277, p=5$, then in base $p$, $n = 4323$ and
$k=2102$, and the theorem states that
\[
\binom{588}{277} = \binom{4}{2} \binom{3}{1} \binom{2}{0}
\binom{3}{2}\pmod{5}.
\]
We can use a
computer to verify that both sides yield a remainder of $4$ when divided
by $5$.

This is an interesting theorem because it tells us there are exactly
$(1+a_0)(1+a_1)(1+a_2)...(1+a_j)$ values of non-multiples of $p$ in the
$n^{th}$ row of Pascal's triangle.  The following steps will help you prove
this theorem.

\begin{problemparts}

\problempart
Show that
\[
k\binom{p^{r}}{k} = p^{r}\binom{p^{r}-1}{k-1},
\]
where $r=\log_p{n}$ and $0<k<p^{r}$.

\solution{ Plug $n=p^{r}$ in the right hand side of the formula yields
\begin{eqnarray*}
p^{r}\binom{p^{r}-1}{k-1} &= &n\binom{n-1}{k-1}\\
&= &k\frac{n}{k}\binom{n-1}{k-1}\\
&= &k\frac{n(n-1)!}{k(k-1)!(n-k)!}\\
&= &k\frac{n!}{k!(n-k)!}\\
&= &k\binom{n}{k}\\
&= &k\binom{p^{r}}{k}\\ 
\end{eqnarray*}
}

\problempart Argue that $p$ divides $\dbinom{p^{r}}{k}$. \hint: What are
the bounds on the number of powers of $p$ that divides the two sides of
the equation in (a)?  

\solution{ The right hand side of the equation in (a) is
$p^{r}\dbinom{p^{r}-1}{k-1}$.  \emph{At least} $r$ powers of $p$ divides
this term.  The left hand side of the equation in (a) is
$k\dbinom{p^{r}}{k}$.  \emph{At most} $r-1$ powers of $p$ divides $k$,
since $k<p^{r}$.  Therefore $p$ must divide $\dbinom{p^{r}}{k}$.}

The previous part implies that $\dbinom{p^{r}}{k}=0\pmod{p}$. 
The exception is when $k=0$ or $k=p^{r}$ in which
$\dbinom{p^{r}}{k}=1\pmod{p}$. 


\problempart
Show that $(1+x)^{p^{r}} = 1 + x^{p^{r}} \pmod{p}$. 

\solution{
Expand the left hand side of the equation using the binominal theorem.  
This yields $\binom{p^{r}}{1}1^{p^{r}} + \binom{p^{r}}{2}1^{p^{r-1}}x + ... + \binom{p^{r}}{p^{r}}x^{p^{r}}$. 
The coefficients of all middle terms are $0\pmod{p}$, whereas the coefficients for the first and last term 
is $1\pmod{p}$ (from (b)).  This yields the right hand side of the equation. 
}


\problempart
Show that $(1+x)^{588} = (1+x^{125})^{4}(1+x^{25})^{3}(1+x^{5})^{2}(1+x)^{3} \pmod{5}$
\solution{
It follows from (c): \\
\begin{eqnarray*}
(1+x)^{588} &= &(1+x)^{4(125)}(1+x)^{3(25)}(1+x)^{2(5)}(1+x)^{3}\\
            &= &(1+x^{125})^{4}(1+x^{25})^{3}(1+x^{5})^{2}(1+x)^{3} \pmod{5}   
\end{eqnarray*} 
}

\problempart
Show that
\[
\binom{588}{277}=
\binom{4}{2}\binom{3}{1}\binom{2}{0}\binom{3}{2}\pmod{5}.
\]
\hint What are the coefficients of $x^{277}$ on both sides of the equation in (d)?

\solution{
The coefficient of the $x^{277}$ term on the left hand side is $\binom{588}{277}$. 
For the right hand side, since $277 = 2*125 + 1*25 + 2*1$,  the $x^{277}$ term comes
exactly from the second term in $(1+x^{125})^{4}$, the first term in $(1+x^{25})^{3}$, 
and the second term in $(1+x)^{3}$.  Their coefficients are exactly $\binom{4}{2}$,
$\binom{3}{1}$, $\binom{2}{0}$, and $\binom{3}{2}$.  Multiplying them yields the
identity we are trying to show. 
}

\problempart
Briefly generalize parts (d) and (e) and prove the theorem. 

\solution{
Generalizing (e) yields the formula $(1+x)^{n} = (1+x^{p^{j}})^{a_0}(1+x^{p^{j-1}})^{a_1}(1+x^{p^{j-2}})^{a_2}...(1+x)^{a_j}$. 
Generalizing (f) implies that the coefficient of the $x^{k}$ term on the right hand side of the equation
comes from the $(b_0,b_1,...,b_j)^{th}$ corresponding term on the right, since 
$k={b_0}^{p^{j}}+{b_1}^{p^{j-1}}+ {b_2}^{p^{j-2}} + ... + {b_j}$.  Comparing coefficients
yields:

\\
\begin{center}
\[
\binom{n}{k} = \binom{a_0}{b_0}\binom{a_1}{b_1}...\binom{a_j}{b_j} \pmod{p}
\]
\end{center}
}

\end{problemparts}
\end{problem}

