Recurrences

September 23rd, 2009 by ben Leave a reply »
In the sequence 2001, 2002, 2003, \ldots , each term after the third is found by subtracting the previous term from the sum of the two terms that precede that term. For example, the fourth term is 2001 + 2002 - 2003 = 2000 . What is the 2004 th term in this sequence?

I know that nobody cares, but here’s my solution anyways.

This problem defines a linear recurrence x_n such that:

x_n = x_{n-3} + x_{n-2} - x_{n-1}

Replacing x_n with a constant in order to find the characteristic polynomial, \lambda^n = x_n :

\lambda^n = \lambda^{n-3} +\lambda^{n-2} - \lambda^{n-1}

Thus the characteristic polynomial of this linear recurrence is:

\lambda^n - \lambda^{n-3} -\lambda^{n-2} + \lambda^{n-1} = 0

Rearrange, and divide by \lambda^{n-3} .

\lambda^3 + \lambda^{2} -\lambda - 1 = 0

This is our characteristic polynomial. Factoring it:

(\lambda^3 - 1) + \lambda(\lambda - 1) = 0

Difference of cubes.

(\lambda - 1)(\lambda^2 + \lambda + 1) + \lambda(\lambda - 1) = 0

Combine like terms and factor \lambda^2 + 2\lambda + 1 .

(\lambda - 1)(\lambda + 1)^2 = 0

The roots of the characteristic polynomial are \{1, -1, -1\} . The root -1 has a multiplicity of two, so the general solution to the recurrence x_n is given by:

x_n = c_1 \cdot 1^n + \left( d_0 + d_1 n \right) (-1)^n

We can plug in the initial values given in the problem, x_1 , x_2 , x_3 , and x_4 to find the constants.

2001 = c_1 \cdot 1^1 + \left( d_0 + d_1 \cdot 1 \right) (-1)^1 2001 = c_1 - d_0 - d_1 2002 = c_1 + d_0 + 2d_1 2003 = c_1 - d_0 - 3d_1

Solving this system of three linear equations gives the following values for c_1 , d_0 , and d_1 :

c_1 = 2002 d_0 = 2 d_1 = -1

Therefore, the formula for the n th term of this sequence is given by:

\boxed{ x_n = 2002 + ( 2 - n ) (-1)^n }

And, finally, x_{2004} is:

x_{2004} = 2002 + (-2002)(1)
x_{2004} = 2002 - 2002
x_{2004} = \boxed{0}

Hey, Andy, you must have solved it intuitively (instead of actually solving the recurrence and finding the general formula), could ya tell me/us how? =D

Related Posts:

Advertisement

2 comments

  1. Andy says:

    Well… Not really…. haha…
    I solved like this:
    First 4 terms: 2001, 2002, 2003, 2000
    Solve for the next 2 terms….
    X5 = 2002+2003-2000 = 2005
    X6 = 2003+2000-2005 = 1998

    U can find a pattern in every other term:
    X1 = 2001
    X3 = 2003
    X5 = 2005
    and
    X2 = 2002
    X4 = 2000
    X6 = 1998
    so you can divide the main sequence into two separate ones:
    Sn (for X2, X4, X6) = 2002, 2000, 1998, 1996 ….
    Sm(for X1, X3, X5) = 2001, 2003, 2005, 2007 ….

    we really don’t need Sm to find the 2004th term so we’ll focus on Sn

    Assuming the original sequence terminates, then the number of Sn is half of the the number of terms in the original sequence.

    So… the 2004th term of the original sequence is the 1002th term of Sn
    Sn is a simple arithmetic sequence, decreasing by 2 per element/number

    thus term n = (term 1) + (n-1)(d)
    or = 2002 – 2(n-1)
    or = 2004 -2n.

    Solve for n=1002,
    =2004-2(1002)
    =0

    There’s probably an even easier way tho… buts thats how i solved it…… haha
    =)

  2. Benji says:

    … that makes me feel extremely dumb for actually solving the whole recurrence, complete with finding the general formula and all.

    >____<

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.