Solving a non-linear recurrence relation. 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)$?
 A: 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.
A: 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!}$
