Did I correctly derive this recurrence equation formula

Question

I started with the recurrence equation $\space\space x_{n+1}=ax_n+b \space \space$ and turned it into the formula at the bottom to allow us to find the value of any nth term in the form $\space \space x_n=f(n)$

Here is how I derived my formula for $f(n)$:

$$x_0=x$$ $$x_1=ax+b$$ $$x_2=a^2x+ab+b$$ $$x_3=a^3x+a^2b+ab+b$$ $$x_n=a^nx+a^{n-1}b+a^{n-2}b...a^2b+ab+b$$ Refer to the geometric progression equation: $$\sum_{k=1}^{n}a^{k-1}b=\frac{b(1-a^n)}{1-a}$$ $$x_n=a^nx+\frac{a^nb-b}{a-1}$$ $$x_n=\frac{a^{n+1}x-a^nx+a^nb-b}{a-1}$$ $$x_n=\frac{a^n(ax-x+b)-b}{a-1}$$ Final simplification and substitution of $x_0=x$ $$x_n=\frac{a^n((a-1)x_0+b)-b}{a-1}$$ Side Note: This idea originally came from problems I encountered in the Collatz Conjecture, eventually leading to create a general formula. Could this potentially be helpful to have other than my own personal use?

Answer 1

You can make it easier. Considering $$ x_{n+1}=a\,x_n+b $$ let $x_n=y_n+c$ to make $$y_{n+1}+c=a\, y_n+ac+b$$ that is to say $$y_{n+1}=a\, y_n+(ac+b-c)$$ Choose $c$ such that $ac+b-c=0$ and you are back to the classical geometric sequence. Solve it for $y_n$ and go back to $x_n$.

Answer 2

This is a linear recurrence with constant coefficients and it can also be solved similarly to a linear ODE.

The homogeneous equation is

$$x_{n+1}=ax_n$$ and obviously has the general solution

$$x_n=ca^n.$$

Now a particular solution of the non-homegeneous equation

$$x_{n+1}=ax_n+b$$ is given by a constant, let $d$, such that

$$d=ad+b.$$

We have

$$x_n=ca^n+\frac b{1-a}$$ and we plug the initial condition $x=x_0$,

$$x_0=c+\frac b{1-a}$$ and finally

$$x_n=a^nx_0+\frac{1-a^n}{1-a}b.$$

---

Other method:

The relation $x_{n+1}=ax_n$ hints the transformation $x_n=a^ny_n$, leading to the modified recurrence

$$y_{n+1}=y_n+ba^{-n},$$ which is solved by the summation of a geometric series

$$y_n=y_0+b\sum_{k=1}^na^{-k}=y_0+a^{-1}\frac{1-a^{-n}}{1-a^{-1}}.$$

Then

$$x_n=a^nx_0+\frac{a^n-1}{a-1}b.$$