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)?



1 Answer 1


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.

  • $\begingroup$ is it fair to assume that if we're only interested in the value of $f(x)$ at $x = 0$, the homogeneous part of the solution is not necessary (i.e. it's equal to $0$)? $\endgroup$
    – fab
    Commented Feb 17, 2021 at 4:41
  • $\begingroup$ @fab: who said that it was zero ? $\endgroup$
    – user65203
    Commented Feb 17, 2021 at 8:40
  • $\begingroup$ I guess it's not super clear to me how to compute the values of $c_i$ but I guess I'll try to apply it to my specific case and see what I can get out of it $\endgroup$
    – fab
    Commented Feb 17, 2021 at 17:18
  • $\begingroup$ @fab: if you read between the lines, my post is saying "better drop it". $\endgroup$
    – user65203
    Commented Feb 17, 2021 at 18:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .