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.
 A: One technique you can try on problems of this sort is to write later terms in terms of the initial term.
So in this problem:
$f(2)=\frac12 f(1)+1$
$f(3)=\frac23 f(2)+1=\frac13 f(1)+\frac23+1=\frac13 f(1)+\frac53$
$f(4)=\frac34 f(3)+1=\frac14 f(1)+\frac54+1=\frac14 f(1)+\frac94$
$f(5)=\frac45 f(4)+1=\frac15 f(1)+\frac{14}{5}$
Noting that $f(2)$ can be rewritten as $f(2)=\frac12 f(1)+\frac22$,
It looks like $f(n)=\frac1n f(1)+\frac{\rm thing}{n}$
The differences in that numerator ('thing') appear to be growing linearly in $n$, so we think that 'thing' is quadratic in $n$...namely 'thing' $=\frac12n^2+\frac12 n-1$.
Putting this all together, we guess that $f(n)=\frac1n f(1)+\frac{\frac12 n^2+\frac12 n-1}{n}=\frac{f(1)-1}{n}+\frac12n+\frac12$.
We can verify all this using math induction. I would note that this form shows that if $f(1)=1$, the nonlinear part vanishes.
A: 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}$$
A: If given $\,f(n) = f(n-1) \; \frac{n-1}{n} + 1,\,$ then
multiply both sides by $\,n\,$ to get
$\,n f(n) = f(n-1)(n-1)+n.\,$ Define $\,g(n):=n\,f(n).\,$
Now $\,g(n) = g(n-1) + n.\,$ The solution to this is
$\,g(n)=g(0)+\sum_{k=1}^n n.\,$ The summation is well-known and $\,g(0)=0\,$ by definition. Thus, $\,g(n)=
n(n+1)/2\,$ which implies $\,f(n)=(n+1)/2.$
This approach was suggested in a comment by Empy2.
A: Clearly,
$$
f(1) = 1
$$
$$
f(2) = f(1) \ {1 \over 2} + 1 = 1 \ {1 \over 2} = {3 \over 2}
$$
Hence, the claim
$$
f(k) = {1 \over 2} \ (k + 1) \tag{1}
$$
is true for $k = 1, 2$.
Assume that the claim (1) is true for $k = m - 1$.
Then we have
$$
f(m - 1) = {1 \over 2} \ (m - 1 + 1) = {m \over 2} \tag{2}
$$
It follows that
$$
f(m) = f(m - 1) \ {m - 1 \over m} + 1 = {m \over 2} \ {m - 1 \over m} + 1
$$
[Using (2)]
Simplifying, we get
$$
f(m) = {m - 1 \over 2} + 1 = {m + 1 \over 2}
$$
Hence, (1) is also true for $k = m$.
Hence, by the principle of mathematical induction, (1) is true for all positive integers $k$.
This completes the proof.
