The series $$F(n,m) := 1^n + 2^n + \ldots + m^n = \sum_{k=1}^m k^n$$

Is known as the Faulhaber's Series.

I've tried to find a formula for this similar series but I've failed so far.

$$\mathcal{F}(n,m) := m^n - (m-1)^n + (m-2)^n -\ldots\pm 1^n= \sum_{k=1}^m (-1)^{m-k}k^n$$


Thanks to André Nicolas' answer I arrived to the following formula:

$$\mathcal{F}(n,m) = (-1)^m\left(F(n,m) - 2^{n+1}F\left(n,\lfloor m/2\rfloor\right)\right)$$

  • $\begingroup$ My immediate impulse is to smack it with a (bivariate?) generating function hammer and see what comes out. Shouldn't be too bad, either. $\endgroup$ – Semiclassical Aug 1 '14 at 16:37
  • $\begingroup$ @Semiclassical Aren't generating functions for adding infinitely many terms? I just want to add $m$. $\endgroup$ – Darth Geek Aug 1 '14 at 16:41
  • $\begingroup$ You want infinitely many different integer $n$, though. So one generating function approach is to let $F(x)=\sum_{n=0}^\infty \mathcal{F}_{n,m}x^n$. (Though doing $x^n/n!$ seems easier to work with right now---it leads to a nice form for $F(x)$.) $\endgroup$ – Semiclassical Aug 1 '14 at 16:43
  • $\begingroup$ @ThomasAndrews thanks, edited. $\endgroup$ – Darth Geek Aug 1 '14 at 16:47

Hint: For $1^4-2^4+3^4-4^4+5^4-6^4+7^4-8^4+9^4$ we would use $$(1^4+2^4+\cdots +9^4)-(2)(2^4+4^4+6^4+8^4).$$

And $2^4+4^4+6^4+8^4=2^4(1^4+2^4+3^4+4^4)$.

One can call it Faulhaber minus Faulhaber.

  • $\begingroup$ So would it be something like $\mathcal{F}_{n,m} = (-1)^m\left(F_{n,m} - 2^{n+1}F_{n,\lfloor\frac{m}{2}\rfloor}\right)$? $\endgroup$ – Darth Geek Aug 1 '14 at 16:51
  • $\begingroup$ Something like that. The components are right, the $\frac{m}{2}$ is not quite right, there is a greatest integer ("floor") symbol missing. $\endgroup$ – André Nicolas Aug 1 '14 at 16:55

The "generating-function hammer" approach I mentioned above proceeds by computing a formal power series in $\mathcal{F}_{n,m}$:

\begin{align} \mathcal{F}_m(x)\equiv\sum_{n=0}^\infty \mathcal{F}_{n,m}\frac{x^n}{n!} &=\sum_{n=0}^\infty\left(\sum_{k=1}^m (-1)^{m-k}k^n\right)\frac{x^n}{n!}\\ &=\sum_{k=1}^m(-1)^{m-k}\sum_{n=0}^\infty \frac{(kx)^n}{n!}\\ &=\sum_{k=1}^m(-1)^{m-k} e^{kx}\\ &=(-1)^m \sum_{k=1}^m (-e^x)^k \\&=(-1)^m \frac{(-e^x)-(-e^x)^{m+1}}{1-(-e^x)}=\frac{e^{mx}\pm 1}{1+e^{-x}} \end{align} where we have used the Taylor series for the exponential and the geometric series. (The $\pm$ in the last equation is for odd/even $m$.)

Now, suppose we had not done the alternating series. One may confirm easily that we would have instead received the generating function $$\mathcal{G}_m(x)=\sum_{k=1}^m e^{kx}=\frac{e^{mx}-1}{1-e^{-x}}$$ (Note that $\mathcal{G}_{n,m}$ is identical to the $F_{n,m}$ defined in the problem; it's merely a matter of personal taste that I use this instead.) Observe that \begin{align} \mathcal{F}_m(x)\mp \, \mathcal{G}_m(x) &=\frac{e^{mx}\pm 1}{1+e^{-x}}\mp \frac{e^{mx}-1}{1-e^{-x}} \\ &=-2\frac{e^{(m-1)x}-1}{1-e^{-2x}}\\ &=-2 G_{\frac{m-1}{2}}(2x), \hspace{1.8cm}(m \text{ odd})\\ &=+2\frac{e^{(m/2)x}-1}{1-e^{-2x}}\\ &=+2 G_{\frac{m}{2}}(2x), \hspace{2cm}(m \text{ even})\\ \end{align} Identifying coefficients, we conclude that

\begin{align} \mathcal{F}_{n,m} &=\begin{cases} \mathcal{G}_{n,m}-2^{n+1}G_{n,\frac{m-1}{2}},& m\text{ odd}\\ -\mathcal{G}_{n,m}+2^{n+1}G_{n,\frac{m}{2}},& m\text{ even} \end{cases}\\ &=(-1)^{m-1}\left(\mathcal{G}_{n,m}-2^{n+1}G_{n,\lfloor m/2 \rfloor}\right) \end{align}

So we have derived (by much more formal means) the same equation glimpsed from Andre's answer. Note that while we had to struggle to relate this to the generating function for the Faulhaber result, getting to $\mathcal{F}(x)$ itself was rather simple. This is useful, since a singularity analysis of this generating function yields (via the Cauchy integral formula and steepest descent) asymptotic results for the alternating Faulhaber series. The curious reader should see Flajolet & Sedgwick's Analytic Combinatorics for a full treatment of this subject.

  • $\begingroup$ @DarthGeek: Note that my solution differs from the one you gave by an overall sign, so one of us has made a slip somewhere. $\endgroup$ – Semiclassical Aug 1 '14 at 19:43

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.