Sum of terms with recurrence relation

90 Views Asked by At

I have the following sequence, where $s$ is some positive multiple of 4:

\begin{equation} L_n = \begin{cases} \frac{(s-2)!}{2^{s/4-1}(s/2)!(s/4-1)!}, & \text{for $n=1$} \\ \\ L_{n-1}\cdot\frac{2(s/4-n+1)}{s-2n+1}, & \text{for $n=2,3,...\frac{s}{4}$} \end{cases} \end{equation}

I would like to find the value of $\sum_{k=1}^{s/4}L_k$.

So far I have tried factoring, but this can't be done repeatedly in any effective way. I'm mainly stumped by how messy these terms are; simplification just doesn't seem possible. I might be willing to settle for upper and lower bounds, provided that they're better than the trivial ones ($s/4$ times the smallest and biggest terms). Asymptotic results might be ok as well. Or even just a suggestion of a strategy which might work.

This is not a homework problem, so there's no reason to believe that a solution will be simple, unfortunately.

Edit: I'm currently trying to obtain an upper and lower bound by making estimates on the coefficient on $L_{n-1}$. I know that for $n=2$ it's very close to $1/2$, and then decreases to 0 as $n$ gets larger.

1

There are 1 best solutions below

1
On BEST ANSWER

For simplicity put $r=s/4$ and $S(r)=\sum_{k=1}^r L_k$. For $n=2\dots, r$ we have $L_n<\frac 12L_{n-1}$, so $L_n$ decreases to zero very quickly (and $L_1<S(r)<2L_1$). Thus a sum of a few first $L_k$ is a good approximation for $S(r)$. A computational evidence suggests that

$$S(r)=L_1\left(2-\frac 3{2r}+\frac 3{4r^2}-\frac{T(r)}{r^3}\right),$$

with $0\le T(r)=O(1)$.