Here is my core question: I know there is some rational polynomial function, $p(s)$ that satisfies the following relationship:
$$\frac{(2s+4)(2s+3)(2s+5)}{8 (s+1)(s+3)^2}p(s+1) – p(s) = \frac{3}{s+3} \tag{1}$$
I happen to know that the answer in this instance is:
$$p(s) = \bbox[grey]{4\frac{(s+2)(5s+8)}{(s+1)}}$$
I know how to verify this answer, but not how to find it from "scratch". Is there a systematic way to do this?
Now, why do I care about equation (1)? Because it helps in solving the summation arising in the answer to the following question:
"Imagine two wealthy gamblers start tossing their own separate fair coins, winning 1\$ on heads and losing 1\$ on tails. Both start at 0\$ and have infinite bank balances. The first one wants to get to 2\$ and the second one wants to get to 3\$. What is the probability that the first one will reach his goal before the second one?"
You can get more details about this problem by going through the following question (and the two of my answers): Race of the wealthy gamblers: How do I get this closed form?
To get the probability that a gambler targeting 1\$ will draw with another gambler targeting 1\$, you need the following identity:
$$\bbox[yellow]{\left(\frac{{2s \choose s}}{2^{2s}}\right)^2}\frac{1}{(s+1)^2} = 4(4s+5)\bbox[orange]{\left(\frac{{2s+2 \choose s+1}}{2^{2s+2}}\right)^2} – 4(4s+1) \bbox[yellow]{\left(\frac{{2s \choose s}}{2^{2s}}\right)^2} \tag{2}$$
If you knew this identity, finding the closed form expression for the summation (which is the probability two 1\$ targeting gamblers will draw):
$$\sum\limits_{t=0}^s \bbox[yellow]{\left(\frac{{2t \choose t}}{2^{2t}}\right)^2}\frac{1}{(t+1)^2}$$ would be trivial as per this approach courtesy @robojohn.
Note how the two yellow bits are the same and the orange bit arises by replacing $s$ with $s+1$ in the yellow bit. Also $p(s)$ for this expression would be $p(s) = 4(4s+1)$ which accompanies the yellow bit on the RHS and then $p(s+1)$ accompanies the orange bit. If you factor out the common terms, you'll end up with an equation like (1).
This seems to be a general pattern for these kinds of summations. Here are more examples for the skeptics:
For solving the summation for 1\$ targeting gambler beating a 2\$ targeting one:
$$\bbox[yellow]{\left(\frac{{2s \choose s}}{2^{2s}}\right)^2}\frac{1}{(s+1)} = 4(s+1)\bbox[orange]{\left(\frac{{2s+2 \choose s+1}}{2^{2s+2}}\right)^2} – 4s \bbox[yellow]{\left(\frac{{2s \choose s}}{2^{2s}}\right)^2} \tag{3}$$
And here are some more (all relating to gambler races see here for details):
$$\bbox[yellow]{\left(\frac{{2s+1 \choose s}}{2^{2s+1}}\right)^2}\frac{1}{(s+2)} = 4(s+2)\bbox[orange]{\left(\frac{{2s+3 \choose s+1}}{2^{2s+3}}\right)^2} – 4(s+1) \bbox[yellow]{\left(\frac{{2s+1 \choose s}}{2^{2s+1}}\right)^2} \tag{3}$$
$$\bbox[yellow]{\left(\frac{{2s+2 \choose s}}{2^{2s+2}} \frac{{2s+3 \choose s+1}}{2^{2s+3}} \right)}\frac{3}{(s+3)} = \frac{4(s+3)(5s+13)}{(s+2)}\bbox[orange]{\left(\frac{{2s+4 \choose s+1}}{2^{2s+4}} \frac{{2s+5 \choose s+2}}{2^{2s+5}} \right)} – \bbox[grey]{\frac{4(s+2)(5s+8)}{(s+1)}} \bbox[yellow]{\left(\frac{{2s+2 \choose s}}{2^{2s+2}} \frac{{2s+3 \choose s+1}}{2^{2s+3}} \right)} \tag{4}$$
$$\bbox[yellow]{\left(\frac{{2s \choose s}}{2^{2s}} \frac{{2s+2 \choose s}}{2^{2s+2}} \right)}\frac{3s+4}{2(s+1)^2} = \frac{-4(s+3)(s+4)}{6(s+2)}\bbox[orange]{\left(\frac{{2s+2 \choose s+1}}{2^{2s+2}} \frac{{2s+4 \choose s+1}}{2^{2s+4}} \right)} – \frac{-4(s+2)(s+3)}{6(s+1)} \bbox[yellow]{\left(\frac{{2s \choose s}}{2^{2s}} \frac{{2s+2 \choose s}}{2^{2s+2}} \right)} \tag{5}$$
I hope you're convinced of the pattern by now. Assuming I didn't know the grey bit in equation (4) and assumed it was $p(s)$. Then cancelling out terms in equation (4) would lead to equation (1). The $p(s)$ mentioned there is probably the only rational solution of equation (1). Question is, how do we find it?
Best Answer
HINT:
We are given a first degree Finite Difference equation, linear and non-homogeneous $$ {{a(s)} \over {b(s)}}p(s + 1) + {{c(s)} \over {d(s)}}p(s ) = {{f(s)} \over {g(s)}} $$ where all the parameters $a(s), \cdots , f(s)$ are polynomials in $s$.
The above equation shall be valid for all real values of $s$, in particular for those for which $a(s) \ne 0$: let's assume $s$ belongs to such a domain.
We normalize to $1$ the coefficient of $p(s+1)$ $$ p(s + 1) + {{b(s)c(s)} \over {a(s)d(s)}}p(s ) = {{b(s)f(s)} \over {a(s)g(s)}} $$
Thereafter, assume also that $s$ (and $s+1$) belongs to a domain in which $b(s)c(s) \ne 0$.
So we can divide by the summing factor (analog to the integration factor) $$ h(s) = \left( { - 1} \right)^{\,s} \prod\limits_{k\, = \,u}^{s - 1} {{{b(k)c(k)} \over {a(k)d(k)}}} $$
where $k$ ranges in the said domain, to obtain an exact difference $$ \eqalign{ & {{p(s + 1)} \over {h(s + 1)}} + {{b(s)c(s)} \over {a(s)d(s)}}{{p(s)} \over {h(s + 1)}} = {{b(s)f(s)} \over {a(s)g(s)h(s + 1)}} \cr & {{p(s + 1)} \over {h(s + 1)}} - {{p(s)} \over {h(s)}} = {{b(s)f(s)} \over {a(s)g(s)h(s + 1)}} \cr & \Delta \left( {{{p(s)} \over {h(s)}}} \right) = {{b(s)f(s)} \over {a(s)g(s)h(s + 1)}} \cr & {{p(s)} \over {h(s)}} = \sum\limits_{k = \,v}^{s - 1} {{{b(k)f(k)} \over {a(k)g(k)h(k + 1)}}} + C \cr} $$
Then we shall verify the domain of validity of the solution standing the assumptions made.