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)}.$$


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.