Closed-form solution of recurrence relation

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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}$$

Answer 4

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.