# Polynomial expansions via prime-base digits

Fix a prime number $$p$$. If $$n$$ is a positive integer, then denote $$\text{\omega_{p,k}(n):=\# of k's in the p-ary expansion of n}$$ and the total sum of all its $$p$$-ary digits by $$\Omega_p(n):=\sum_{k=0}^{p-1}k\cdot\omega_{p,k}(n).$$

Question. Given a prime $$p$$ and for each $$n\in\Bbb{N}$$, is this true? $$\prod_{k=0}^{p-1}\left(\frac{X^{k+1}-Y^{k+1}}{X-Y}\right)^{\omega_{p,k}(n)} =\sum_{\Omega_p(j)+\Omega_p(n-j)=\Omega_p(n)}^{0\leq j\leq n} X^{\Omega_p(j)}\cdot\,\,Y^{\Omega_p(n-j)}.$$

Example. If $$p=2$$ and $$s_2(n)=\#$$ the sum of binary digits of $$n$$, then $$(X+Y)^{s_2(n)}=\sum_{s_2(j)+s_2(n-j)=s_2(n)}^{0\leq j\leq n} X^{s_2(j)}\cdot\,\,Y^{s_2(n-j)}.$$

## 1 Answer

First we notice that the equality $$\Omega_p(a)+\Omega_p(b)=\Omega_p(a+b)$$ happens if and only if there are no carries when adding $$a+b$$ in base $$p$$. Indeed the number of carries is equal to $$\frac{\Omega_p(a)+\Omega_p(b)-\Omega_p(a+b)}{p-1}$$ which is also equal to $$\nu_p\left(\binom{a+b}{a}\right)$$ by Kummer's theorem. This is equivalent to saying that the base $$p$$ expansions of $$a,b$$ $$a=a_0+a_1p+a_2p^2+\cdots , b=b_0+b_1p+b_2p^2+\cdots$$ satisfy $$a_i+b_i\le p-1$$ for all $$i$$.

Consider the generating function $$F(X,Y,t)=\sum_{n\geq 0}\left(\sum_{\Omega_p(j)+\Omega_p(n-j)=\Omega_p(n)}^{0\leq j\leq n} X^{\Omega_p(j)}\cdot\,\,Y^{\Omega_p(n-j)}\right)t^n$$ where the coefficient of $$t^n$$ is the right hand side of your identity. By the observation above this can also be written as $$F(X,Y,t)=\sum_{\Omega_p(a)+\Omega_p(b)=\Omega_p(a+b)}t^{a+b}X^{\Omega(a)}Y^{\Omega(b)}$$ $$=\sum_{a_i+b_i\le p-1}t^{a+b}X^{\sum a_i}Y^{\sum b_i}=\prod_{i=1}^{\infty} \left(\sum_{a_i+b_i\le p-1} X^{a_i}Y^{b_i}t^{(a_i+b_i)p^i}\right)$$ $$=\prod_{i=1}^{\infty} \left(\sum_{k=0}^{p-1}\left(\frac{X^{k+1}-Y^{k+1}}{X-Y}\right) t^{kp^i}\right)$$ from this last expression we see that the coefficient of $$t^n$$ is equal to $$\prod_{k=0}^{p-1}\left(\frac{X^{k+1}-Y^{k+1}}{X-Y}\right)^{\omega_{p,k}(n)}$$ which is the left hand side of our identity, as desired.

• Really nice, Gjergji. – T. Amdeberhan Sep 28 '18 at 17:31