Solving the following ratio of two series

70 Views Asked by At

I'm currently trying to solve the following expression for $0< s \leq 1$:

$$\frac{\sum\limits _{n=1}^{\lfloor l/3\rfloor}s^{l-3n}(1-s)^{3n}{l-1 \choose 3n-1}}{\sum\limits _{n=0}^{\lfloor l/3\rfloor}s^{l-3n}(1-s)^{3n}{l \choose 3n}}$$

I've only made very modest progress, transforming it into the following ratio:

$$\frac{3}{l}\frac{\sum\limits _{n=1}^{\lfloor l/3\rfloor}n\cdot x^{3n}\cdot{l-1 \choose 3n-1}}{1+\sum\limits _{n=1}^{\lfloor l/3\rfloor}x^{3n}\cdot{l \choose 3n}},$$ where $x=\frac{1-s}{s}$.

I'm trying to find an analytic expression for the whole ratio, for all $l\in\mathbb{N}_{>0}$. More modestly, I'm curious to find a way to prove that/how the ratio converges for $l\rightarrow\infty$. Numerical simulation suggest that it converges, for $l\rightarrow \infty$, to $1-s$.

Any help/tips/pointers would be immensely appreciated!

1

There are 1 best solutions below

1
On BEST ANSWER

Let $t = 1-s$. Also, I'm going to use $L$ instead of your $l$ because I find it easier to distinguish visually.

Key observation

Your denominator looks similar to the binomial expansion $$(t+s)^L = \sum_{k=0}^L t^{k} s^{L-k} \binom{L}{k}$$ except that your version only includes terms where the exponent on $t$ is a multiple of $3$. The numerator is also pretty similar but not quite as direct.

There's a trick for evaluating this type of sum, which I'll demonstrate below.

Denominator

Let $\omega = e^{\frac{2i \pi}{3}}$, a complex cube root of unity. We can write $$\begin{align} (s+t)^L + (s+\omega t)^L + (s+\omega^2 t)^L &= \sum_{k=0}^L t^{k} s^{L-k} \binom{L}{k} + \sum_{k=0}^L \omega^k t^{k} s^{L-k} \binom{L}{k} + \sum_{k=0}^L \omega^{2k} t^{k} s^{L-k} \binom{L}{k} \\ &= \sum_{k=0}^L (1 + \omega^k + \omega^{2k}) t^k s^{L-k} \binom{L}{k}. \end{align}$$ Now note that $(1+\omega^k + \omega^{2k})$ is $3$ if $k \equiv 0 \mod 3$ and $0$ otherwise, so we have: $$\begin{align} (s+t)^L + (s+\omega t)^L + (s+\omega^2 t)^L &= 3 \sum_{n=0}^{\lfloor L/3 \rfloor} t^{3n} s^{L-3n} \binom{L}{3n} \\ \frac{(s+t)^L + (s+\omega t)^L + (s+\omega^2 t)^L}{3} = \sum_{n=0}^{\lfloor L/3 \rfloor} t^{3n} s^{L-3n} \binom{L}{3n}. \end{align}$$

This gives a "nice" closed form for your original denominator.

Numerator

Your numerator expression can be redescribed as: the sum of all terms from the binomial expansion of $(s+t)^k$ where $t$ is raised to a multiple-of-3 power and the first $(s+t)$ in the product is required to contribute a factor of $t$. This condition matches up with your binomial coefficient $\binom{L-1}{3n-1}$ because we already have one $t$, so we need to choose $3n-1$ more $t$'s from the remaining $L-1$ possible positions.

Another way to phrase the same sum is: Add up all terms from the binomial expansion of $(s+t)^{L-1}$ where the exponent on $t$ is congruent to $2 \mod 3$. Then multiply that result by $t$. To do the "add up all terms..." part, we can use a modified version of the same trick from above:

$$\begin{align} (s+t)^{L-1} & + \omega (s+\omega t)^{L-1} + \omega^2 (s+\omega^2 t)^{L-1} \\ &= \sum_{k=0}^{L-1} t^{k} s^{L-1-k} \binom{L-1}{k} + \omega \sum_{k=0}^{L-1} \omega^k t^{k} s^{L-1-k} \binom{L-1}{k} + \omega^2 \sum_{k=0}^{L-1} \omega^{2k} t^{k} s^{L-1-k} \binom{L-1}{k} \\ &= \sum_{k=0}^{L-1} (1 + \omega^{k+1} + \omega^{2k+2}) t^k s^{L-1-k} \binom{L-1}{k} \end{align}$$

Similar to the denominator computation, we use the fact that $1 + \omega^{k+1} + \omega^{2k+2}$ equals $3$ if $k+1$ is $0$ mod $3$ and equals $0$ otherwise. Therefore we have $$\begin{align} \frac{(s+t)^{L-1} + \omega (s+\omega t)^{L-1} + \omega^2 (s+\omega^2 t)^{L-1}}{3} &= \sum_{n=1}^{\lfloor L/3 \rfloor} t^{3n-1} s^{L-1-(3n-1)} \binom{L-1}{3n-1}. \end{align}$$

This last expression is very similar to your original numerator, but the power on $t$ is off by 1. We can fix that by multiplying both sides by $t$, getting:

$$\begin{align} t \left(\frac{(s+t)^{L-1} + \omega (s+\omega t)^{L-1} + \omega^2 (s+\omega^2 t)^{L-1}}{3} \right) &= \sum_{n=1}^{\lfloor L/3 \rfloor} t^{3n} s^{L-3n} \binom{L-1}{3n-1}. \end{align}$$

Putting it together to compute the limit

Combining the numerator and denominator into one big fraction gives a messy expression:

$$ \frac{t \left(\frac{(s+t)^{L-1} + \omega (s+\omega t)^{L-1} + \omega^2 (s+\omega^2 t)^{L-1}}{3} \right)}{\frac{(s+t)^L + (s+\omega t)^L + (s+\omega^2 t)^L}{3}} = t \frac{(s+t)^{L-1} + \omega (s+\omega t)^{L-1} + \omega^2 (s+\omega^2 t)^{L-1}}{(s+t)^L + (s+\omega t)^L + (s+\omega^2 t)^L} $$

We're interested in the limit as $L \to \infty$, and that can actually be simplified nicely.

Remember that we defined $t = 1-s$, so we have $s+t = 1$. Also, $s + \omega t = \omega + s(1 - \omega)$, which has magnitude $< 1$ for $0<s<1$ and magnitude $1$ for $s \in \{0, 1\}$. A similar observation shows that $|s + \omega^2 t| \le 1$, again with equality for $s=0$ and $s=1$. The point of these observations is that as $L \to \infty$, the terms with magnitude $<1$ will go to $0$, so they can be ignored when computing the limit.

Now if $0 < s < 1$ we get: $$\begin{align} \lim_{L \to \infty} (\text{your expression}) &= \lim_{L \to \infty} t \frac{(s+t)^{L-1}}{(s+t)^L} = t = 1-s \end{align}$$

If $s = 1$, the limit is $0$ due to the $t$ out in front of the expression. Combining these, we find $$\lim_{L \to \infty} (\text{your expression}) = 1-s$$ for all $0 < s \le 1$, confirming your originally simulation-based guess.