Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

Does anyone have an idea about an exact or approximate formulae for the following summation? $$ \sum_{j=1}^n \frac{j^k}{(j-1)!} $$ where k is a positive integer (the denominator of the j^th term is of course $\Gamma(j)$).

share|improve this question
add comment

5 Answers

up vote 11 down vote accepted

REVISED ANSWER.

In retrospect, deriving the approximation is quite easy. Indeed, $$ \sum\limits_{j = 1}^n {\frac{{j^k }}{{(j - 1)!}}} = e\sum\limits_{j = 1}^n {e^{ - 1} \frac{{j^{k + 1} }}{{j!}}} \approx e\sum\limits_{j = 0}^\infty {e^{ - 1} \frac{{j^{k + 1} }}{{j!}}} = eB_{k + 1}. $$ (For large $k$, you may consider Asymptotic limit and bounds.)

ORIGINAL ANSWER.

Assume that $n$ is sufficiently large. Since $$ \sum\limits_{j = 1}^n {\frac{{j^k }}{{(j - 1)!}}} = \sum\limits_{j = 0}^{n - 1} {\frac{{(j + 1)^k }}{{j!}}} , $$ the problem reduces to approximating $\sum\nolimits_{j = 0}^{n - 1} {\frac{{j^m }}{{j!}}} $, for $0 \leq m \leq k$. Now, $e^{ - 1} \sum\nolimits_{j = 0}^\infty {\frac{{j^m }}{{j!}}} $ is the $m$-th moment of the Poisson distribution with mean $1$. For the latter, see, for example, this.

EDIT: Specifically, the approximation (with the right-hand side being an upper bound) is $$ \sum\limits_{j = 1}^n {\frac{{j^k }}{{(j - 1)!}}} \approx e\sum\limits_{m = 0}^k {{k \choose m}B_m }, $$ where $B_m$ is the $m$-th Bell number (a list is given here). Numerical results indicate that this approximation is very accurate, even for moderate values of $n$. For example, the absolute error for $n=15$, $k=3$ is $\approx 3.4 \times 10^{-9}$; for $n=20$, $k=5$ is $\approx 1.8 \times 10^{-12}$; for $n=20$, $k=7$ is $\approx 7.9 \times 10^{-10}$; for $n=23$, $k=9$ is $\approx 5.8 \times 10^{-11}$.

EDIT: If only the relative error is concerned, then the approximation is quite accurate even for relatively small $n$ values (of course, depending on $k$). For example, for $n=8$, $k=4$: $\approx 141.156$ compared to $\approx 141.351$; for $n=9$, $k=5$: $\approx 551.484$ compared to $\approx 551.811$; for $n=10$, $k=6$: $\approx 2383.359$ compared to $\approx 2383.933$.

EDIT: As Mike Spivey observed, using the identity $$ \sum\limits_{m = 0}^k {{k \choose m}B_m } = B_{k + 1}, $$ the above approximation can be simplified greatly to $$ \sum\limits_{j = 1}^n {\frac{{j^k }}{{(j - 1)!}}} \approx e B_{k+1}. $$

share|improve this answer
1  
Shai, $\sum_{m=0}^k \binom{k}{m} B_m = B_{k+1}$. See the first identity under en.wikipedia.org/wiki/Bell_number#Properties_of_Bell_numbers. So this will simplify your answer greatly. –  Mike Spivey Feb 15 '11 at 6:25
    
@Mike: Great observation, thanks! I'll edit the answer soon. –  Shai Covo Feb 15 '11 at 6:37
1  
I think you can improve on your approximation by subtracting a shifted infinite sum from the unshifted one, then using the binomial theorem and the original approximation. –  Steve Huntsman Feb 15 '11 at 11:28
    
@Steve and all: You are welcome to edit my answer. –  Shai Covo Feb 15 '11 at 15:47
add comment

There might be something in Hall and Knight, Higher Algebra. On page 333, they have the formula, $\sum_1^{n+2}{j^2+j-1\over(j+2)!}={1\over2}-{1\over(n+2)(n!)}$.

share|improve this answer
add comment

The infinite sum is a multiple of $e\ $ and a Bell number. So find the discrepancy (which will be very small), maybe on order of $e^{-2n}$).

share|improve this answer
    
I discovered this by experiment with mathematica (the sum from 0 to $\infty$) -- what's the reference? –  Igor Rivin Feb 15 '11 at 0:47
    
But for the discrepancy to be small, $n$ has to be very large (crudely, on the order of $k.$) –  Igor Rivin Feb 15 '11 at 0:50
1  
A reference is en.wikipedia.org/wiki/Bell_number see Dobinski's formula. –  Gerry Myerson Feb 15 '11 at 0:52
    
@Gerry: thanks! –  Igor Rivin Feb 15 '11 at 2:46
add comment

You can use Wolfram Alpha to get exact solutions for different k, although the results are expressed in not-so-good functions

This allows to build smooth plots:

http://storage4.static.itmages.ru/i/11/0220/h_1298189475_0effdae27f.png http://storage5.static.itmages.ru/i/11/0220/h_1298189539_2043dbc994.png

(both plots are for k=5)

share|improve this answer
add comment

It should be possible to derive the asymptotics of the expression automatically:

1) let the computer guess and prove a recurrence for the expression, which is P-recursive in $n$.

2) use Doron Zeilberger's package asyrec for Maple to obtain the asymptotics (but not the constant term, unfortunately)

3) try to guess the constant term...

I did only part one, for your convenience I post the complete code. (in FriCAS, Bruno Salvy's gfun for Maple and Manuel Kauers' guess for Mathematica should work just as well. In fact, FriCAS is not particularly well suited because it does not yet support multivariate guessing...)

Setup:

)expose RECOP
f := operator 'f; ops := [N^l for l in 0..2]; vars := [f(n+l) for l in 0..2];

Guess the recurrences for each $k$ separately (and transform the results into operator notation for easier postprocessing:

g(n,k) == reduce(+, [j^k/factorial(j-1) for j in 1..n], 0)

r := [eval(getEq first guessPRec([g(n,k) for n in 0..100], maxShift==2), vars, ops)::UP(N, POLY INT)::UP(N, FR POLY INT) for k in 1..15]

The result is (showing only $k=1..4$)

           2 2     2
   [(n + 1) N  - (n  + 3n + 3)N + n + 2,
           3 2     3     2                     2
    (n + 1) N  - (n  + 4n  + 7n + 5)N + (n + 2) ,
           4 2     4     3      2                      3
    (n + 1) N  - (n  + 5n  + 12n  + 16n + 9)N + (n + 2) ,
           5 2     5     4      3      2                       4
    (n + 1) N  - (n  + 6n  + 18n  + 34n  + 37n + 17)N + (n + 2) ,

So the coefficients of $N^2$ (i.e., $f(n+2)$) and $N^0$ (i.e., $f(n)$) are obvious. The coefficient of $N$ turns out to have a rational generating function:

guessPade([coefficient(t, 1) for t in r], indexName=='k)

resulting in

                   2      2
   k (n + 1)(n + 2) x - (n  + 3n + 3)
[[x ]--------------------------------]
                    2
     (n + 1)(n + 2)x  - (2n + 3)x + 1
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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