# Sum of series $\frac{x^k}{n-k}$

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?

-
Multiply by $x^{-n}$ and substitute $u=1/x$. – Raskolnikov Dec 20 '10 at 22:16
@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
...well, either hypergeometric functions or Lerch transcendents. – J. M. Dec 21 '10 at 1:06
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

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}$$

-
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
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)$.

-
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. – Andrés E. 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. – Andrés E. Caicedo Dec 21 '10 at 0:40
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