2
$\begingroup$

I've come across an interesting sum of products series. I know the sum, I can more or less see why it is so, but I'm stuck at a certain point of the proof.

Let $0 <q \leq 1$ be some fraction, $K$ some large positive integer.

$\sum_{i = 0}^{K - 1} {[\frac{1}{i + 1}\prod_{j=i+2}^{K}{(1 - \frac{1}{jq})}]} = q$

When I simulate it e.g. in R it seems legit:

K <- 1000
s <- 0
q <- 0.5
for (i in 0:(K - 1)) {
  p <- 1
  for (j in (i + 2): K) {
    p <- p * (1 - 1 / (q *j))
  }
  s <- s + (1 / (i + 1)) * p
}
s
[1] 0.499996

And I can pretty much see how this happens but am stuck below:

$\sum_{i = 0}^{K - 1} {[\frac{1}{i + 1}\prod_{j=i+2}^{K}{(1 - \frac{1}{jq})}]} =$ $\frac{1}{1} \cdot (1 - \frac{1}{2q})(1 - \frac{1}{3q}) \cdots (1 - \frac{1}{Kq}) + \frac{1}{2} \cdot (1 - \frac{1}{3q}) \cdots (1 - \frac{1}{Kq}) + \cdots + \frac{1}{K} \cdot 1=$

$= \frac{1}{1} \cdot (\frac{2q - 1}{2q})(\frac{3q - 1}{3q}) \cdots (\frac{Kq - 1}{Kq}) + \frac{1}{2} \cdot (\frac{3q - 1}{3q}) \cdots (\frac{Kq - 1}{Kq}) + \cdots + \frac{1}{K} \cdot 1=$

$= \frac{(2q - 1)(3q - 1) \cdots (Kq - 1)}{\frac{K!}{0!}q^{K - 1}} + \frac{(3q - 1)(4q - 1) \cdots (Kq - 1)}{\frac{K!}{1!}q^{K - 2}} + \cdots + \frac{1}{\frac{K!}{(K - 1)!}q^{K - K}}$

(I can see the gist of all the $q^{K - i}$ disappearing but beyond that I'm lost)

$\endgroup$

2 Answers 2

5
$\begingroup$

Your sum is near but not exactly equal to $q$.

To see this, rewrite the summand as follows: $$\frac{1}{i+1}\prod_{j=i+2}^K\left(1 - \frac{1}{jq}\right) = q\left[ \prod_{j=i+2}^K\left(1 - \frac{1}{jq}\right) - \prod_{j=i+1}^K\left(1 - \frac{1}{jq}\right) \right] $$ We are dealing with a telescoping sum and

$$\sum_{i = 0}^{K - 1} \left[\frac{1}{i + 1}\prod_{j=i+2}^{K}\left(1 - \frac{1}{jq}\right)\right] = q\left[ 1 - \prod_{j=1}^K\left(1 - \frac{1}{jq}\right)\right]$$

For large $K$, the product on RHS decays like $e^{-\sum_{j=1}^K \frac{1}{jq}} \sim K^{-\frac1{q}}$. It becomes very small and hard to detect through numerical simulations.

$\endgroup$
1
  • $\begingroup$ I'm so impressed and there's no one tell. Thank you. $\endgroup$ Sep 15, 2021 at 16:40
3
$\begingroup$

If you are familiar with Pochhammer symbols $$\prod_{j=i+2}^{K}\left(1 - \frac{1}{jq}\right)=\frac{\left(i+2-\frac{1}{q}\right)_{K-i-1}}{(i+2)_{K-i-1}}$$ $$\sum_{i = 0}^{K - 1}\frac{\left(i+2-\frac{1}{q}\right)_{K-i-1}}{(i+2)_{K-i-1}}=q+\frac{q^2 \,\Gamma \left(K-\frac{1}{q}+1\right)}{\Gamma (K+1)\, \Gamma \left(-\frac{1}{q}\right)}$$ If you make $q=\frac 12$ the result is then exactly $\frac 12 \forall K but this is the only case.

Close to $q=\frac 12$, a series expansion would give $$\frac{1}{2}+\left(1+\frac{2}{K(K-1) }\right) \left(q-\frac{1}{2}\right)+O\left(\left(q-\frac{1}{2}\right)^2\right)$$

Now, if $K$ is large, using Stirling approximation $$\frac{\Gamma \left(K-\frac{1}{q}+1\right)}{\Gamma (K+1)}=K^{-1/q}\Bigg[1+\frac{1-q}{2 K q^2}+O\left(\frac{1}{K^2}\right) \Bigg]$$

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