I recently started reading Concrete Mathematics by Graham, Knuth and Patashnik and met falling/rising factorials for the first time; it seemed like a very convenient method for evaluating particular sums.

I saw the following problem asked on a different site and tried to use falling factorials to get the answer:$$\text{Determine}\ \sum_{k=0}^\infty \frac{1}{(4k+1)(4k+2)(4k+3)(4k+4)}.$$ Here's what i did:

First I noted that $(4k)^\underline{-4}=\dfrac{1}{(4k+1)(4k+2)(4k+3)(4k+4)} $; so I rewrote the series as $$ \lim_{n\rightarrow \infty}\left(\sum_{k=0}^n (4k)^\underline{-4}\right)\;.$$ Evaluating the series I get, \begin{align} \sum_{k=0}^n (4k)^\underline{-4} &=\frac{(4k)^\underline{-3}}{-3}\Bigg|_0^{n+1}\\ &= \frac{[4(n+1)]^\underline{-3}}{-3}-\frac{0^\underline{-3}}{-3}\\ &= -\frac{1}{3}\frac{1}{[4(n+1)+1][4(n+1)+2][4(n+1)+3]}+\frac{1}{18} \end{align} I then took the limit of the closed form expression for the series above, $$ \lim_{n\rightarrow \infty}\left(-\frac{1}{3}\frac{1}{[4(n+1)+1][4(n+1)+2][4(n+1)+3]}+\frac{1}{18}\right)=\frac{1}{18}\;.$$

$ \frac{1}{18} $ is apparently the wrong answer. This is the first time that I've used the falling factorials outside of the textbook, so I'm not sure if using it on this question is correct (but I can't see why it wouldn't be). If anyone can give me a hint or explanation, it would be much appreciated.

  • $\begingroup$ Whaaat??? How do you mean these underlines in the exponent? .. and then you integrate a series.. well.. I don't say it's not correct.. but What is it??? $\endgroup$ – Berci Oct 11 '12 at 10:01
  • $\begingroup$ mathworld.wolfram.com/FallingFactorial.html $\endgroup$ – SomethingWitty Oct 11 '12 at 10:36
  • 1
    $\begingroup$ Though I can’t give you a nice fix, I turned my answer into an explanation of what goes wrong; you may find it of some small use in getting a better handle on this material. $\endgroup$ – Brian M. Scott Oct 11 '12 at 11:29

Completely revised and corrected:

The problem is that you need a chain rule to handle the factor of $4$ in $4k$, and the finite calculus doesn’t have one. In general it’s very hard to deal with composite functions other than simple shifts by adding a constant to the variable. To see the problem, consider what function $f(x)$ would have $\Delta f(x)=(2x)^{\underline 2}$. Analogy with ordinary calculus would suggest that it ought to be something like $(2x)^{\underline 3}$, probably adjusted by a constant coefficient. But

$$\begin{align*} \Delta(2x)^{\underline 3}&=\big(2(x+1)\big)^{\underline 3}-(2x)^{\underline 3}\\ &=(2x+2)(2x+1)(2x)-(2x)(2x-1)(2x-2)\\ &=4x\Big((x+1)(2x+1)-(2x-1)(x-1)\Big)\\ &=24x^2\;,\tag{1} \end{align*}$$

while $(2x)^{\underline 2}=(2x)(2x-1)=4x^2-2x$; clearly these are not constant multiples of each other. Multiplying $(1)$ by $\frac16$, as is suggested by ordinary calculus, gets the $x^2$ term right, but it does nothing to fix give us the missing first power term. Now $\Delta x^{\underline 2}=2x$, so in this case we actually can fix things up:

$$\Delta\left(\frac16(2x)^{\underline 3}-x^{\underline 2}\right)=\frac16\left(24x^2\right)-2x=4x^2-2x=(2x)^{\underline 2}\;.$$

But that was an ad hoc fix-up after the fact that doesn’t obviously point the way to a general solution even in the case of a positive exponent.

I don’t know a slick finite calculus method for evaluating your limit, but this at least explains why what you tried didn’t work.

  • $\begingroup$ Thank you!! The book didn't mention the chain rule at all; I basically just saw the 4k as an x. $\endgroup$ – SomethingWitty Oct 11 '12 at 9:45
  • $\begingroup$ Gonna have to recheck that table when i get home. $\endgroup$ – SomethingWitty Oct 11 '12 at 9:50
  • $\begingroup$ According to wolfram it converges to something entirely different wolframalpha.com/input/… $\endgroup$ – SomethingWitty Oct 11 '12 at 10:32
  • 1
    $\begingroup$ @SomethingWitty: My apologies: my mind was wandering. There is no finite calculus analogue of the chain rule, and it’s not immediately clear to me that there is a short way to get this limit. You should un-accept the answer, and I’ll delete it. $\endgroup$ – Brian M. Scott Oct 11 '12 at 10:50
  • $\begingroup$ Ok, no problem. Thanks for your help anyway. $\endgroup$ – SomethingWitty Oct 11 '12 at 11:02

You might try writing , 1/((4k+1)(4k+2)(4k+3)(4k+4))

=1/(6(4k+1)) + 1/(2(4k+3)) - 1/(4(2k+1)) - 1/(24(k+1))


As Brian M. Scott already pointed out, you need a way to handle the factor 4, or more general, you need a rule for to sum/difference $(ak+b)^{\underline m}$ where $(a,b)=(4,0)$ in your case.

Such a rule is not given in Concrete Mathematics, however you can find it in Boole's Calculus if Finite Differences, on page 68, eq.(6), it reads

$\sum (ak+b)^{\underline m} = \frac{(ak+b)^{\underline m+1}}{a(m+1)}+C,$

or equivalently

$\Delta (ak+b)^{\underline m}=am(ak+b)^{\underline m-1}.$

  • $\begingroup$ By the way, if anybody knows how to prove this, I would be happy to know (the book seems not to give a reason) $\endgroup$ – flonk Nov 19 '13 at 20:33
  • $\begingroup$ That book does not use the falling factorial, $(ak+b)^{\underline m}$. It uses $(ak+b)^{(m)}$, which it defines as $(ak+b)(a(k-1)+b)\cdots(a(k-m+1)+b)$. With this new definition, things work out nicely, but it provides no insight into the question at hand. $\endgroup$ – Mike Earnest Jul 26 '18 at 17:02

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.