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.
 A: 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$.
A: 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}
