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?
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 :)
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.
