5
$\begingroup$

Given this recurrence equation:

$u_1 = 0, u_2 = 1$

$u_n = 4u_{n−1} + 4u_{n−2}$

Is the correct characteristic equation:

$4x+4 = 4$

EDIT:

Complete solve:

The characteristic equation is

$x^2-4x-4=0$

We solve the quadratic equation...

$\alpha = 5$

$\beta=-1$

So:

$u_n = c_1 \alpha^n + c_2 \beta^n$

We solve the equation...

$c_1 = 1/30$

$c_2 = 1/6$

Finally:

$u_n = \dfrac{5^n}{30} + \dfrac{(-1)^n}{6}$

  • 0
    I don't think you have $\alpha$ and $\beta$ correct. Their product should be the constant term of the quadratic. You have $(x-2)^2-8=0$.2011-01-31

4 Answers 4

4

When I am working with recurrence relations and trying to simplify them, I like to move all of the "recurring" terms to one side. Doing this here will give you a homogeneous difference equation. So here you would get,

$u_{n} - 4u_{n-1} - 4u_{n-2} = 0$.

Now to find the characteristic equation, you may want to shift the subscripts to get,

$u_{n+2} - 4u_{n+1} - 4u_{n} = 0$.

Now, we can see that the characteristic equation will be,

$\lambda^{2} - 4 \lambda - 4 = 0$.

3

Your characteristic equation is incorrect. The way you obtain the characteristic equation is to assume $u_n = m^n$. Plug it in to get a quadratic in $m$. Solve for $m$. Get the two roots say $m_1$ and $m_2$. Now the general solution is given by the linear combination namely $u_n = a_1 m_1^n + a_2 m_2^n$. Solve for $a_1$ and $a_2$ using the initial conditions.

This methodology is analogous to plugging in $y=e^{mx}$ when you want to solve a linear ODE. Here you have a difference equation instead of a differential equation.

  • 0
    Arghhh, I wrote 36 instead of 32 when I was solving the square. You are right.2011-01-31
0

The characteristic equation is the equation satisfied by $\lambda$ if $u_n = \lambda^n$ be a solution. For example, if the recurrence is $a_n = a_{n-1} + a_{n-2}$ then a solution $\lambda^n$ must satisfy $\lambda^n = \lambda^{n-1} + \lambda^{n-2}.$ The point is that all these equations reduce to the one equation $\lambda^2 = \lambda + 1.$ Back to your question, when I follow the same steps I get something else.

0

Give Wilf's techniques a try... define $U(z) = \sum_{n \ge 0} u_{n + 1} u^z$, and write the recurrence as: $ u_{n + 2} = 4 u_{n + 1} + 4 u_n \qquad u_1 = 0, u_2 = 1 $ By properties of generating functions: $ \frac{U(z) - u_1 - u_2 z}{z^2} = 4 \cdot \frac{U(z) - u_1}{z} + 4 \cdot U(z) $ Maxima solves this as: $ U(z) = \frac{z}{1 - 4 z - 4 z^2} = \frac{1}{2^{5/2}} \cdot \frac{1}{1 - (2^{3/2} + 2) z} - \frac{1}{2^{5/2}} \cdot \frac{1}{1 + (2^{3/2} - 2) z} $ Two geometric series: $ u_{n + 1} = \frac{1}{2^{5/2}} \cdot \left( (2^{3/2} - 2)^n - (-1)^n (2^{3/2} + 2)^n \right) $