Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it possible to find closed form of following sum: $\sum\limits_{k=1}^{n-1}\frac{x^k}{n-k}$ ?
If not then maybe there is at least some good aproximation?

share|improve this question
4  
Multiply by $x^{-n}$ and substitute $u=1/x$. –  Raskolnikov Dec 20 '10 at 22:16
1  
@Raskolnikov: Probably I dont see something, because after these transformations I will get more or less something like this $\sum\limits_{k=1}^{n-1}\frac{u^k}{k}$. It's easy to calculate the sum when the upper limit is infinity, but what's when the upper limit is equal to n? –  Tomek Tarczynski Dec 20 '10 at 22:41
    
Try integrating the sum of a geometric series (recall that the integral of $x^{k-1}$ is $x^k/k$). –  Yuval Filmus Dec 20 '10 at 23:18
1  
...well, either hypergeometric functions or Lerch transcendents. –  J. M. Dec 21 '10 at 1:06
2  
I don't think you'll get a useful closed form. As far as approximations, what values of x and n are you looking at? –  Qiaochu Yuan Dec 21 '10 at 1:14

2 Answers 2

up vote 4 down vote accepted

Here's a very simple yet quite good approximation to $\sum\nolimits_{k = 1}^{n - 1} {\frac{{x^k }}{{n - k}}}$, suitable for $|x|>1$ and $n$ sufficiently large (which is the interesting case, in my opinion). First write $$ S(n,x) := \sum\limits_{k = 1}^{n - 1} {\frac{{x^k }}{{n - k}}} = x^n \sum\limits_{k = 1}^{n - 1} {\frac{{u^k }}{k}}, $$ where $u=1/x$. If $|x|>1$, then $|u|<1$; hence $\sum\nolimits_{k = 1}^\infty {\frac{{u^k }}{k}} = - \log (1 - u)$. So, noting that $ - \log (1 - \frac{1}{x}) = \log (\frac{x}{{x - 1}})$, this gives rise to the approximation $$ S(n,x) \approx x^n \log \bigg(\frac{x}{{x - 1}}\bigg), $$ provided that $n$ is sufficiently large. It turns out that this simple approximation is quite good. (You can check by yourself.) See the table for an example.


Rounded values of $S(n,x)$ and its approximation, for $n=10$ and several values of $x$.

$$\begin{array}{ccc}x&S(n,x)&x^n \log\left(\frac{x}{x-1}\right)\\-5&-1780484.04&-1780483.95\\-3&-16987.42&-16987.34\\2&709.598&709.783\\ 4&301656.39&301656.52\\6&1.102428722 \times 10^7&1.102428734 \times 10^7\end{array}$$

share|improve this answer
    
This approximation is far better than I expected, it turns out to be very accurate even for quite small n. –  Tomek Tarczynski Dec 21 '10 at 11:27
    
Shai, the table environment wasn't working; hopefully I didn't ruin anything by replacing it with an array. –  J. M. Dec 21 '10 at 12:01
2  
I'll add the note that the closed form for Tomek's original sum is $$x^n\log\left(\frac{x}{x-1}\right)-\sum_{k=0}^\infty\frac{x^{-k}}{n+k}=x^n\log\‌​left(\frac{x}{x-1}\right)-\Phi\left(\frac1{x},1,n\right)=x^n\log\left(\frac{x}{x-‌​1}\right)-\frac1{n}{}_2 F_1\left(n,1;n+1;\frac1{x}\right)$$, where $\Phi(x,s,n)$ is the Lerch transcendent and ${}_2 F_1(a,b;c;z)$ is the Gaussian hypergeometric function. If $n$ is indeed supposed to be "large" as Tomek commented in his question, then it is clear from these expressions why Shai's approximation is very good. –  J. M. Dec 21 '10 at 13:09
    
@J.M.: Indeed, now the table appears correctly. Thanks! –  Shai Covo Dec 21 '10 at 14:38

Tomek:

Here is a suggestion, perhaps it is not giving you as explicit a formula as you'd like. Let $f_n(x)$ the sum that you are interested in. Then $$g_n(x):=x^{-n}f_n(x)=\sum_{k=1}^{n-1}\frac{x^{k-n}}{n-k}=\sum_{k=1}^{n-1}\frac{x^{-k}}{k}.$$ Let $y=1/x$, and $h_n(y):=g_n(1/y)$. Differentiate to get $$\sum_{k=1}^{n-1}y^{k-1}=\frac{1-y^{n-1}}{1-y}.$$ This gives you a formula for $h_n(y)$ after integrating (if you try to find it explicitly rather than leaving it in terms of the integral, this formula is a bit messy because it depends on $n$). From this, you easily get the formula for $f_n(x)$.

share|improve this answer
    
I know how to get to this point, but I dont know how to calculate the integral. –  Tomek Tarczynski Dec 20 '10 at 23:24
    
Yes, that's what I figured. Try replacing $1-y$ with $t$. The integral then turns into a sum of binomial terms, which may be suitable to combinatorial interpretation. –  Andres Caicedo Dec 20 '10 at 23:29
    
@Andreas: If I'm correct then I'll have sum of n binomial terms, so sum of n 'things', which I have at the beginning will be expressed in terms of sum of some other n 'things'. –  Tomek Tarczynski Dec 20 '10 at 23:35
    
As I said, the new sum may be easier to analyze, perhaps on combinatorial grounds. –  Andres Caicedo Dec 21 '10 at 0:40
1  
The problem with the new sum is that it has a lot of cancellation in it. It's a nice identity but as far as asymptotics go it's harder, not easier, to analyze than the original. –  Qiaochu Yuan Dec 21 '10 at 1:11

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.