12
$\begingroup$

I want to know if there exists some way, approximate or exact, to do a partial sum of falling factorials of the kind:

$$\sum_{k=i}^{n}(a+k)_{h}$$ where all are constants (here $(r)_s:=r(r-1)\cdots (r-s+1)$ represent a falling factorial).

And I'm interested too in some partial sum like this

$$\sum_{k=i}^{n}(a+k)_{h}r^k$$

In particular I want a closed form to this formula:

$$\sum_{m=0}^{3}\left(\sum_{k=1}^{19-m}(19-k)_m\right )^{-1} \left(-(19)_m+\sum_{k=0}^{19-m}(19-k)_m q^k\right )$$

Possibly there is not a closed form but I don't know. I started to read about hypergeometric series but this topic is completely new to me so I don't have a clear way to approach to my question by now.

I will appreciate any help. If you can show me via some link or bibliography is fine too. Thank you in advance.


UPDATE

Ok, I was reading the book of Graham that @ncmathsadist said to me and I have a partial answer. The question is close to some general topics on discrete maths (that I unfortunately forget).

The point is that an analogue to $\int_{a}^{b}x^n dx=\frac{x^{n+1}}{n+1}\Big|_{a}^{b}\ $ on difference calculus is

$$\sum\nolimits_{a}^{b}(k)_n\delta k =\frac{(k)_{n+1}}{n+1}\bigg|_{a}^{b}$$

For the second case I can use an analogue to integration by parts that is named summation by parts:

$$\sum f(k)\Delta g(k) \delta k=f(k)g(k)-\sum \Delta f(k) g(k+1)\delta k$$

But I dont get any closed form, so I assumed these formulas haven't closed forms.

$\endgroup$
  • 2
    $\begingroup$ Consult the book Concrete Mathematics. $\endgroup$ – ncmathsadist May 30 '15 at 2:23
  • 2
    $\begingroup$ Frankly, I agree with your P.S. This seems to me a perfectly reasonable question, though not, unfortunately, one with which I’m likely to be able to help. $\endgroup$ – Brian M. Scott May 30 '15 at 3:30
  • 1
    $\begingroup$ @Brian, ty very much for your support... I really dont know about this topic, and I read some books of discrete maths. When I see negative votes I though that my question was "so easy" to answer or something like this. I dont want people work for me or so but I think my question is legit. $\endgroup$ – Masacroso May 30 '15 at 3:39
4
$\begingroup$

I like Knuth's notation for falling factorials better:

$$ \alpha^{\underline{h}} = \alpha \cdot (\alpha - 1) \cdot \dotsm \cdot (\alpha - h + 1) $$

First note that:

$$ \Delta \alpha^{\underline{h}} = (\alpha + 1)^{\underline{h}} -\alpha^{\underline{h}} = (\alpha + 1) \cdot \alpha^{\underline{h - 1}} - \alpha^{\underline{h - 1}} \cdot (\alpha - h + 1) = h \alpha^{\underline{h - 1}} $$

This suggests:

$$ \sum_{0 \le k \le n} (\alpha + k)^{\underline{h}} = \frac{(\alpha + n + 1)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} $$

This we prove by induction.

Base: $n = 0$ gives:

$\begin{align} \sum_{0 \le k \le 0} (\alpha + k)^{\underline{h}} &= \alpha^{\underline{h}} \\ \frac{(\alpha + 1)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} &= \frac{1}{h + 1} \Delta \alpha^{\underline{h + 1}} \\ &= \alpha^{\underline{h}} \end{align}$

This checks out.

Induction: Assume it is true for $n$, look at $n + 1$:

$\begin{align} \sum_{0 \le k \le n + 1} (\alpha + k)^{\underline{h}} &= \sum_{0 \le k \le n} (\alpha + k)^{\underline{h}} + (\alpha + n + 1)^{\underline{h}} \\ &= \frac{(\alpha + n + 1)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} + (\alpha + n + 1)^{\underline{h}} \\ &= \frac{(\alpha + n + 1)^{\underline{h}} \cdot (\alpha + n + 1 - h)} {h + 1} + \frac{(\alpha + n + 1)^{\underline{h}} \cdot (h + 1)} {h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} \\ &= \frac{(\alpha + n + 1)^{\underline{h}} \cdot (\alpha + n + 2)} {h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} \\ &= \frac{(\alpha + n + 2)^{\underline{h + 1}}}{h + 1} - \frac{\alpha^{\underline{h + 1}}}{h + 1} \end{align}$

This is exactly as claimed.

For your second sum, note that:

$$ (\alpha + k)^{\underline{h}} x^{\alpha + k - h} = \frac{\mathrm{d}^h}{\mathrm{d} x^h} x^{\alpha + k} $$

Thus the sum is essentially:

$\begin{align} \sum\limits_{k=0}^n (\alpha + k)^{\underline{h}} r^k &= r^{h - \alpha} \sum\limits_{k=0}^n (\alpha + k)^{\underline{h}} r^{\alpha + k - h} \\ &= r^{h - \alpha} \left. \frac{\mathrm{d}^h}{\mathrm{d} x^h} \sum\limits_{k=0}^n x^{\alpha + k} \right|_{x = r} \\ &= r^{h - \alpha} \left. \frac{\mathrm{d}^h}{\mathrm{d} x^h} \left(x^\alpha \sum\limits_{k=0}^n x^k\right) \right|_{x = r} \\ &=\left.r^{h-\alpha} \frac{d^h}{d x^h} \left( \frac{x^\alpha - x^{\alpha+n+1}}{1- x} \right)\right|_{x=r} \\ &=r^{h-\alpha} \sum\limits_{l=0}^h \binom{h}{l} \left(\alpha^{\underline{h-l}} r^{\alpha-(h-l)} - (\alpha+n+1)^{\underline{h-l}} r^{\alpha+n+1-(h-l)}\right) \cdot \frac{l!}{(1-r)^{l+1}} \\ &= \frac{1}{(1-r)^{h+1}} \sum\limits_{l=0}^h \binom{h}{l} \left(\alpha^{\underline{h-l}} r^{l} - (\alpha+n+1)^{\underline{h-l}} r^{n+1+l}\right) \cdot l! (1-r)^{h-l} \\ &= \frac{h!}{(1-r)^{h+1}} \sum\limits_{l=0}^h \frac{1}{(h-l)!} \left(\alpha^{\underline{h-l}} r^{l} - (\alpha+n+1)^{\underline{h-l}} r^{n+1+l}\right) \cdot (1-r)^{h-l} \\ &= \frac{h!}{(1-r)^{h+1}} \sum\limits_{l=0}^h \left(\binom{\alpha}{h-l} r^{l} - \binom{\alpha+n+1}{h-l} r^{n+1+l}\right) \cdot (1-r)^{h-l} \\ &= \frac{h!}{(1-r)} \left\{ \binom{\alpha}{h} \cdot F_{2,1} \left[\begin{array}{ll}1 & -h \\ \alpha-h+1 \end{array};\frac{r}{r-1}\right] - r^{n+1} \binom{\alpha+n+1}{h} \cdot F_{2,1} \left[\begin{array}{ll}1 & -h \\ \alpha+n-h+2 \end{array};\frac{r}{r-1}\right] \right\} \end{align}$

This is quite ugly. The remaining sum is geometric, and can be expressed as a fraction. Leibnitz' formula for multiple derivatives of a product reduce that somewhat, but it is still a mess. If $h$ is small integer, perhaps a CAS gives somewhat manageable.

Note: It is a matter of taste whether an expression is ugly or not. In my opinion the final result has a closed form if we use hypergeometric functions.

$\endgroup$

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.