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

Question

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)

Answer 1

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.

Answer 2

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