<s>[INST] Finding a closed form of $f(n) = \frac{n-4}{n}f(n-1)+1\ ,\ n \geq 5$ where $f(4) = 1$. 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?
 [/INST] 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$$
</s>