11
$\begingroup$

Recently I was playing around with some numbers and I stumbled across the following formal power series:

$$\sum_{k=0}^\infty\frac{x^{ak}}{(ak)!}\biggl(\sum_{l=0}^k\binom{ak}{al}\biggr)$$

I was able to "simplify" the above expression for $a=1$:

$$\sum_{k=0}^\infty\frac{x^k}{k!}\cdot2^k=e^{2x}$$ I also managed to simplify the expression for $a=2$ with the identity $\sum_{i=0}^\infty\frac{x^{2k}}{(2k)!}=\cosh(x)$:

$$\sum_{k=0}^\infty\frac{x^{2k}}{(2k)!}\biggl(\sum_{l=0}^k\binom{2k}{2l}\biggr)=\mathbf[\cdots\mathbf]=\frac{1}{4}\cdot(e^{2x}+e^{-2x})+\frac{1}{2}=\frac{1}{2}\cdot(\cosh(2x)+1)$$

However, I couldn't come up with a general method for all $a\in\Bbb{N}$. I would be very thankful if someone could either guide me towards simplifying this expression or post his solution here.

$\endgroup$
11
$\begingroup$

You might be able to use the fact that $$\sum_{k=0}^\infty b_{ak}=\sum_{k=0}^\infty \left(\frac{1}{a}\sum_{j=0}^{a-1} \exp\left(2\pi ijk/a\right)\right)b_k.$$ For example, when $a=1$, taking $b_k = \frac{x^k}{k!}\sum_{\ell \ge 0} \binom{k}{\ell}$ yields $$\sum_{k=0}^\infty b_{k}=\sum_{k=0}^\infty \frac{x^k}{k!}\sum_{\ell \ge 0} \binom{k}{\ell}=\sum_{k=0}^\infty \frac{x^k}{k!}2^k=\exp(2x),$$ as you already obtained. For $a=2$, first note that \begin{align} \sum_{\ell \ge 0}\binom{k}{2 \ell} &= \sum_{\ell\ge 0} \left(\frac{1}{2}\sum_{j=0}^1 \exp\left(2\pi ij\ell/2\right)\right)\binom{k}{\ell}\\ &= \sum_{\ell\ge 0} \frac{1+(-1)^\ell}{2}\binom{k}{\ell}\\ &= \frac{1}{2}\sum_{\ell\ge 0} \binom{k}{\ell}+ \frac{1}{2}\sum_{\ell\ge 0} (-1)^\ell\binom{k}{\ell}\\ &= \frac{2^k+0^k}{2}. \end{align} Now taking $b_k = \frac{x^k}{k!}\sum_{\ell \ge 0}\binom{k}{2 \ell}$ yields \begin{align}\sum_{k=0}^\infty b_{2k}&=\sum_{k=0}^\infty \left( \frac{1}{2}\sum_{j=0}^1 \exp\left(\pi ijk\right)\right)\frac{x^k}{k!}\sum_{\ell \ge 0}\binom{k}{2 \ell}\\ &=\frac{1}{2}\sum_{k=0}^\infty \left(1+(-1)^k\right)\frac{x^k}{k!}\left(2^{k-1}+\frac{1}{2}[k=0]\right)\\ &=\frac{1}{4}\sum_{k=0}^\infty \frac{x^k}{k!}2^k+\frac{1}{4}\sum_{k=0}^\infty (-1)^k\frac{x^k}{k!}2^k+\frac{1}{2}\\ &=\frac{\exp(2x)+\exp(-2x)}{4} +\frac{1}{2}\\ &=\cosh^2(x), \end{align} again matching your result. For $a=3$, first note that \begin{align} \sum_{\ell \ge 0}\binom{k}{3 \ell} &= \sum_{\ell\ge 0} \left(\frac{1}{3}\sum_{j=0}^2 \exp\left(2\pi ij\ell/3\right)\right)\binom{k}{\ell}\\ &= \sum_{\ell\ge 0} \frac{1+\exp(2\pi i\ell/3)+\exp(4\pi i\ell/3)}{3}\binom{k}{\ell}\\ &= \frac{1}{3}\sum_{\ell\ge 0} \binom{k}{\ell}+ \frac{1}{3}\sum_{\ell\ge 0} \exp(2\pi i/3)^\ell\binom{k}{\ell}+ \frac{1}{3}\sum_{\ell\ge 0} \exp(4\pi i/3)^\ell\binom{k}{\ell}\\ &= \frac{2^k+(1+\exp(2\pi i/3))^k+(1+\exp(4\pi i/3))^k}{3}\\ &= \frac{2^k+\exp(\pi i/3)^k+\exp(-\pi i/3)^k}{3}. \end{align} Now taking $b_k = \frac{x^k}{k!}\sum_{\ell \ge 0}\binom{k}{3 \ell}$ yields \begin{align}\sum_{k=0}^\infty b_{3k}&=\sum_{k=0}^\infty \left( \frac{1}{3}\sum_{j=0}^2 \exp\left(2\pi ijk/3\right)\right)\frac{x^k}{k!}\sum_{\ell \ge 0}\binom{k}{3 \ell}\\ &=\frac{1}{3}\sum_{k=0}^\infty \left(1+\exp(2\pi ik/3)+\exp(4\pi ik/3)\right)\frac{x^k}{k!}\frac{2^k+\exp(\pi i/3)^k+\exp(-\pi i/3)^k}{3}\\ &=\frac{1}{9}\sum_{k=0}^\infty (1+\exp(2\pi i/3)^k+\exp(4\pi i/3)^k)(2^k+\exp(\pi i/3)^k+\exp(-\pi i/3)^k)\frac{x^k}{k!}. \end{align} Now expand the product of trinomials to obtain 9 sums that reduce to $\exp(cx)$ for various constants $c$.

Alternatively, note that: $$\sum_{k=0}^\infty \frac{x^{ak}}{(ak)!}\sum_{\ell \ge 0}\binom{ak}{a\ell} = \left(\sum_{k=0}^\infty \frac{x^{ak}}{(ak)!}\right)^2,$$ so you might as well just compute \begin{align} \sum_{k=0}^\infty \frac{x^{ak}}{(ak)!} &= \sum_{k=0}^\infty \left( \frac{1}{a}\sum_{j=0}^{a-1} \exp\left(2\pi ijk/a\right)\right)\frac{x^k}{k!} \\ &= \frac{1}{a}\sum_{j=0}^{a-1} \sum_{k=0}^\infty \frac{(\exp(2\pi ij/a)x)^k}{k!} \\ &= \frac{1}{a}\sum_{j=0}^{a-1} \exp(\exp(2\pi ij/a)x), \end{align} and then square the result.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer! Is there an online platform where I can find identities such as the one you mentioned? Or is it just something one has to know from experience? $\endgroup$ – Susp1cious Nov 16 at 22:06
  • 5
    $\begingroup$ Wilf's generatingfunctionology and Graham, Knuth, et al.'s Concrete Mathematics are good sources for manipulating sums. $\endgroup$ – Rob Pratt Nov 16 at 23:26
  • $\begingroup$ My result for $a=2$ is slightly different. Is it possible that you forgot to eliminate the $2$ from the Binomial? Shouldn't the expression be $\sum_{k=0}^\infty b_{2k}=\sum_{k=0}^\infty\biggl(\frac{1}{2}\sum_{j=0}^1\exp(\pi\ ijk)\biggr)\frac{x^k}{k!}\sum_{l\geq0}\binom{k}{l}$ $\endgroup$ – Susp1cious Nov 17 at 8:57
  • $\begingroup$ @Susp1cious, why is the bottom of your binomial coefficient $\ell$ when it is independent of $k$? $\endgroup$ – J. M. is not a mathematician Nov 17 at 15:08
  • $\begingroup$ No, I made a different error, which I should have noticed because evaluating at $x=0$ should yield 1. I’ll fix it. $\endgroup$ – Rob Pratt Nov 17 at 15:20
7
$\begingroup$

The explicit formula is as follows: $$ S_a=\frac{1}{a^2}\left(\sum_{z^a=2^a}+2\sum_{p_a(z)=0}\right)e^{az} $$ where the polynomials $p_a$ are given by A244608. For example, \begin{align} p_9(z)&= 1 - 13604 z^9 - 13359 z^{18} + 247 z^{27} + z^{36}\\ p_{10}(z)&=3125-383750 z^{10}-73749 z^{20}+502 z^{30}+z^{40} \end{align} whose roots in the complex plane look like follows:

enter image description here

enter image description here

The first few solutions are \begin{align} S_1&=e^{2 x}\\ S_2&=\frac{e^{-2 x}}{4}+\frac{e^{2 x}}{4}\\ S_3&=\frac{2 e^{-x}}{9}+\frac{e^{2 x}}{9}+\frac{2}{9} e^{\frac{x}{2}-\frac{1}{2} i \sqrt{3} x}+\frac{2}{9} e^{\frac{x}{2}+\frac{1}{2} i \sqrt{3} x}+\frac{1}{9} e^{-x-i \sqrt{3} x}+\frac{1}{9} e^{-x+i \sqrt{3} x}\\ S_4&=\frac{e^{-2 x}}{16}+\frac{1}{8} e^{(-1-i) x}+\frac{1}{8} e^{(-1+i) x}+\frac{1}{16} e^{-2 i x}+\frac{1}{16} e^{2 i x}+\frac{1}{8} e^{(1-i) x}+\frac{1}{8} e^{(1+i) x}+\frac{e^{2 x}}{16} \end{align} as given by \begin{align} p_1(z)&=0\\ p_2(z)&=0\\ p_3(z)&=1+z^3\\ p_4(z)&=4+z^4\\ p_5(z)&=-1+11z^5+z^{10}\\ p_6(z)&=-27+26z^6+z^{12} \end{align} etc. Quoting the OEIS entry, the coefficients are found as follows:

Let $\omega$ be a primitive $j$-th root of unity. Let $L(k)=\sum_{p=0}^{j-1} c(p)\omega^{kp}$ with $c(0)=2$ and $c(i)=C(j,i)$ if $i>0$. Then $p(j,X)=(X-L(1))(X-L(2))\dots(X-L([(n-1)/2]))$.

$\endgroup$
2
$\begingroup$

Actually the true generalisation for your $a=1$, $a=2$ cases is this expression for your sum: $$\frac{1}{a^2}\sum_{s=0}^{a-1}\sum_{r=0}^{a-1}e^{x\omega^r(1+\omega^s)}.$$ where $\omega$ is an $a$-th root of unity ($\omega^a=1$, $a \neq 1$).

When $a=1$ we have $\omega=1$ and your sum is $e^{2x}$. For $a=2$ we have $\omega=-1$ and your sum is $\frac{1}{4}(e^{2x}+e^{-2x}+e^0+e^0)=\frac{1}{4}(e^{2x}+e^{-2x}+2)$. Both agreeing with your observations.

Proof: Using the fact that $\sum_{l=0}^{a-1}\omega^{lr}=0$ unless $a|l$ we can show: $$\sum_{l=0}^k\binom{ak}{al}=\frac{1}{a}\sum_{s=0}^{a-1}(1+\omega^s)^{ak}$$ and$$\sum_{k=0}^\infty\frac{x^{ak}}{(ak)!}=\frac{1}{a}\sum_{r=0}^{a-1}e^{\omega^r x}.$$

Substituting the above expressions into your sum we obtain:

$$\sum_{k=0}^\infty\frac{x^{ak}}{(ak)!}\biggl(\sum_{l=0}^k\binom{ak}{al}\biggr)=\sum_{k=0}^\infty\frac{x^{ak}}{(ak)!}\frac{1}{a}\sum_{s=0}^{a-1}(1+\omega^s)^{ak}=\frac{1}{a}\sum_{s=0}^{a-1}\sum_{k=0}^\infty\frac{(x(1+\omega^s))^{ak}}{(ak)!}$$$$=\frac{1}{a}\sum_{s=0}^{a-1}(\frac{1}{a}\sum_{r=0}^{a-1}e^{x\omega^r(1+\omega^s)})=\frac{1}{a^2}\sum_{s=0}^{a-1}\sum_{r=0}^{a-1}e^{x\omega^r(1+\omega^s)}.$$

$\endgroup$
  • $\begingroup$ "Actually the true...": Are you suggesting that something is untrue in my solution? I did a sanity check via WolframAlpha that your double sum matches my square of a sum for $a=3$.. $\endgroup$ – Rob Pratt Nov 17 at 19:05
  • $\begingroup$ @RobPratt No but your answer was not a finite expression for the sum in question in terms of exponential functions which was the case for a=1 and a=2 in the OP's question. $\endgroup$ – Ivan Meir Nov 17 at 19:17
  • $\begingroup$ Right, I didn't complete the computation for $a=3$ and instead gave a result for general $a$ in terms of the square of a finite sum of exponentials. $\endgroup$ – Rob Pratt Nov 17 at 19:19

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.