3

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.

zaemon_23
  • 465
  • If I did the algebra correctly, $u = [a, 2a, 4a-1, 8a-6, 16a-21, 32a-63, 64a-189, \dots]$. Notice a pattern? – Dan Nov 13 '23 at 17:52
  • @Dan the pattern seems to be $u_n= 2^{n-1}a - \text{something}$. That something seems to be tripling in the last three terms, but doesn't follow that in the starting terms – zaemon_23 Nov 13 '23 at 18:15

3 Answers3

3

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.

Robert Israel
  • 448,999
  • I don't understand what do you mean by "(one particular solution) + (general solution of homogeneous equation)". 1. What is one particular solution (like do you mean a term of the sequence?). 2. What is general solution of homogeneous equation? Can you please elaborate on your answer? Thanks – zaemon_23 Nov 13 '23 at 18:11
  • @zaemon_23: Oversimplifying things a bit, the solution to $u_{n+1} = 2u_n$ is an exponential $u_n = 2^na$, and the solution to $u_{n+1} = -n^2$ is a polynomial, so try assuming that the solution is an exponential plus a polynomial. – Dan Nov 13 '23 at 18:16
  • @Dan so we need to find these two closed forms individually right? The first one is $2^n$, and the second one us already well defined to be $-n^2$, now do we combine these two as Robert Israel said? – zaemon_23 Nov 13 '23 at 18:26
3

$$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}$.

DanielV
  • 23,556
0

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?

user170231
  • 19,334
  • as I posted, I got this except for the last line. I'm not quite sure how would I proceed though. I'm pretty sure we have to solve for $U(x)$ but how – zaemon_23 Nov 13 '23 at 18:30
  • Solving for $U(x)$ is trivial, it's a linear equation. The harder part is expressing $U(x)$ as a series in order to identify $u_n$. – user170231 Nov 13 '23 at 18:32
  • FWIW Expanding the partial fractions as a power series, allows you to calculate $u_n$. – Calvin Lin Nov 14 '23 at 03:01