Exercise 4.1.34* ($
u_p \binom{a+b}{a}$ is the number of carries when $a,b$ are added base $p$ (Kummer))

Question

Let $a$ and $b$ be positive integers withs $a+b = n$. Show that the power of $p$ dividing $\binom{n}{a}$ is exactly the number of carries when $a$ and $b$ are added base $p$.

Richard Ganaye · Accepted Answer

\begin{proof} 
We write $a, b$ and $n = a+b$ in base $p$ in the form
$$a = \sum_{i = 0}^k a_i p^i,\qquad b  = \sum_{i = 0}^k b_i p^i, \qquad  n = a + b = \sum_{i = 0}^k c_i p^i.$$
(Here $k$ is any integer greater than the lengths of the representations of $a, b, n$ in base $p$.)

The Legendre- de Polignac's formula gives
\begin{align}

u_p\binom{n}{a} = \sum_{i = 1}^k \left ( \left \lfloor \frac{n}{p^i }ight floor - \left \lfloor \frac{a}{p^i} ight floor -  \left \lfloor \frac{b}{p^i} ight flooright ),
\end{align}
since $\left \lfloor \frac{n}{p^i } ight floor = \left \lfloor \frac{a}{p^i} ight floor= \left \lfloor \frac{b}{p^i }ight floor= 0$ if $i>k$.

We proved in Problem 33 (with $d = p$) that the carries $r_{i}$ such that
\begin{align}
&r_0 = 0\
&
\left\{
\begin{array}{lll}
r_{i+1} &= \left \lfloor \frac{a_i + b_i + r_i}{p}  ight floor &= (a_i + b_i + r_i)\  //\  p,\
c_i &= (a_i +b_i +r_i) - pr_{i+1} &=(a_i +b_i +r_i) \ \%\  p,
\end{array}
ight.
\end{align}
satisfy
\begin{align}
\sum_{j = 0}^i a_j p^j + \sum_{j = 0}^i b_j p^j = \sum_{j = 0}^i c_j p^j  + r_{i+1} p^{i+1} \qquad (i = 0, 1, \ldots,k).
\end{align}
Since $r_i = 0$ or $r_i = 1$ for all indices $i$ (and $r_0 = 0$), the number $N$ of carries when $a$ and $b$ are added in base $p$ is given by
\begin{align}
N = \sum_{i=0}^{k+1} r_i = \sum_{i=1}^{k+1} r_i = \sum_{i=0}^{k} r_{i+1}.
\end{align}
Then the equalities (4) give
\begin{align}
N &= \sum_{i=0}^{k} r_{i+1}\
&= \sum_{i=0}^{k} \frac{1}{p^{i+1}}  \left (\sum_{j = 0}^i a_j p^j + \sum_{j = 0}^i b_j p^j -\sum_{j = 0}^i c_j p^j ight).
\end{align}
If $i = k$, $\sum_{j = 0}^i a_j p^j + \sum_{j = 0}^i b_j p^j -\sum_{j = 0}^i c_j p^j = a +b - n = 0$, so
\begin{align}
N &= \sum_{i=0}^{k-1} \frac{1}{p^{i+1}}  \left (\sum_{j = 0}^i a_j p^j + \sum_{j = 0}^i b_j p^j -\sum_{j = 0}^i c_j p^j ight).
\end{align}
We proved in Problem 33 (see formula (4) of Problem 33) that
\begin{align}
&\left \{ \frac{a}{p^{i+1}} ight \}  = \frac{1}{p^{i+1}} \sum_{j = 0}^i a_j p^j, \qquad
\left \{ \frac{b}{p^{i+1}} ight \}  = \frac{1}{p^{i+1}} \sum_{j = 0}^i b_j p^j,\qquad
\left \{ \frac{n}{p^{i+1}} ight \}  = \frac{1}{d^{i+1}} \sum_{j = 0}^i c_j p^j.
\end{align}
Then formulas (8) and (9) give
\begin{align*}
N &= \sum_{i=0}^{k-1} \left( \left \{ \frac{a}{p^{i+1}} ight \} + \left \{ \frac{b}{p^{i+1}} ight \}  - \left \{ \frac{n}{p^{i+1}} ight \}  ight)\
&= \sum_{i=0}^{k-1}  \left(  \frac{a}{p^{i+1}}  - \left \lfloor  \frac{a}{p^{i+1}}  ight floor  + \frac{b}{p^{i+1}}  - \left \lfloor  \frac{b}{p^{i+1}}  ight floor - \frac{n}{p^{i+1}}  + \left \lfloor  \frac{n}{p^{i+1}}  ight floor ight)\
&=  \sum_{i=0}^{k-1}  \left(  \frac{a}{p^{i+1}}  - \left \lfloor  \frac{a}{p^{i+1}}  ight floor  + \frac{b}{p^{i+1}}  - \left \lfloor  \frac{b}{p^{i+1}}  ight floor - \frac{n}{p^{i+1}}  + \left \lfloor  \frac{n}{p^{i+1}}  ight floor ight)\
&=  \sum_{i=0}^{k-1}  \left(   - \left \lfloor  \frac{a}{p^{i+1}}  ight floor   - \left \lfloor  \frac{b}{p^{i+1}}  ight floor  + \left \lfloor  \frac{n}{p^{i+1}}  ight floor ight)&(	ext{since } a +b = n)\
&= \sum_{j = 1}^{k} \left(   \left \lfloor  \frac{n}{p^{j}} ight floor  - \left \lfloor  \frac{a}{p^{j}}  ight floor   - \left \lfloor  \frac{b}{p^{j}}  ight floor    ight)& (j = i+1)\
&=
u_p\binom{n}{a}&(	ext{by (1))}.
\end{align*}
In conclusion,
$$N = \sum_{i=0}^{k+1} r_i = 
u_p\binom{n}{a}$$
is exactly the number of carries when $a$ and $b$ are added base $p$.
\end{proof}

Exercise 4.1.34* ($\nu_p \binom{a+b}{a}$ is the number of carries when $a,b$ are added base $p$ (Kummer))

Answers

Comments

Exercise 4.1.34* ($\nu_p \binom{a+b}{a}$ is the number of carries when $a,b$ are added base $p$ (Kummer))

Answers

Comments

Add answer