Closed-form solution of recurrence relation

closed-formrecurrence-relations

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.

Best Answer

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.

Related Question