Solving a non-linear recurrence relation.

Question

I have a recurrence relation of the following form:

$x(t+1)=\alpha x(t) t-\beta t$

Could anyone point me to a resource for how to solve the above for an arbitrary initial condition, $x(0)$?

Answer 1

This is not an answer but just the result from a CAS.

Considering $$x_{t+1}=\alpha\, t\, x_t-\beta\, t\qquad \qquad(\text{with }\,x_\color{red}{1}=a)$$ a CAS gave me an awful result which only simplifies if $\alpha >0$. It is $$x_t=\alpha ^{t-2} (t-1) \left(a\, \alpha \, (t-2)!-e^{\frac{1}{\alpha }} \beta \,\, \Gamma \left(t-1,\frac{1}{\alpha }\right)\right)$$ where appears the incimplete gamma function.

Answer 2

It is a linear recurrence, just not with constant coefficients. Luckily, it is first order.

Say you got $x_{n + 1} = a_n x_n + f_n$ with $x_0$ given. You can divide by the summing factor $a_n a_{n - 1} \dotsb a_0$ to get:

$\begin{align*} \frac{x_{n + 1}}{a_n a_{n - 1} \dotsb a_0} - \frac{x_n}{a_{n - 1} \dotsb a_0} &= \frac{f_n}{a_n a_{n - 1} \dotsb a_0} \\ \end{align*}$

If you sum over $0 \le n \le m$, the left hand side telescopes nicely. You can continue to get a general formula, but it is messy.

In your specific case, the summing factor is $\alpha^t t!$, so that:

$\begin{align*} \frac{x(t + 1)}{\alpha^t t!} - \frac{x(t)}{\alpha^{t - 1} (t - 1)!} &= - \frac{\beta}{(t - 1)!} \\ \sum_{1 \le t \le n - 1} \left( \frac{x(t + 1)}{\alpha^t t!} - \frac{x(t)}{\alpha^{t - 1} (t - 1)!} \right) &= - \beta \sum_{1 \le t \le n - 1} \frac{1}{(t - 1)!} \\ \frac{x(n)}{\alpha^{n - 1} (n - 1)!} - x(1) &= - \beta \exp_{n - 1}(1) \\ x(n) &= x(1) \cdot \alpha^{n - 1} (n - 1)! - \alpha^{n - 1} \beta (n - 1)! \exp_{n - 1}(1) \end{align*}$

Here we use the truncated exponential function $\exp_k(x) = \sum_{0 \le r \le k} \frac{x^r}{r!}$