Add Me!Close Menu Navigation

Almost Linear

Find the general term of the sequence given by x_0 = 3, x_1 = 4, and

    $$(n + 1 )(n + 2 )x_n = 4 (n + 1 )(n + 3 )x_{n - 1} - 4 (n + 2 )(n + 3 )x_{n - 2}$$

We want to formulate this problem as x_n = f(x_{n-1}, x_{n-2}) instead, so the natural thing to do is to divide both sides by (n+1)(n+2)

    \begin{align*} x_{n} &= 4\frac{n+3}{n+2}x_{n-1} - 4\frac{n+3}{n+1}x_{n-2} \\ \frac{x_{n}}{n+3} &= 4 \frac{x_{n-1}}{x+2} - 4\frac{x_{n-2}}{n+1} \\ \intertext{Since we see a monotonic pattern, we can derive a linear recurrence $z_n = \frac{x_{n}}{n+3}$} z_n &= 4 z_{n-1} - 4z_{n-2} \\ p_Z(\lambda) &= \lambda^2 - 4\lambda + 4 \\ \lambda_1,\lambda_2 &= \frac{4 \pm \sqrt{16-16}}{2} = 2,2 \\ \intertext{As with ODEs whose characteristic polynomial are rank deficient, we know that $z_n = A2^n + Bn2^{n-1}$, and apply initial value conditions on $z_0$ and $z_1$ to find their coefficients} z_0 &= A \\ &= \frac{3}{3} \\ z_1 &= 2A + B \\ &= B + 2 \\ &= \frac{4}{4} \\ B &= -1 \end{align*}

Therefore, z_n = 2^n - n2^{n-1}, which means that x_n = \left(2^n-n2^{n-1}\right)(n+3). \blacksquare

Posted By Lee

Woosh