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$
10
  • $\begingroup$ Do you realize that you have factorials of negative integers in the denominator? $\endgroup$ Jan 8, 2015 at 11:46
  • $\begingroup$ @BrianM.Scott Which is not a problem. It just makes the notation cleaner. $\endgroup$
    – Pp..
    Jan 8, 2015 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$ Jan 8, 2015 at 11:48
  • $\begingroup$ @user2520938 thanks for clarification $\endgroup$ Jan 8, 2015 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$ Jan 8, 2015 at 11:53

2 Answers 2

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$
10
  • $\begingroup$ Thanks for the answer! Im not familiar with any of the things you said, but i will try figuring it out. $\endgroup$ Jan 8, 2015 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$ Jan 9, 2015 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, 2015 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$ Jan 9, 2015 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$ Jan 9, 2015 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.