I have a questions about recursive functions. What I usually find online are discrete functions where a new term is computed from the previous one starting from an initial condition.
What I'm generally interested in is, in general, something like this:
$$f(x) = g(x) + kf(x + p)$$
with $p > 0$ and no need of any initial conditions. This translates into an infinite expression that may or may not converge:
$$f(x) = g(x) + kg(x + p) + k^2g(x + 2p) + x^3g(x+3p)+…$$
More specifically, if $g(x)=ax+b$ is a linear function and if $k<1$, it's easy to prove (though I won't prove it here) that the recursive function converges to this explicit expression:
$$f(x) = \frac{1}{1 – k}(ax + b + \frac{apk}{1 – k})$$
So here's my question: what if the recursive (linear) function has more than one recursive term?
$$f(x) = ax + b + k_1f(x + p_1) + k_2f(x + p_2) + … + k_nf(x + p_n)$$
I suppose that if $k_1, k_2,… k_N$ are all smaller than 1, $f(x)$ will converge for all $x$ (but I haven't proved it). I searched a bit online but I couldn't find much in the existing literature. I guess I can try computing it myself but it doesn't look trivial (since the number of terms explode quickly) and likely beyond my abilities… Do you have any hints on how to compute this (or know if there are existing results somewhere in the literature)?
Thanks
Best Answer
If the $p_k$ are in rational ratios, you can rescale $x$ so that they are all integer. Now we have the discrete recurrence relation
$$f(m)-\sum_{i=1}^n k_if(m+p_i)=am+b.$$
The solution of the homogeneous part of the equation can be written in terms of the roots of the polynomial
$$1-\sum_{i=1}^n k_iz^{p_i}=0,$$ let $z_1,z_2,\cdots z_{p_n}$ (where $p_n$ is the largest coefficient). The solution is
$$f(m)=\sum_{i=1}^{p_n}c_i z_i^m.$$
Then a particular solution of the non-homogeneous equation is a linear ansatz,
$$f(m)=um+v$$ and
$$um+v-\sum_{i=1}^n k_i(u(m+p_i)+v)=am+b$$
and by identification,
$$u\left(1-\sum_{i=1}^n k_i\right)=a$$ $$v\left(1-\sum_{i=1}^n k_i\right)=b+u\sum_{i=1}^n k_ip_i.$$
Finally, the general solution
$$f(m)=um+v+\sum_{i=1}^{p_n}c_i z_i^m.$$
Note that this is only valid for integer values of $m$, and a similar relation holds for all sets of values of $x$ that are one unit apart. Finally we can write
$$f(x)=u(\{x\})\lfloor x\rfloor+v(\{x\})+\sum_{i=1}^{p_n}c_i(\{x\}) z_i^{\lfloor x\rfloor}.$$ The functions $u,v$ and $c_i$ are completely arbitrary on $[0,1)$.
As you see, the solution with a linear RHS is complex even for a moderate number of terms. For more general RHS, finding particular solutions is tremendous. And if the $p_i$ are incommensurable, I guess that the number of terms can be infinite.