Using generating functions to solve a recurrence

Question

I am trying to learn generating functions so I am trying this recurrence:

$$F(n) = 1 + \frac{n-1}{n}F(n-1)$$

But I am struggling with it. Luckily the base case can be anything since $F(1)$ will multiply it by $0$ anyway, so let's say $F(0) = 0$. Then I tried this:

$$G(x) = \sum_{n=0}^{\infty} F(n)x^n$$

Remove base case $n=0$, split $F(n)$ into its parts:

$$G(x) = 0 + \sum_{n=1}^{\infty} x^n + \sum_{n=1}^{\infty} \frac{n-1}{n} F(n-1) x^{n}$$

Simplify the first sum (accounting for $n=0$), pull $x$ out of the right sum and shift index:

$$G(x) = -1 + \frac{1}{1-x} + x\sum_{n=0}^{\infty} \frac{n}{n+1} F(n) x^{n}$$

At this point I don't know how to simplify the right sum any further because I cannot simply pull out $\frac{n}{n+1}$ and replace the sum with $G(x)$ like I normally can with constant coefficients.

Just looking for hints because I want to solve this myself (as much as I can, anyway), please. What are the typical methods people use at this point?

Answer 1

Hint: Life will be more pleasant if we let $kF(k)=W(k)$. Then we are looking at $W(n)=n+W(n-1)$. The generating function is straightforward, and then we can obtain the generating function of $F$.

Answer 2

If you are interested in an easier proof:

Observe:

$F(1)=1$, $F(2)=\frac{3}{2}$, $F(3)=2$, $F(4)=\frac{5}{2}$ $\dots$

Now it is easy to get the pattern $F(n)=\frac{n+1}{2}$ and prove it by induction.

First you can check that the induction base $F(1)=1$ holds.

In the induction step, assume $F(n)=\frac{n+1}{2}$. Then $$F(n+1)= 1 + \frac{n+1-1}{n+1}F(n)=1+\frac{n}{n+1}\frac{n+1}{2}=\frac{n+2}{2},$$ where we used the induction assumption.

Answer 3

The usual GF-approach may go through the following lines. We have $F(0)=0$ and $n F(n) = n + (n-1) F(n-1)$. Assuming that $$ G(x) = \sum_{n\geq 0}F(n) x^n = \sum_{n\geq 1}F(n) x^n,\tag{1} $$ we have: $$ x\cdot G'(x) = \sum_{n\geq 1} n F(n)\,x^{n}=\sum_{n\geq 0} n F(n)\,x^{n}, \tag{2}$$ $$ x^2\cdot G'(x) = \sum_{n\geq 0} (n-1) F(n-1)\, x^n,\tag{3} $$ $$ \sum_{n\geq 0}n\,x^n = \frac{x}{(1-x)^2}\tag{4}$$ hence the recurence relation turns into the pseudo-DE $$ x G'(x) = \frac{x}{(1-x)^2}+x^2 G'(x)\tag{5} $$ leading to $G'(x)=\frac{1}{(1-x)^3}$ and $G(x)=K+\frac{1}{2(1-x)^2}$. Since $G(0)=0$ we have $K=-\frac{1}{2}$, hence:

$$ G(x) = \frac{1}{2}\sum_{n\geq 1}\binom{n+1}{1}x^n \tag{6} $$ by stars and bars, and $F(n)=\frac{n+1}{2}$ for any $n\geq 1$ readily follows.