# Need help finding a closed form for complicated sum

I'm trying to find a closed form expression for the following sequence:

$$a_n=\sum_{i=1}^{n}\frac{(n-1-i+d)!}{(n-2i)!(i)!}=\sum_{i=1}^{\frac{n}{2}}\frac{(n-1-i+d)!}{(n-2i)!(i)!}$$

Where $n$ and $d$ are both positive integers.

An important note!: I'm actually not even interested in an exact solution. Any closed form that is a 'reasonably' close approximation is fine!

Now I have no reason to assume a close form even exists, and the expression looks quite ugly, so I would even go as far as to say that I highly doubt a closed form exists, but maybe someone can take a look and tell why it does/does not exist.

Thanks!

Edit: an other way to write the sequence is as:

$$a_n=(d-1)!\sum_{i=1}^{n}\binom{n-1-i+d}{n-2i}\binom{i+d-1}{i}$$

Maybe someone will recognize this or know how to deal with this.

• Do you realize that you have factorials of negative integers in the denominator? Jan 8 '15 at 11:46
• @BrianM.Scott Which is not a problem. It just makes the notation cleaner.
– Pp..
Jan 8 '15 at 11:47
• @BrianM.Scott see edit. Maybe you like the second form better, but I though the first one was more clear Jan 8 '15 at 11:48
• @user2520938 thanks for clarification Jan 8 '15 at 11:52
• @Pp..: In the absence of an explicitly stated convention I consider it a problem. It could also have been a genuine oversight, which is why I asked. Jan 8 '15 at 11:53

Are you familiar with Gegenbauer polynomials ? Either way, we can use their definition

in rewriting the sum as $$a_n=\pi\cdot\big(-{\bf i}\big)^n\cdot{\large\bf C}_n^{(d)}\bigg(\dfrac{\bf i}2\bigg)\cdot\displaystyle\lim_{\delta\to d}\dfrac{\csc\big(\delta\pi\big)}{\big(-\delta\big)!}$$ , where the limit can

be evaluated using Euler's reflection formula for the $$\Gamma$$ function as $$\dfrac{\Gamma\big(d\big)}\pi=\dfrac{\big(d-1\big)!}\pi$$.

• Thanks for the answer! Im not familiar with any of the things you said, but i will try figuring it out. Jan 8 '15 at 17:26
• Could it be that it should be $i^n$ instead of $(-i)^n$? And this is an approximation right? (which is perfectly fine by the way) Jan 9 '15 at 11:10
• No, it is an exact closed form. The $(-1)^n$ comes from $\csc\Big((n+\delta)\pi\Big)$. The $i^n$ is meant to transform the Gegenbauer polynomial of imaginary argument into a real value. Jan 9 '15 at 11:59
• But evaluation of the value at $d=2$ gives the following list of values with $n=1,...,10$ and $(-i)^n$: {-2, 5, -10, 20, -38, 71, -130, 235, -420, 744}, while $i^n$ gives {2, 5, 10, 20, 38, 71, 130, 235, 420, 744}. Jan 9 '15 at 12:07
• Also, the same values according to the original definition are: {0, 2, 6, 15, 32, 64, 122, 226, 410, 733}, which is close but not exact. Jan 9 '15 at 12:08

Without loss of generality we can simplify the problem a wee bit and change the lower limit in the sum to zero. Thus we have: \begin{equation} F_n:= \sum\limits_{k=0}^n \frac{(n-1+k+d)!}{k!(n-2 k)!} \end{equation}

Now, by using either Sister Celine's or the Zeilberger algorithms we quickly establish the recursion relation satisfied by the quantity in question: It reads: \begin{equation} F_n = \frac{1}{n} \left[ (n+d-1) F_{n-1} + (n+2 d-2) F_{n-2}\right] \end{equation} for $n\ge 2$.

Now, we define the generating function $F(x) := \sum\limits_{n=0}^\infty F_n x^n$. This function satisfies the following differential equation:

\begin{equation} (1-x-x^2)F^{'}(x) = d(1+2 x) F(x) + (F_1-d F_0) \end{equation} where $F(0)=F_0$ and $F^{'}(0)=F_1$. The solution to the differential equation reads: \begin{equation} F(x) = (F_1-d \cdot F_0) \cdot \frac{\sum\limits_{0\le l_1 \le l \le d-1} \binom{d-1}{l} \binom{l}{l_1} (-1)^l \frac{x^{l+l_1+1}}{(l+l_1+1)}}{(1-x-x^2)^d} + \frac{F_0}{(1-x-x^2)^d} \end{equation}

The solution above has a following partial fraction decomposition: \begin{equation} F(x) = \sum\limits_{j=1}^d \left[ \frac{A_+^{(d)}(j)}{(2 x+1+\sqrt{5})^j} + \frac{A_-^{(d)}(j)}{(2 x+1-\sqrt{5})^j}\right] \end{equation} where the numbers $\left( A_\pm^{(d)}(j)\right)_{j=1}^d$ are linear combinations of $F_0$ and $F_0$ only with coefficients belonging to ${\mathbb Q}(\sqrt{5})$. Finally, the closed form solution to the sum in question reads: \begin{equation} F_n = \sum\limits_{j=1}^d \frac{(-2)^n j^{(n)}}{n!} \cdot \left( \frac{A_+^{(d)}(j)}{(1+\sqrt{5})^{j+n}} + \frac{A_-^{(d)}(j)}{(1-\sqrt{5})^{j+n}}\right) \end{equation}