1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you realize that you have factorials of negative integers in the denominator? $\endgroup$ – Brian M. Scott Jan 8 '15 at 11:46
  • $\begingroup$ @BrianM.Scott Which is not a problem. It just makes the notation cleaner. $\endgroup$ – Pp.. Jan 8 '15 at 11:47
  • 1
    $\begingroup$ @BrianM.Scott see edit. Maybe you like the second form better, but I though the first one was more clear $\endgroup$ – user2520938 Jan 8 '15 at 11:48
  • $\begingroup$ @user2520938 thanks for clarification $\endgroup$ – Irrational Person Jan 8 '15 at 11:52
  • 2
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jan 8 '15 at 11:53
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the answer! Im not familiar with any of the things you said, but i will try figuring it out. $\endgroup$ – user2520938 Jan 8 '15 at 17:26
  • $\begingroup$ 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) $\endgroup$ – user2520938 Jan 9 '15 at 11:10
  • $\begingroup$ 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. $\endgroup$ – Lucian Jan 9 '15 at 11:59
  • $\begingroup$ 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}. $\endgroup$ – user2520938 Jan 9 '15 at 12:07
  • $\begingroup$ 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. $\endgroup$ – user2520938 Jan 9 '15 at 12:08
0
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.