# Method of solving no-homogeneous recurrence equation

I need to obtain a closed form of $M(t)$, satisfying the following recurrence equation:

$$M(t+1)=a+bM(t)+\frac{c}{t+1}\sum_{t'=0}^tM(t')+df(t)$$

Where $f(t)$ is a known function and $a$, $b$, $c$ and $d$ are known constants. And with the initial condition $M(t=0)=0$.

I've never solved an equation of this kind, so I'm asking for a known analythic method for obtaining a closed form of the function $M(t)$. Maybe a reference book may help, or just the name of one method of solution.

## migrated from physics.stackexchange.comMar 11 '15 at 17:21

This question came from our site for active researchers, academics and students of physics.

• Would Mathematics be a better home for this question? – Qmechanic Mar 11 '15 at 17:10
• Comment to the question (v3): If $t=0$ then you are dividing with zero on the rhs. – Qmechanic Mar 13 '15 at 0:32
• Do you have other boundary conditions? – Alex R. Mar 18 '15 at 2:44
• Observe that $(t+1)M(t+1)-tM(t)=a+(t+1)bM(t)-tbM(t-1)+cM(t)+(t+1)df(t)-tdf(t-1)$. After reduction one gets $M(t+1)=A(t)M(t)+B(t)M(t-1)+C(t)$, where $A(t)=\frac{t(b+1)+b+c}{t+1}, B(t)=-\frac{tb}{t+1}, C(t)=\frac{a+d((t+1)f(t)-tf(t-1))}{t+1}$. – Marcin Malogrosz Mar 18 '15 at 17:50
• Also, why the nonlinear system tag? There are no nonliear functions of $M$ in this. Although one coefficient depends nonlinearly on $t$, this does not make a nonlinear system. – rajb245 Apr 19 '15 at 15:25

There is, I fear, not much to be done for lower values of $t$. But the asymptotics for $t\to\infty$ could reasonably be estimated, depending on the values of the parameters. For instance, if $b>0$, write $h(t)=tb^{-t}M(t)$ and consider the functional equation $$h(t+1)=\frac{t+1}th(t)+(t+1)b^{-t-1}\left(a+df(t)\right)+\frac cb \frac {t+1}{t}\int_0^tb^{u-t}h(u)\frac{\mathrm du}u$$ which is equivalent to your recurrence equation. As $t\to\infty$, one can expand $h(t+1)$ to the first order and neglect the second order terms in $t$ (i.e. using $t+1\simeq t$) and get a more addressable equation $$h'(t)=tb^{-t}\left(a+df(t)\right)+\frac cb\int_0^tb^{u-t}h(u)\frac{\mathrm du}u.$$

From there, everything depends on the function $t\mapsto tb^{-t}\left(a+df(t)\right)$. It is impossible to say something general and you will probably have to distinguish cases, that is find which term is leading the asymptotic behaviour.

However, in the case the function $t\mapsto tb^{-t}(a+df(t))$ is bounded you can use Grönwall's inequality to bound the solution. Let us say that $tb^{-t}(a+df(t))$ is between $A>0$ and $B>0$ for sufficiently large $t$. Since the antiderivative of $u\mapsto b^u/u$ is $u\mapsto\mathrm{Ei}\left(u\log b\right)$, you get the asymptotic behaviour of $h$ as roughly $h(t)\sim \exp\left(\frac cb \mathrm {Ei}(t \log b)\right)$ which gives $$M(t)\sim \frac{b^t}t\exp\left[\frac cb\mathrm{Ei}\left(t\log b\right)\right].$$ The leading constant would be in that case a number between $A$ and $B$.

I have an explicit solution, which I obtained by using the method of generating functions. First, compute what I called $P_n(1)$ from a recurrence relation. Then use those to compute explicit values of $M(k)$. $P_n(1)$ is the sum of the $M(k)$ values, for $0 \le k \le n$. You don't even need to compute all $P_n(1)$ values ahead of time. You can compute the $P$'s and the $M$'s in alternation (one $P$, one $M$, one $P$, one $M$, etc).

$\begin{array}{rcl} P_n(1) &\!\!\!=&\!\!\! \sum_{k\,=\,1}^{n} b^k \sum_{j\,=\,0}^{k-1} \frac{\displaystyle (j+1)\,[\,a + d\,f(j)\,] + c\,P_j(1)}{\displaystyle (j+1)\,b^{j+1}} \qquad (n \ge 1) \\[0.2in] % M(k) &\!\!\!=&\!\!\! b^k \sum_{j\,=\,0}^{k-1} \frac{\displaystyle (j+1)\,[\,a + d\,f(j)\,] + c\,P_j(1)}{\displaystyle (j+1)\,b^{j+1}} \qquad (k>0)\,. \end{array}$

Now, the proof of this result took me 4 pages of LaTeX, with lots of macros of my own that are not supported by the LaTeX engine here so I'm not sure what the best way to share that proof is. For now, I'm going to post screen shots.

• This is a good idea to use a generating function. But unfortunately this solution requires computing $P_n(1)$ step by step using the first formula in the frame, and the recurrence on $P_n$ belongs actually to the same class as the initial recurrence on $M$. So I see little improvement. – Tom-Tom Apr 20 '15 at 12:55
• One step at a time... I'm working on solving the recurrence for $P_n(1)$. :) – wltrup Apr 20 '15 at 12:58
• No luck so far in regards to solving the recurrence for $P_n(1)$. And not for lack of trying! – wltrup Apr 20 '15 at 16:41
• I've been trying to sum up the generating function with infinite $n$. I get a pretty weird functional equation (using your notations and $|z|<1$) $$P(z)=\frac{H(z)}{1-bz}+c\int_0^z \frac {P(z)}{u(1-u)\ln\frac zu}\mathrm du.$$ Maybe there is something to do from there, but I really can't see what. – Tom-Tom Apr 21 '15 at 8:25
• I worked on that for a few hours yesterday, to no avail. I'm afraid there's no way to solve this problem analytically. As someone commented in the original question, the original recurrence can be cast into a non-homogeneous 2nd-order recurrence with non-constant coefficients, $M(k+1) + a_k\,M(k) + b_k\,M(k-1) + c_k = 0$. I couldn't find any references on the web on solving those analytically so I doubt anyone will be able to solve for $M(k)$ or $P_n(1)$ separately. I'd love to be wrong on that opinion, though. – wltrup Apr 21 '15 at 8:32