Consider the following sequence $\begin{cases}
u_0 = 1 \\
u_n = 1.5u_{n-1} + 1
\end{cases}$
Usually to find the closed formula of a simple sequence like this you either use iteration and back-substitution or you build a telescoping sum from the recurrence formula.
Before being introduced to characteristic polynomial equations with linear algebra and generating functions, we solved recurrence relations in the form of
$$u_n = au_{n-1} + b \quad\text{with}\quad a,u \in\mathbb{R}$$
by determining the fixed point $\alpha$ such as $\alpha = a \alpha + b$ and involving the fact that
$$\left(u_n – \alpha\right) = k\left(u_{n-1} – \alpha\right)$$
The fixed point $\alpha$ is then used as a pivot to construct an auxiliary geometric sequence $v_n = u_n – \alpha$ and through algebraic manipulations you get
$$v_n = a\left(v_{n-1}\right)$$
so that $k=a$. The closed formula in term of $v_n$ can now be determined since $u_n = v_n + \alpha$ and we have
$$u_n = \left(u_0 – \alpha\right) \cdot a^n + \alpha$$
So for the first example we have
$$u_n = 3 \times 1.5^n – 2$$
The following seems intuitive since shifting by the fixed point also shift the initial condition and the difference is geometric
$$\left(u_n – \alpha\right) = k\left(u_{n-1} – \alpha\right)$$
However, is there any formal proof to this statement?
In fact, the fixed point happens to be the particular solution $P_x$ (here as a constant sequence $u_n = \alpha$) for the complete solution $S_x = Q_x + P_x$ of an non-homogeneous recurrence relation. This method happens to be a shorthand for the complete proof using linear algebra. Conjugacy is used as the proof mechanism but the underlying motivation has something to do with linear algebra.
Best Answer
Yes, one can prove this. It's good to identify exactly what we want to show first, though:
Note that if $x=u_{n-1}$ then $f(x)=u_n$, so this is precisely what you are trying to prove. We can prove this by algebraic manipulation: \begin{align*}f(x)-\alpha&=f(x)-f(\alpha)\\ &=(kx+b)-(k\alpha+b)\\ &=k(x-\alpha) \end{align*} where the first step uses that $\alpha=f(\alpha)$ and the second step follows from substituting in the definition of $f$ and the last step follows from cancelling and factoring out $k$.
Note that we could apply this theorem at $f(x)$ to get $$f(f(x))-\alpha = k(f(x)-\alpha)$$ and then applying the theorem at $x$ gives $$k(f(x)-\alpha) = k^2(x-\alpha).$$ We could similarly find that $f(f(f(x)))-\alpha = k^3(x-\alpha)$ by repeatedly applying the above theorem - and solving for $f(f(f(x)))$ and so on gives the closed form solution to the recurrence relation.
A slightly nicer way to see this is via conjugacy. In particular, we could define a map $g(x)=x+\alpha$ and $h(x)=kx$. We claim that $$g^{-1}(f(g(x)) = h(x)$$ which can be verified algebraically just by substituting in the functions on the each side, noting that $g^{-1}(x)=x-\alpha$, since subtraction undoes addition. This means that $f$ is conjugate to the map $h$ by $g$. You can also, by changing variables to $y=g(x)$ and applying $g$ to both sides derive $$f(y)=g(h(g^{-1}(y))).$$ Then, you can figure out that, to compute two steps, you would apply $f$ twice, but then we note $$f(f(y))=g(h(g^{-1}(g(h(g^{-1}(y)))))$$ but we can cancel out the $g^{-1}(g(\cdot))$ to get $$f(f(y))=g(h(h(g^{-1}(y)))$$ and we could proceed to see $$f(f(f(y))) = g(h(h(h(g^{-1}(y))))$$ and so on. The nice thing here is that $h$ is just multiplication - we know how to multiply something $n$ times by the same constant $k$ - that's the same as multiplying by $k^n$. This relation tells us how to transfer that knowledge to $f$ by cleverly choosing $g$ to translate $0$ to a fixed point. This general setup is applicable to more general recurrence relations.