Finding closed form of $u_{n+1} =2u_n - n^2$

Question

Find a closed form formula for $u_n$ where $u_{n+1} =2u_n - n^2$ and $u_0=a$

---

I'm not totally sure how closed form expressions are derived of a given sequence. I tried generating functions which goes like this: $\begin{aligned} \sum_{n=0}^{\infty} u_n x_0^n & =u_0+\sum_{n=0}^{\infty} u_{n+1} x^{n+1} \\ & =a+\sum_{n=0}^{\infty}\left(2 u_n-n^2\right) x^{n+1} \\ & =a+2 \sum_{n=0}^{\infty} u_n x^{n+1}-\sum_{n=0}^{\infty} n^2 x^{n+1} \\ & =a+2 x \cdot \sum_{n=0}^{\infty} u_n x^n-\sum_{n=0}^{\infty} n^2 x^{n+1} \end{aligned}$ Im stuck here. Please help.

Answer 1

$$u_{n+1} = 2u_n - n^2$$ Since $(n + 1)^2 = n^2 + 2n + 1$, the relevant non recursive terms are $n^2$, $n$, and $1$. $$u_{n} = v_{n} + An^2 + Bn + C$$ $$v_{n+1} + A(n+1)^2 + B(n+1) + C = 2v_n + 2An^2 + 2Bn + 2C - n^2$$ $$v_{n+1}-2v_n + (1-A)n^2 + (2A-B)n + (A + B - C) = 0$$ So choose $$1 - A = 0 \implies A = 1$$ $$2A - B = 0 \implies B=2$$ $$A+B-C = 0 \implies C=3$$ Now all you have to do is solve $v_{n + 1} = 2v_{n}$.

Answer 2

This is an inhomogeneous linear equation, so the general solution is of the form (one particular solution) + (general solution of homogeneous equation). The initial condition can then be used to choose which solution of the homogeneous equation to take. For the particular solution, try a polynomial of degree $2$. For the homogeneous equation, try an exponential.

Answer 3

For $|x|<1$, let $f(x) = \displaystyle\sum_{n\ge0} x^n = \frac1{1-x}$, and let $U(x)$ denote the generating function for $u_n$. Using the GF method, you should end up with

$$\begin{align*} \sum_{n\ge0} u_{n+1} x^n &= \sum_{n\ge0} \left(2 u_n - n^2\right) x^n \\ \sum_{n\ge1} u_n x^{n-1} &= 2 \sum_{n\ge0} u_n x^n - \sum_{n\ge0} n^2 x^n \\ \implies \frac{U(x) - a}x &= 2 U(x) - \left(x^2 f''(x) + x f'(x)\right) \end{align*}$$

Solving for $U(x)$ and expanding into partial fractions right away yields

$$\begin{align*} U(x) &= \frac{a - x f'(x) - x^2 f''(x)}{\frac1x-2} \\ &= -\frac a2 + \frac{a-6}{2(1-2x)} + \frac2{1-x} - \frac1{(1-x)^2} + \frac2{(1-x)^3} \\ &= -\frac a2 + \left(\frac a2-3\right) f(2x) + 2f(x) - f'(x) + f''(x) \end{align*}$$

Can you wrap up from here?