<s>[INST] difference equation( recurrence relation) Let $y_n$ satisfy the nonlinear difference equation:
$$(n+1)y_n=(2n)y_{n-1}+n.$$
Let $u_n=(n+1) y_n$. Show that
$$u_n= 2u_{n-1}+n.$$
Solve the linear difference equation for $u_n$. Hence find $y_n$ subject to the initial condition $y_0=4$.
I have showed that $u_n=2u_{n-1}+n$, but I don't know how to do the next step, can anyone help me with this please?
 [/INST] Firstly, divide throughout by $2^n$ to get:
$$\frac{u_n}{2^n} = \frac{u_{n-1}}{2^{n-1}} + \frac{n}{2^n}$$
Rearrange to get
$$\frac{u_n}{2^n} - \frac{u_{n-1}}{2^{n-1}} = \frac{n}{2^n}$$
Sum from $1$ to $n$:
$$\sum_{i=1}^n \frac{u_i}{2^i} - \frac{u_{i-1}}{2^{i-1}} = \sum_{i=1}^n\frac{i}{2^i}$$
$$\frac{u_n}{2^n} - \frac{u_0}{2^0} = \left(\frac{1}{2}\right)^1 + 2\cdot\left(\frac{1}{2}\right)^2 + 3\cdot\left(\frac{1}{2}\right)^3 + \dots + n\cdot\left(\frac{1}{2}\right)^n$$
Now, recall that
$$(1 - x^n)(1-x)^{-1} = (1 + x + x^2 + \cdots + x^{n-1})$$
Differentiate both sides to get:
$$(1-x^{n+1})(1-x)^{-2} -(n+1)x^{n}(1-x)^{-1} = 1 + 2x + 3x^2 + \cdots + nx^{n-1}$$
I'll leave the rest to you :)
</s>