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?
 A: 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 :)
A: This is a linear recurrence of the first order, thus solvable. Write:
$$
y_{n + 1} - \frac{2 n + 2}{n + 2} y_n = \frac{n + 1}{n + 2}
$$
If this is written:
$$
y_{n + 1} - u_n y_n = f_n
$$
you can divide by the summing factor:
$$
s_n = \prod_{0 \le k \le n} u_n
$$
to get the nicely telescoping:
$$
\frac{y_{n + 1}}{s_n} - \frac{y_n}{s_{n - 1}} = \frac{f_n}{s_n}
$$
Here the summing factor is:
$$
s_n 
  = \prod_{0 \le k \le n} \frac{2 k + 2}{k + 2}
  = \frac{2 \cdot 4 \cdot \ldots \cdot (2 n + 2)}
         {2 \cdot 3 \cdot \ldots \cdot (n + 2)}
  = \frac{2^n (n + 1)!}{(n + 2)!}
  = \frac{2^n}{n + 2}
$$
Sure enough:
$$
\frac{(n + 2) y_{n + 1}}{2^n} - \frac{(n + 1) y_n}{2^{n - 1}} 
  = \frac{n + 1}{2^n}
$$
Sum over $0 \le n \le k - 1$ to get:
$$
\frac{(k + 1) y_k}{2^{k - 1}} - \frac{y_0}{2^{-1}}
  = \sum_{0 \le n \le k - 1} \frac{n + 1}{2^{n - 1}}
$$
Still need the sum on the right hand side:
$$
\sum_{0 \le n \le k - 1} \frac{n + 1}{2^{n - 1}}
  = 2 \sum_{0 \le n \le k - 1} (n + 1) \cdot 2^{-n}
$$
\begin{align}
\sum_{0 \le n \le k} z^n
  &= \frac{1 - z^{k + 1}}{1 - z} \\
\sum_{0 \le n \le k} n z^{n - 1}
  &= \sum_{0 \le n \le k - 1} (n + 1) z^n \\
  &= \frac{\mathrm{d}}{\mathrm{d} z} \frac{1 - z^{k + 1}}{1 - z}
  &= \frac{1 - (k + 1) z^k + k z^{k + 1}}{(1 - z)^2}
\end{align}
Evaluating the last expression at $z = 1/2$ gives:
$$
\sum_{0 \le n \le k - 1} (n + 1) 2^{-n}
  = \frac{2^{k + 2} - 2 k  - 4}{2^k}
$$
Pulling all together:
$$
y_k = \frac{2^{k + 2} - 2 k - 4 + 2^k y_0}{k + 1}
$$
Phew!
Maxima did much of the algebra.
