Summation of an expression - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T10:19:16Z http://mathoverflow.net/feeds/question/55455 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55455/summation-of-an-expression Summation of an expression ogn 2011-02-14T22:06:02Z 2011-02-20T15:34:39Z <p>Hi,</p> <p>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)$).</p> http://mathoverflow.net/questions/55455/summation-of-an-expression/55460#55460 Answer by Gerry Myerson for Summation of an expression Gerry Myerson 2011-02-14T22:23:56Z 2011-02-14T22:23:56Z <p>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!)}$. </p> http://mathoverflow.net/questions/55455/summation-of-an-expression/55464#55464 Answer by Shai Covo for Summation of an expression Shai Covo 2011-02-14T22:43:17Z 2011-02-15T08:22:13Z <p><strong>REVISED ANSWER.</strong></p> <p>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 <a href="http://en.wikipedia.org/wiki/Bell_number#Asymptotic_limit_and_bounds" rel="nofollow">Asymptotic limit and bounds</a>.)</p> <p><strong>ORIGINAL ANSWER.</strong></p> <p>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, <a href="http://math.stackexchange.com/questions/6335/bell-numbers-and-moments-of-the-poisson-distribution" rel="nofollow">this</a>.</p> <p><strong>EDIT</strong>: 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 <a href="http://oeis.org/A000110" rel="nofollow">here</a>). 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}$.</p> <p><strong>EDIT</strong>: 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$.</p> <p><strong>EDIT</strong>: 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}.$$</p> http://mathoverflow.net/questions/55455/summation-of-an-expression/55477#55477 Answer by Aaron Meyerowitz for Summation of an expression Aaron Meyerowitz 2011-02-15T00:24:59Z 2011-02-15T00:24:59Z <p>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}$).</p> http://mathoverflow.net/questions/55455/summation-of-an-expression/56047#56047 Answer by Anixx for Summation of an expression Anixx 2011-02-20T07:40:33Z 2011-02-20T08:13:04Z <p>You can use Wolfram Alpha to get exact solutions for different k, although the results are <a href="http://www.wolframalpha.com/input/?i=sum+x5/Gamma%5Bx%5D+from+x=0+to+z&amp;s=36&amp;incTime=true" rel="nofollow">expressed in not-so-good functions</a></p> <p>This allows to build smooth plots:</p> <p><img src="http://storage4.static.itmages.ru/i/11/0220/h_1298189475_0effdae27f.png" alt="http://storage4.static.itmages.ru/i/11/0220/h_1298189475_0effdae27f.png"> <img src="http://storage5.static.itmages.ru/i/11/0220/h_1298189539_2043dbc994.png" alt="http://storage5.static.itmages.ru/i/11/0220/h_1298189539_2043dbc994.png"></p> <p>(both plots are for k=5)</p> http://mathoverflow.net/questions/55455/summation-of-an-expression/56068#56068 Answer by Martin Rubey for Summation of an expression Martin Rubey 2011-02-20T15:34:39Z 2011-02-20T15:34:39Z <p>It should be possible to derive the asymptotics of the expression automatically:</p> <p>1) let the computer guess and prove a recurrence for the expression, which is P-recursive in $n$.</p> <p>2) use Doron Zeilberger's package <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/asy.html" rel="nofollow">asyrec</a> for Maple to obtain the asymptotics (but not the constant term, unfortunately)</p> <p>3) try to guess the constant term...</p> <p>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...)</p> <p>Setup:</p> <pre> )expose RECOP f := operator 'f; ops := [N^l for l in 0..2]; vars := [f(n+l) for l in 0..2]; </pre> <p>Guess the recurrences for each $k$ separately (and transform the results into operator notation for easier postprocessing:</p> <pre> 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] </pre> <p>The result is (showing only $k=1..4$)</p> <pre> 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) , </pre> <p>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:</p> <pre> guessPade([coefficient(t, 1) for t in r], indexName=='k) </pre> <p>resulting in</p> <pre> 2 2 k (n + 1)(n + 2) x - (n + 3n + 3) [[x ]--------------------------------] 2 (n + 1)(n + 2)x - (2n + 3)x + 1 </pre>