Creative telescoping of a non-hypergeometric function $\sum_{k=0}^n\binom{n}{k}p^k(1-p)^{n-k}A_{n,k}/\left[(1+A_{n,k})(b+cA_{n,k})(q+pA_{n,k})\right]$

Question

I have been struggling with finding an analytic form for the following expression: $$ a_n=\sum\limits_{k=0}^n\binom{n}{k}p^k(1-p)^{n-k}A_{n,k}\left[(1+A_{n,k})(1-q+(1-p)A_{n,k})(q+pA_{n,k})\right]^{-1} $$ where $A_{n,k}=(\frac{p}{q})^k(\frac{1-p}{1-q})^{n-k}$ and $0<q<p<1$.

EDIT 2: I am editing the question to being interested in $\sum\limits_{n=0}^m a_n$ so that I may accept @mathlove 's second answer, which is the one which (imo) makes the most progress in the desired direction (end of EDIT 2)

In fact, I am also interested in $\sum\limits_{m=1}^M\frac12-(p-q)^2\sum\limits_{n=0}^m a_n$ (because the limit $\lim\limits_{m\to\infty}(p-q)^2\sum\limits_{n=0}^m a_n=\frac12$, which I "know" numerically), with $M$ being some number or potentially going to $\infty$ (because, from what I can tell numerically, this series converges, see this Wolfram notebook). I say this in case solving for one of these sums is actually simpler, but I believe that I will be able to figure this out if I can make some headway on $a_n$ itself.

So far, I have stumbled on this website onto a few references to the book A=B, and the term of "creative telescoping". Unfortunately, after scanning the book, I am led to believe that the algorithms for such telescoping do not work in this case since the function is not (unless I am mistaken) hypergeometric. However, I am hopeful that some other type of creative telescoping would work here, just there is, as far as I can tell, no universal way of achieving this here and so far I have not found any way to do so.

The main issue seems to reside in the portion that is on the denominator (the term in brackets to the $-1$ power), which has $1+x$ terms inside which are causing me a headache because it prevents the usual technique of simplifying the powers when searching for a recurrence by expressing it as a ratio of two successive terms. If we call that term in brackets $F_{n,k}$, I think it could be interesting to find a recurrence over it, but so far I have failed to find one. I have tried expressing it as a function of $F_{n-1,k-1}$ and $F_{n,k-1}$ but no success this way so far. I also tried writing the ratio $F_{n,k}/F_{n-1,k-1}$, by using logs, but so far this is a dead end.

Any suggestions on paths forward would be appreciated!

PS: although I am dealing in discrete sums, if any continuous results do exists I am also interested as I can perhaps make some connections that way.

== Edit 1 ==

@mathlove, in their derivations here and in a related post, introduce $D_{n,k}=\left(\dfrac{1}{p}\right)^k\left(\dfrac{1}{1-p}\right)^{n-k}+\left(\dfrac{1}{q}\right)^k\left(\dfrac{1}{1-q}\right)^{n-k}$. By working on solving $a_n$, I get to (I hope this is correct but it seems to check out): $$ a_n=\sum\limits_{k=0}^n\binom{n}{k}\frac{1}{D_{n,k}}-\sum\limits_{k=0}^{n+1}\binom{n+1}{k}\frac{1}{D_{n+1,k}} $$ It is tempting to think that this would telescope, but the fact that $D_{n,k}$ is on the denominator has me struggling...

Answer 1

You have a nice idea in Edit 1.

This answer proves the following claims :

Claim 1 : $\ \ a_n=\dfrac{1}{(q-p)^2}(G_n-G_{n+1})$ where $G_n=\displaystyle\sum_{k=0}^{n}\binom nk\dfrac{1}{D_{n,k}}$

Claim 2 : $\ \ \displaystyle\sum_{n=0}^{m}a_n=\frac{1}{(q-p)^2}\bigg(\frac 12-G_{m+1}\bigg)$

Claim 3 : $\ \ \displaystyle\lim_{m\to\infty}(p-q)^2\sum_{n=0}^{m}a_n=\dfrac 12$

Claim 4 : $\ \ \displaystyle\frac{(q+1-p)^2}{2(p-q)}\lt\lim_{M\to\infty}\sum_{m=1}^{M}\bigg(\frac 12-(p-q)^2\sum_{n=0}^{m}a_n\bigg)\leqslant \frac{(\sqrt{pq}+\sqrt{(1-p)(1-q)})^2}{2(1-\sqrt{pq}-\sqrt{(1-p)(1-q)})}$

---

Claim 1 : $\ \ a_n=\dfrac{1}{(q-p)^2}(G_n-G_{n+1})$ where $G_n=\displaystyle\sum_{k=0}^{n}\binom nk\dfrac{1}{D_{n,k}}$

Proof :

We have $$\begin{align}a_n&=\frac{1-p}{(q-p)^2}e_n-\frac{b_n}{(q-p)^2} \\\\&=\frac{1-p}{(q-p)^2}\bigg(\frac{1}{1-p}-\frac{1}{1-p}\sum_{k=0}^{n+1}\binom{n+1}{k}\frac{1}{D_{n+1,k}}\bigg) \\&\qquad\quad -\frac{1}{(q-p)^2}\bigg(1-\sum_{k=0}^{n}\binom nk\frac{1}{D_{n,k}}\bigg) \\\\&=\frac{1}{(q-p)^2}(G_n-G_{n+1})\end{align}$$

where $b_n=\displaystyle\sum_{k=0}^{n}\binom nkp^k(1-p)^{n-k}\frac{A_{n,k}}{A_{n,k}+1}$.

---

Claim 2 : $\ \ \displaystyle\sum_{n=0}^{m}a_n=\frac{1}{(q-p)^2}\bigg(\frac 12-G_{m+1}\bigg)$

Proof :

$$\begin{align}\sum_{n=0}^{m}a_n&=\frac{1}{(q-p)^2}\sum_{n=0}^{m}(G_n-G_{n+1}) \\\\&=\frac{1}{(q-p)^2}(G_0-G_{m+1}) \\\\&=\frac{1}{(q-p)^2}\bigg(\frac 12-G_{m+1}\bigg)\end{align}$$

---

Claim 3 : $\ \ \displaystyle\lim_{m\to\infty}(p-q)^2\sum_{n=0}^{m}a_n=\dfrac 12$

Proof :

This answer shows that $\displaystyle\lim_{m\to\infty}G_{m+1}=\lim_{m\to\infty}(1-b_{m+1})=0$.

Therefore, we have $$\lim_{m\to\infty}(p-q)^2\sum_{n=0}^{m}a_n=\lim_{m\to\infty}\bigg(\frac 12-G_{m+1}\bigg)=\frac 12$$

---

Claim 4 : $\ \ \displaystyle\frac{(q+1-p)^2}{2(p-q)}\lt\lim_{M\to\infty}\sum_{m=1}^{M}\bigg(\frac 12-(p-q)^2\sum_{n=0}^{m}a_n\bigg)\leqslant \frac{(\sqrt{pq}+\sqrt{(1-p)(1-q)})^2}{2(1-\sqrt{pq}-\sqrt{(1-p)(1-q)})}$

Proof :

We have $$\begin{align}\sum_{m=1}^{M}\bigg(\frac 12-(q-p)^2\sum_{n=0}^{m}a_n\bigg)&=\sum_{m=1}^{M}G_{m+1}\end{align}$$ Then, we have $$\sum_{m=1}^{M}G_{m+1}\gt\sum_{m=1}^{M}\frac 12C^{m+1}=\frac{C^2-C^{M+2}}{2(1-C)}$$ and $$\sum_{m=1}^{M}G_{m+1}\leqslant\sum_{m=1}^{M}\frac 12B^{m+1}=\frac{B^2-B^{M+2}}{2(1-B)}$$ where $B=\sqrt{pq}+\sqrt{(1-p)(1-q)}$ and $C=q+1-p$.

The claims follows from these.

Answer 2

Here's a possible start (with help from Wolfram Alpha):

$\dfrac1{(1+ax)(1+bx)(1+cx)} =\dfrac{a^2}{(a - b) (a - c) (a x + 1)} - \dfrac{b^2}{(a - b) (b - c) (b x + 1)} - \dfrac{c^2}{(a - c) (c - b) (c x + 1)} $

so

$\begin{array}\\ \dfrac1{(1+x)(1-q+(1-p)x)(q+px)} &=\dfrac{p^2}{(q - p)^2 (p x + q)} - \dfrac{(p - 1)^2}{(q - p)^2 ((p - 1) x + q - 1)} - \dfrac1{(x + 1) (q - p)^2}\\ &=\dfrac1{(q-p)^2}\left(\dfrac{p^2}{p x + q} - \dfrac{(p - 1)^2}{(p - 1) x + q - 1} - \dfrac1{x + 1}\right)\\ \end{array} $

You might be able to get some telescoping from this.

Answer 3

This answer proves that $\displaystyle\lim_{n\to\infty}a_n=0$ and that $\displaystyle\lim_{N\to\infty}\sum_{n=1}^{N}(1-a_n)=\infty$.

Proof :

Using the result of marty cohen's answer, we have $$ a_n=\sum_{k=0}^{n}\dfrac{\binom{n}{k}p^k(1-p)^{n-k}A_{n,k}}{(1+A_{n,k})(1-q+(1-p)A_{n,k})(q+pA_{n,k})} $$ $$=\sum_{k=0}^{n}\dfrac{\binom{n}{k}p^k(1-p)^{n-k}A_{n,k}}{(q-p)^2}\left(\dfrac{p^2}{p A_{n,k} + q} - \dfrac{(p - 1)^2}{(p - 1) A_{n,k} + q - 1} - \dfrac1{A_{n,k} + 1}\right) $$

$$=\sum_{k=0}^{n}\underbrace{\dfrac{\binom{n}{k}p^k(1-p)^{n-k}A_{n,k}}{(q-p)^2}\left(\dfrac{p^2}{p A_{n,k} + q} - \dfrac{(p - 1)^2}{(p - 1) A_{n,k} + q - 1}\right)}_{c_n} - \frac{b_n}{(p-q)^2} $$ where $b_n=\displaystyle\sum_{k=0}^{n}\binom nkp^k(1-p)^{n-k}\frac{A_{n,k}}{A_{n,k}+1}$. This answer proves that $\displaystyle\lim_{n\to\infty}b_n=1$.

Here, noting that

$$\frac{q(1-p)}{p(1-q)}A_{n,k+1}=A_{n,k}$$ $$\frac{q}{1-q}\bigg(1-q+(1-p)A_{n,k+1}\bigg)=q+pA_{n,k}$$

we have

$$\begin{align}c_n&=\dfrac{\binom{n}{k}p^k(1-p)^{n-k}A_{n,k}}{(q-p)^2}\left(\dfrac{\frac{p^2(1-q)}{q}}{1-q+(1-p)A_{n,k+1}} + \dfrac{(p - 1)^2}{1-q+(1-p) A_{n,k}}\right) \\\\&=\dfrac{\frac{p^2(1-q)}{q}\cdot\dfrac{\binom{n}{k}p^k(1-p)^{n-k}\frac{q(1-p)}{p(1-q)}A_{n,k+1}}{(q-p)^2}}{1-q+(1-p)A_{n,k+1}} + \dfrac{(p - 1)^2\dfrac{\binom{n}{k}p^k(1-p)^{n-k}A_{n,k}}{(q-p)^2}}{1-q+(1-p) A_{n,k}} \\\\&=\dfrac{\dfrac{\binom{n}{k}p^{k+1}(1-p)^{n+1-k}A_{n,k+1}}{(q-p)^2}}{1-q+(1-p)A_{n,k+1}} + \dfrac{\dfrac{\binom{n}{k}p^k(1-p)^{n+2-k}A_{n,k}}{(q-p)^2}}{1-q+(1-p) A_{n,k}} \\\\&=\binom nk(d_{n,k+1}+d_{n,k})\end{align}$$

where $$d_{n,k}=\dfrac{\dfrac{p^k(1-p)^{n+2-k}A_{n,k}}{(q-p)^2}}{1-q+(1-p) A_{n,k}}$$

Using $\binom{N}{r}=\binom{N-1}{r-1}+\binom{N-1}{r}$, we have $$\begin{align}\sum_{k=0}^{n}c_n&=\sum_{k=0}^{n}\binom nk\bigg(d_{n,k+1}+ d_{n,k}\bigg) \\\\&=\binom n0d_{n,0}+\bigg(\sum_{k=1}^{n}\bigg(\binom{n}{k-1}+\binom nk\bigg)d_{n,k}\bigg)+\binom nnd_{n,n+1} \\\\&=\sum_{k=0}^{n+1}\binom{n+1}{k}d_{n,k} \\\\&=\frac{1}{(q-p)^2}\sum_{k=0}^{n+1}\binom{n+1}{k}\dfrac{p^k(1-p)^{n+2-k}A_{n,k}}{1-q+(1-p) A_{n,k}} \\\\&=\frac{1-p}{(q-p)^2}\underbrace{\sum_{k=0}^{n+1}\binom{n+1}{k}\dfrac{p^k(1-p)^{n+1-k}(\frac{p}{q})^k(\frac{1-p}{1-q})^{n-k}}{1-q+(1-p) (\frac{p}{q})^k(\frac{1-p}{1-q})^{n-k}}}_{e_n}\end{align}$$

Now, let us consider $\dfrac{1}{1-p}-e_n$.

$$\begin{align}\frac{1}{1-p}-e_n&=\sum_{k=0}^{n+1}\binom{n+1}{k}p^k(1-p)^{n+1-k}\frac{1}{1-p} \\&\qquad -\sum_{k=0}^{n+1}\binom{n+1}{k}\dfrac{p^k(1-p)^{n+1-k}(\frac{p}{q})^k(\frac{1-p}{1-q})^{n-k}}{1-q+(1-p) (\frac{p}{q})^k(\frac{1-p}{1-q})^{n-k}} \\\\&=\sum_{k=0}^{n+1}\binom{n+1}{k}\dfrac{p^k(1-p)^{n+1-k}\frac{1-q}{1-p}}{1-q+(1-p) (\frac{p}{q})^k(\frac{1-p}{1-q})^{n-k}} \\\\&=\frac{1}{1-p}\sum_{k=0}^{n+1}\binom{n+1}{k}\dfrac{1}{D}\end{align}$$

where

$$D=\bigg(\frac{1}{p}\bigg)^k\bigg(\frac{1}{1-p}\bigg)^{n+1-k}+\bigg(\frac{1}{q}\bigg)^k\bigg(\frac{1}{1-q}\bigg)^{n+1-k}$$

Since $\dfrac 1p\lt \dfrac 1q$ and $\dfrac{1}{1-q}\lt\dfrac{1}{1-p}$, we get $D\lt 2\left(\dfrac{1}{q}\right)^k\left(\dfrac{1}{1-p}\right)^{n+1-k}$ from which we have $$\frac{1}{1-p}-e_n\gt \frac{1}{2(1-p)}(q+1-p)^{n+1}\tag1$$

Next, using $\dfrac{2}{\dfrac{1}{a}+\dfrac 1b}\leqslant \sqrt{ab}$, i.e. $\dfrac{1}{a+b}\leqslant\dfrac 12(ab)^{-\frac 12}$, we get $$\frac 1D\leqslant \frac 12\bigg(\bigg(\frac{1}{pq}\bigg)^k\bigg(\frac{1}{(1-p)(1-q)}\bigg)^{n+1-k}\bigg)^{-\frac 12}$$ i.e. $$\frac 1D\leqslant \frac 12\bigg(\sqrt{pq}\bigg)^k\bigg(\sqrt{(1-p)(1-q)}\bigg)^{n+1-k}$$ from which we have $$\frac{1}{1-p}-e_n\leqslant \frac{1}{2(1-p)}\bigg(\sqrt{pq}+\sqrt{(1-p)(1-q)}\bigg)^{n+1}\tag2$$

Since $0\lt q+1-p\lt 1$ and $0\lt \sqrt{pq}+\sqrt{(1-p)(1-q)}\lt 1$, we get, from $(1)(2)$, $\displaystyle\lim_{n\to\infty}e_n=\frac{1}{1-p}$.

Therefore, we finally get $$\lim_{n\to\infty}a_n=\lim_{n\to\infty}\bigg(\frac{1-p}{(p-q)^2}e_n-\frac{b_n}{(p-q)^2}\bigg)=0$$

---

In the following, let us prove that $\displaystyle\lim_{N\to\infty}\sum_{n=1}^{N}(1-a_n)=\infty$.

We have $$1-\frac 12B^n\leqslant b_n\lt 1-\frac 12C^n$$ and $$\frac{1}{1-p}-\frac{1}{2(1-p)}B^{n+1}\leqslant e_n\lt \frac{1}{1-p}-\frac{1}{2(1-p)}C^{n+1}$$ where $B=\sqrt{pq}+\sqrt{(1-p)(1-q)}$ and $C=q+1-p$.

So, $$\sum_{n=1}^{N}(1-a_n)\gt \sum_{n=1}^{N}\bigg(1-\frac{1-p}{(p-q)^2}\bigg(\frac{1}{1-p}-\frac{1}{2(1-p)}C^{n+1}\bigg)+\frac{1}{(p-q)^2}\bigg(1-\frac 12B^n\bigg)\bigg)$$

$$=\sum_{n=1}^{N}\bigg(1+\frac{C^{n+1}}{2(p-q)^2}-\frac{B^n}{2(p-q)^2}\bigg)$$

Since $$\lim_{N\to\infty}\sum_{n=1}^{N}\bigg(1+\frac{C^{n+1}}{2(p-q)^2}-\frac{B^n}{2(p-q)^2}\bigg)=\infty$$ we finally get $$\lim_{N\to\infty}\sum_{n=1}^{N}(1-a_n)=\infty$$

---

Added 1 :

There must be a problem somewhere (when I say "somewhere", that includes on my end) because, as I stated and as far as I can tell with the choices of $p$ and $q$ I have tried so far, the series $\displaystyle\lim_{N\to\infty}\sum_{n=1}^{N}(1−a_n)$ converges numerically for $0<q<p<1$.

Let us take $q=\frac 15$ and $p=\frac 45$.

WolframAlpha gives the followings :

• $a_1\approx 0.23529411764$

• $a_2\approx 0.18316742081$

• $a_3\approx 0.11438350617$

• $a_4\approx 0.09170369833$

• $a_5\approx 0.06139304418$

• $a_6\approx 0.04992997170$

• $a_7\approx 0.03451152357$

• $a_8\approx 0.02830677081$

• $a_9\approx 0.01992934589$

• $a_{10}\approx 0.0164383$ (see here)

• $a_{100}\approx 1.04532460 × 10^{-11}$ (see here)

• $a_{1000}\approx 2.00942830 × 10^{-99}$ (see here)

So, it seems that $\displaystyle\lim_{n\to\infty}a_n=0$ is correct.

Also, we have the followings :

• $\displaystyle\sum_{n=1}^{1}(1−a_n)\approx 0.76470588236$

• $\displaystyle\sum_{n=1}^{2}(1−a_n)\approx 1.58153846155$

• $\displaystyle\sum_{n=1}^{3}(1−a_n)\approx 2.46715495538$

• $\displaystyle\sum_{n=1}^{4}(1−a_n)\approx 3.37545125705$

• $\displaystyle\sum_{n=1}^{5}(1−a_n)\approx 4.31405821287$

• $\displaystyle\sum_{n=1}^{6}(1−a_n)\approx 5.26412824117$

• $\displaystyle\sum_{n=1}^{7}(1−a_n)\approx 6.2296167176$

• $\displaystyle\sum_{n=1}^{8}(1−a_n)\approx 7.20130994679$

• $\displaystyle\sum_{n=1}^{9}(1−a_n)\approx 8.1813806009$

• $\displaystyle\sum_{n=1}^{10}(1−a_n)\approx 9.1649423009$

Considering $a_{100}\approx 1.04532460 × 10^{-11}$ and $a_{1000}\approx 2.00942830 × 10^{-99}$, it seems that $\displaystyle\lim_{N\to\infty}\sum_{n=1}^{N}(1−a_n)=\infty$ is correct.

---

Added 2 :

Let $T(M):=\displaystyle\sum_{m=1}^M\bigg(\frac 12-\sum_{n=0}^{m}a_n\bigg)$. Then, for $q=\frac 15$ and $p=\frac 45$, I got the followings :

• $T(1)=\frac 12-a_0-a_1$$\approx -0.23529411764$

• $T(2)=1-2a_0-2a_1-a_2$$\approx -0.65375565609$

• $T(3)=\frac 32-3a_0-3a_1-2a_2-a_3$$\approx -1.18660070071$.

So, it seems that $T(M)$ is decreasing, which is very different from the plot in your comment below.