Find the general term of $x_{n+1} = \frac{x_{n} + 1}{n + 1}$ where $x_1 = 0$
I've tried finding the general term by introducing a generating function $G(z)$ and then solving for $G(z)$ with no luck.
I've also tried to express $x_n$ and get rid of the constant doing the following:
$$
x_{n+1} = \frac{x_n + 1}{n+1}\\
x_n = \frac{x_{n-1} + 1}{n}
$$
Subtract one from another:
$$
(n+1)\cdot x_{n+1} – n\cdot x_n = x_n – x_{n-1}
$$
So:
$$
(n+1)\cdot (x_{n+1} – x_n) = -x_{n-1}
$$
Not sure how to proceed from here. I've seen how recurrence relations are solve with characteristic equations. Should i introduce some characteristic polynomial and solve it?
Basically i'm more interested in a common approach than in solution (yet an example would be nice) since i am going to solve lots of similar problems after this one.
Best Answer
Hint. Let $z_n=n!x_n$ then $z_0=0$ and $$z_{n+1}=(n+1)!x_{n+1}=n!(n+1)x_{n+1}=n!(x_n+1)=z_n+n!\\= z_{n-1}+(n-1)!+n!=\sum_{k=1}^n k!$$