A sequence of positive real numbers is defined by

- a
_{0}= 1, - a
_{n+2}= 2a_{n}− a_{n+1}, for n = 0, 1, 2, ... .

Find a_{2005}.

It may at first seem that the sequence is not uniquely defined! However, the constraint that the sequence consists of *positive* numbers allows us to deduce the value of a_{1}. We will show that, if a_{1} 1, the sequence will eventually contain a negative number.

Letting a_{1} = x, we find

a_{0} = 1 + 0x, | a_{1} = 0 + x x > 0, |

a_{2} = 2 − x x < 2, | a_{3} = −2 + 3x x > 2/3, (1) |

a_{4} = 6 − 5x x < 6/5, | a_{5} = −10 + 11x x > 10/11, ... |

It seems clear that, as we calculate more and more terms, x will be "squeezed" between two fractions, both of which are part of a sequence which tends to 1 as n tends to infinity. (It would follow that x = 1.) We verify this intuition below.

Setting x = 0, to isolate the constant terms in (1), we obtain the sequence {b_{n}}: 1, 0, 2, −2, 6, −10, ...

We conjecture that, from b_{2} = 2, b_{3} = −2 onwards, the sequence alternates in sign, with |b_{n+2}| > |b_{n}|.

We prove this conjecture by mathematical induction.

Consider b_{2n} = r, b_{2n+1} = −s, where n, r, s are positive integers.

If n = 1, r = s = 2, which alternates in sign, as per the inductive hypothesis.

If n = k, b_{2k+2} = b_{2(k+1)} = 2r + s > r > 0, and b_{2k+3} = b_{2(k+1)+1} = −(2r + 3s) < 0, so that |−(2r + 3s)| > s.

That is, b_{2k+2} > b_{2k} > 0, and b_{2k+3} < b_{2k+1} < 0.

The result follows by induction; sequence {b_{n}} alternates in sign, with |b_{n+2}| > |b_{n}|.

Setting x = 1, we know from the recurrence relation that a_{n} = 1, for all n 0.

Therefore, the absolute value of the coefficient of x in sequence (1) must always differ by 1 from the absolute value of the constant term.

More specifically, we have

a_{2n} = b_{2n} − (b_{2n} − 1)x x < b_{2n}/(b_{2n} − 1), and

a_{2n+1} = b_{2n+1} − (b_{2n+1} − 1)x x > b_{2n+1}/(b_{2n+1} − 1). (Note: b_{2n+1} < 0.)

Since |b_{2n}| and |b_{2n+1}| are strictly increasing with n, the limit as n tends to infinity of both {b_{2n}/(b_{2n} − 1)} and {b_{2n+1}/(b_{2n+1} − 1)} is 1.

Hence x = 1.

(For any x 1, there exists n such that x > b_{2n}/(b_{2n} − 1) or x < b_{2n+1}/(b_{2n+1} − 1), and hence a_{2n} < 0 or a_{2n+1} < 0.)

Therefore a_{n} = 1, for all n 0. Specifically, a_{2005} = 1.

The above proof is from first principles. We can also use the theory of recurrence relations.

This recurrence relation may be written as a_{n+2} + a_{n+1} − 2a_{n} = 0. It is linear and homogenous, and has *characteristic equation*

m^{2} + m − 2 = (m − 1)(m + 2) = 0, with roots m = 1, m = −2.

Hence the general solution is a_{n} = A·1^{n} + B·(−2)^{n}, where A, B are constants, to be determined.

Then a_{n} > 0, for all n 0 B = 0.

And a_{0} = 1 A = 1.

Therefore the solution to the recurrence relation is a_{n} = 1, for all n 0.

Source: Traditional