Formula for infinite sequence

Question

I have the following sequence:

$$\begin{align}x_1&=2\\ x_n&=x_{n-1}(ab+a)-1\end{align}$$

$a$ and $b$ are positive numbers.

What would be the formula for $x_n$ that does not refer to $x_{n-1}$?

Answer 1

Let $c=ab+a$ to make the numbers nicer; then $x_1 = 2$ and $x_n = c x_{n-1} - 1$.

Then $x_2 = 2c-1, x_3 = 2c^2-c-1, x_4 = 2c^3-c^2-c-1$.

I formulate an inductive hypothesis! $x_i = 2c^{i-1} - c^{i-2} - \dots - c - 1$.

This is easy to prove inductively. You can also simplify it a bit if you like, noting that the $- c^{i-2} - \dots - c - 1$ terms are the [negation of a] sum of finitely many terms of a geometric series.

Answer 2

Suppose $x_n = ux_{n-1}+v $.

If $u=1$, this is $x_n = x_{n-1}+v $, so $x_n = x_0+nv$.

From now on, I will assume that $u \ne 1$.

I now apply a standard trick and divide by $u^{n}$. This becomes $\dfrac{x_n}{u^n} = \dfrac{x_{n-1}}{u^{n-1}}+\dfrac{v}{u^n} $.

Now, let $y_n = \dfrac{x_n}{u^n} $. This becomes $y_n = y_{n-1}+\dfrac{v}{u^n} $, or $y_n- y_{n-1}=\dfrac{v}{u^n} $.

Summing this from $1$ to $m-1$, we get

$\begin{array}\\ y_m-y_0 &=\sum_{n=1}^{m-1} (y_n- y_{n-1})\\ &=\sum_{n=1}^{m-1} \dfrac{v}{u^n}\\ &=v\sum_{n=1}^{m-1} (1/u)^n\\ &=v\dfrac{1/u-1/u^m}{1-1/u}\\ \text{or}\\ \dfrac{x_m}{u^m}-x_0 &=v\dfrac{1/u-1/u^m}{1-1/u}\\ &=v\dfrac{1-1/u^{m-1}}{u-1}\\ \text{or}\\ x_m &=x_0u^m+v\dfrac{u^m-u}{u-1}\\ &=u^m(x_0+\dfrac{v}{u-1})-\dfrac{uv}{u-1}\\ \end{array} $