In a problem I am currently working on, I want to bound the Lipschitz constant of a function defined recursively as the $J$-th term of a certain sequence of functions $(f_j)_{j\ge 0} $.
If I let $x,y$ be two arbitrary inputs and define for all $j\ge 0$ the quantity $c_j := |f_j(x)-f_j(y)|$, I can show that it satisfies $c_0 = 0$ and
$$ c_j\le|x-y|\big(1 +(d+js)m_{j-1}\big) + R(d+js)c_{j-1},\tag1$$
where $d,s,R>1$ are some fixed parameters, and the sequence $(m_j)_{j\ge0}$ is such that $m_0=1$ and
$$m_j\le R\cdot \big((d+js)\ m_{j-1} + 1\big)\quad\forall j\ge 1. \tag2$$
Working recursively, I could show (provided I didn't make a mistake) that $$m_j\le R^j\prod_{k=1}^j(d+ks) + \sum_{k=1}^j R^k \tag3 $$ and similary, $$c_j \le |x-y|\underbrace{\left[\sum_{k=1}^j R^{k-1}\left(\prod_{\ell=0}^{k-2}\big( d+(j-\ell)s\big) + m_{j-k}\prod_{\ell=0}^{k-1}\big( d+(j-\ell)s\big)\right)\right]}_{=:L_j}\tag4 $$
Main question : What is a reasonably tight upper bound of $L_j$ as a function of $j,d,s,R$ whose mathematical expression is as "tractable" as possible (e.g. with as little sums and products as possible) ?
Sorry for the lack of precision here on what I mean by "tractable" upper bound, but essentially I need something that is easy enough to work with so that I can relate it to other variables of my problem.
Also, as I might be looking at similar problems for different families of recursive functions in the future, I wanted to know if there is a "systematic way" to go about evaluating these kind of recurrence relations, as it is easy to make a mistake when handling them manually.
Extra : are there any references (papers, books..), or software that provide ways to solve recursions such as $(1)$ or $(2)$ "automatically" ?
Thanks for your time !
So it turns out that all the products which appear in the bounds $(3)$ and $(4)$ have closed form expressions. Indeed, for any fixed $a,b>0$ and $n,m\in\mathbb N $ we have $$\prod_{k=n}^{m-1} (a + kb) = a^{n-m}\prod_{k=n}^{m-1} \left(1 + k\frac{b}{a}\right) = a^{n-m}\frac{\Gamma(1+mb/a)}{\Gamma(1+nb/a)} $$ Hence if we rewrite everything in closed-form, we get the equivalent expression for $L_j$ : $$\begin{align}L_j &= \sum_{k=1}^j R^{k-1}d^{k-1}\frac{\Gamma\left(1+(j+1)\frac s d\right)}{\Gamma\left(1+(j-k+2)\frac sd\right)}\\ &+\sum_{k=1}^j R^{k-1}d^{k}\left( \left(d^j \frac{\Gamma\left(1 + (j+1)\frac sd\right)}{\Gamma\left(1 + \frac sd\right)} + \frac{R^{j-k}-1}{R-1}\right)\left(\frac{\Gamma\left(1+(j+1)\frac s d\right)}{\Gamma\left(1+(j-k+1)\frac sd\right)}\right)\right). \end{align}$$ Although it still looks scary, this expression is at least a sum of "usual" functions, so I expect it'd be possible to do better than the "brute force" approach (that is, multiplying the maximum summand by $j$) to bound it. For instance, any good bound on the ratio $$\frac{\Gamma(1+x)}{\Gamma(1+y)} $$ for $x,y>0$ would be helpful. Any ideas/references ?
Here's a start.
Using $e^x \ge 1+x$,
$\begin{array}\\ p_n &=\prod_{\ell=0}^{n}\big( d+(j-\ell)s\big) \\ &=\prod_{\ell=j-n}^{j}\big( d+\ell s\big) \\ &=d^{n+1}\prod_{\ell=j-n}^{j}\big( 1+\ell s/d\big) \\ &\le d^{n+1}\prod_{\ell=j-n}^{j}e^{\ell s/d} \\ &= d^{n+1}e^{\sum_{\ell=j-n}^{j}\ell s/d} \\ &= d^{n+1}e^{(s/d)\sum_{\ell=j-n}^{j}\ell} \\ &= d^{n+1}e^{(s/d)(j(j+1)-(j-n)(j-n-1))/2} \\ &= d^{n+1}e^{(s/d)(2 j n + 2 j - n^2 - n)/2} \\ \text{so}\\ p_{k-2} &\le d^{k-1}e^{(s/d)(2 j (k-2) + 2 (k-2) - (k-2)^2 - (k-2))/2} \\ &\le d^{k-1}e^{(s/d)(2 j k - 4 j - k^2 + 5 k - 6)/2} \\ \end{array} $
and similarly for $p_{k-1} $.