# Recurrences

September 23rd, 2009 by ben
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:

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.

>____<

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