Finding a closed form of $f(n) = \frac{n-4}{n}f(n-1)+1\ ,\ n \geq 5$ where $f(4) = 1$.

Question

I'm trying to find the closed form of

$f(n) = \frac{n-4}{n}f(n-1)+1\ ,\ n \geq 5$ where $f(4) = 1$.

Empirically, it turns out the answer is simply $f(n)=1+\frac{n-4}{5}\ ,\ n \geq 4$, but I'm having a hard time getting there. I've tried two ways but neither is very successful. Could someone please suggest a way through?

Attempt 1: I try to set up a generating function

$$G(x)=f(4)x^4+f(5)x^5+\dots=\sum_{k=4}^\infty f(k)x^k$$

Substituting in the recurrence (edit: noticed I forgot to add the +1) $$\begin{align}G(x)&=x^4+\sum_{k=5}^\infty(1-\frac{4}{k})f(k-1)x^k \\ &=x^4+x\sum_{k=5}^\infty (1-\frac{4}{k}) f(k-1)x^{k-1} \\ &= x^4+x\sum_{k=4}^\infty (1-\frac{4}{k+1})f(k)x^k \\ &= x^4+xG(x)-x\sum_{k=4}^\infty \frac{4}{k+1}f(k)x^k \end{align} $$

But I don't know how to express the last part in terms of G(x).

Attempt 2: Just brute force it:

With arbitrary $k$,

$$\begin{align}f(n) &= \frac{(n-4)(n-5) \dots (n-(k+3))}{n(n-1)\dots(n-(k-1))}f(n-k)\\ &\ \ + \left(1+\frac{n-4}{n}+\frac{(n-4)(n-5)}{n(n-1)}+\dots+\frac{(n-4)\dots(n-(k+2))}{n\dots(n-(k-2))}\right)\end{align}$$ Setting $n-k=4 \implies k = n -4$ and using $f(4)=1$,

$$\begin{align} f(n) &= \frac{(n-4)!}{n!/4!}+\left(1+\frac{n-4}{n}+\frac{(n-4)(n-5)}{n(n-1)}+\dots+\frac{(n-4)\dots2}{n \dots 6}\right) \\ &= {n \choose 4}^{-1}+\left(1+\frac{(n-4)!}{n!}\left(\frac{(n-1)!}{(n-5)!} + \frac{(n-2)!}{(n-6)!}+\dots +\frac{5!}{1!}\right)\right) \\ &= {n \choose 4}^{-1}+\frac{(n-4)!}{n!}\sum_{k=1}^{n-5}\frac{(k+4)!}{k!} \\ &= {n \choose 4}^{-1}+\frac{1}{n(n-1)(n-2)(n-3)}\sum_{k=1}^{n-5}(k+4)(k+3)(k+2)(k+1) \\ &= {n \choose 4}^{-1}+\frac{1}{n(n-1)(n-2)(n-3)}\sum_{k=5}^{n-1}k(k-1)(k-2)(k-3)\end{align}$$

Empirically this seems to be correct, but even Mathematica refuses to simplify it all the way down. Surely there is a better way?

Answer 1

From the recursive definition, we have the identity

$$\sum_{n=5}^\infty f(n) x^n = \sum_{n=5}^\infty \frac{n-4}n f(n-1) x^n + \sum_{n=5}^\infty x^n$$

With $G(x) = \sum\limits_{n=4}^\infty f(n)x^n$, for $|x|<1$ we have

$$\begin{align*} G(x) - x^4 &= \sum_{n=5}^\infty f(n-1) x^n - 4 \sum_{n=5}^\infty \frac{f(n-1)}n x^n + \left(\frac1{1-x} - 1 - x - x^2 - x^3 - x^4\right) \\[1ex] G(x) &= x \sum_{n=5}^\infty f(n-1) x^{n-1} - 4 \sum_{n=5}^\infty \frac{f(n-1)}n x^n + \frac{x^4}{1-x} \\[1ex] G(x) &= x G(x) - 4 \sum_{n=5}^\infty \frac{f(n-1)}n x^n + \frac{x^4}{1-x} \\[1ex] (1-x) G(x) &= -4 \phi(x) + \frac{x^4}{1-x} \end{align*}$$

where $\phi'(x) = G(x)$. Differentiating both sides and isolating $G'(x)$ yields the linear differential equation

$$G'(x) + \frac3{1-x}G(x) = \frac{4x^3-3x^4}{(1-x)^3}$$

which is solved below using the integrating factor method.

$$\begin{align*} \frac1{(1-x)^3} G'(x) + \frac3{(1-x)^4}G(x) &= \frac{4x^3-3x^4}{(1-x)^6} \\[1ex] \left(\frac1{(1-x)^3} G(x)\right)' &= \frac{4x^3-3x^4}{(1-x)^6} \\[1ex] G(x) &= (1-x)^3 \int_0^x \frac{4\xi^3-3\xi^4}{(1-\xi)^6} \, d\xi \\[1ex] G(x) &= \frac{x^4 (5-4x)}{5 (1-x)^2} \end{align*}$$

Next, get the power series expansion of $G(x)$ to determine $f(n)$. Polynomial division yields

$$G(x) = -\frac{4x^3}5 - \frac{3x^2}5 - \frac{2x}5 - \frac15 + \frac15 \frac1{(1-x)^2}$$

Use the series for the derivative of $\frac1{1-x}$ to wrap up.

$$\frac1{1-x} = \sum_{n=0}^\infty x^n \implies \frac1{(1-x)^2} = \sum_{n=0}^\infty nx^{n-1}$$

Hence

$$G(x) = -\frac{4x^3}5 - \frac{3x^2}5 - \frac{2x}5 - \frac15 + \frac15 \left(1 + 2x + 3x^2 + 4x^3 + \sum_{n=5}^\infty nx^{n-1}\right) \\ G(x) = \frac15 \sum_{n=4}^\infty (n+1)x^n = \sum_{n=4}^\infty f(n)x^n$$ $$\implies f(n) = \frac{n+1}5$$

Answer 2

Hint

If you solve $$f(n) = \frac{n-4}{n}f(n-1)+1$$ the solution is given by $$f(n)=\frac {n+1} 5+\frac C{(n-3) (n-2) (n-1) n}$$ Then, ..., try to find the mistake.

Answer 3

Alt. hint: write it as $\lambda_nf(n) = \lambda_{n-1}f(n-1) + \mu_n$ where $\lambda_n=\mu_n=n(n-1)(n-2)(n-3)$.

---

[ EDIT ] After telescoping $\,\lambda_nf(n) = \lambda_4 f(4) + \sum_{k=5}^n \mu_k\,$ where $\,\lambda_4 = 24\,$, $\,f(4)=1\,$, and the sum of falling factorials can be calculated as shown at $\sum r(r+1)(r+2)(r+3)$ is equal to?, or in the general case Partial sums of falling factorials.

Answer 4

This recurrence is linear so we can solve it as follows

$$ \cases{ f_n = f_n^h+f_n^p\\ f_n^h = \frac{n-4}{n}f_{n-1}^h\\ f_n^p = \frac{n-4}{n}f_{n-1}^p + 1\\ } $$

The solution for the homogeneous part is easy to determine

$$ f_n^h = \frac{c_0}{n(n-1)(n-2)(n-3)} $$

now assuming $f_n^p = \frac{c_0(n)}{n(n-1)(n-2)(n-3)}$ after substitution we have

$$ c_0(n)-c_0(n-1) = n(n-1)(n-2)(n-3) $$

and solving

$$ c_0(n) = \frac 15(n+1)n(n-1)(n-2)(n-3) $$

hence

$$ f_n^p = \frac 15(n+1) $$

and

$$f_n = \frac{f_0}{n(n-1)(n-2)(n-3)} + \frac 15(n+1)$$