Find the general term of $x_{n+1} = \frac{x_n + 1}{n+1}$ where $x_1 = 0$

Question

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.

Answer 1

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!$$

Answer 2

Another way to find the same answer : let $x_n=\frac{a_n}{b_n}$ (with $a_n$ and $b_n$ integers), then $$x_{n+1}=\frac{1+\frac{a_n}{b_n}}{n+1}=\frac{a_n+b_n}{(n+1)b_n}$$ so that $$a_{n+1}=a_n+b_n\text{ and }b_{n+1}=(n+1)b_n$$ with initial conditions $a_1=0$ and $b_1=1$. Solving this, you find $b_n=n!$, and $a_n=\sum_{k=1}^{n-1}k!$, so $$x_n=\frac{1!+2!+\dots+(n-1)!}{n!}$$