Q:

Fixed point theorem and solving first-order linear recurrence relations

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.

A:

Yes, one can prove this. It's good to identify exactly what we want to show first, though:

Let $f(x)=kx+b$ be a linear function and suppose that $f(\alpha)=\alpha$. Then $$f(x)-\alpha = k(x-\alpha).$$

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.

