<s>[INST] Closed-form solution of recurrence relation I have the first-order non-homogeneous recurrence (defined for $n \geq 1$):
$$f(n) = f(n-1) \; \frac{n-1}{n} + 1$$
with base case $f(1) = 1$.
Looking at the values of the sequence ‒ $1, 1.5, 2, 2.5$ ‒ one can easily see the closed form is $f(n) = \frac{1}{2}(n+1)$.
But how whould one come to this solution without looking at the values, or if it's not obvious from the values?

If I assume the recurrence is linear, I can

*

*Compute the formula for difference:
$$\Delta_n = \frac{-f(n)}{n+1}+1$$


*Compute difference of differences:
$$\Delta^{(2)}_n = \frac{2f(n-1)-n}{n(n+1)}$$


*Knowing $\Delta^{(2)}_n = 0$ for all $n$, I obtain the closed-form solution from the formula for $\Delta^{(2)}_n$. (I also need to adjust according to the base case, which in this case happens to make no difference).


*I can verify that the closed-form solution is correct (and the recurrence is indeed linear) by substituting the closed-form solution into the original recurrence formula and checking whether the equality holds:
\begin{aligned}
f(n) &= f(n-1) \cdot \frac{n-1}{n} + 1 \\
\frac{1}{2}(n+1) &\stackrel{?}{=} \frac{1}{2}n \cdot \frac{n-1}{n} + 1 \\
\frac{1}{2}(n+1) &= \frac{1}{2}(n+1)
\end{aligned}
So now I know my solution is correct.
But what if I don't want to (cannot) assume the recurrence is linear? The result will obviously be the same, but I don't really care about the result in this particular case, but rather about a more general approach to obtaining closed-form formulas from recurrence relations.
 [/INST] You just have to use this formula
$$f(n) = f(n-1)\frac{n-1}{n} + 1$$ recursively that is,
\begin{aligned}
f(n) &= f(n-1)\frac{n-1}{n} + 1 \\
 &= (f(n-2)\frac{n-2}{n-1} +1)*(\frac{n-1}{n}) + 1 \\
 &=
f(n-2)\frac{n-2}{n} + \frac{n-1}{n} + 1
\end{aligned}
If you use it n-1 times and the condition that f(1) = 1 you get
$$f(n) = \frac{1}{n} + \frac{2}{n} + ... + \frac{n-1}{n} + 1 = 
\frac{1 + 2 + ... + (n-1)}{n} + 1 = \frac{(n-1)n}{2n} + 1 = \frac{n+1}{2}$$
</s>