Using generating functions to solve a recurrence 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?
 A: 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.
A: 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$.
A: 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.
