wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> FIND A(2005)
        
(Message started by: pcbouhid on Dec 1^st, 2005, 9:50am)

Title: FIND A(2005)
Post by pcbouhid on Dec 1^st, 2005, 9:50am

A sequence of positive real numbers is defined by

a(0) = 1,

a(n+2) = 2a(n) - a(n+1), for all n>0.

Find a(2005).

Title: Re: FIND A(2005)
Post by JocK on Dec 1^st, 2005, 10:33am

on 12/01/05 at 09:50:52, pcbouhid wrote:

A sequence of positive real numbers is defined by

a(0) = 1,

a(n+2) = 2a(n) - a(n+1), for all n>0.

Find a(2005).

This is a second order difference equation. I think you need to prescribe one more a-value (e.g. a(1) = 2 )...?

Or do you want us to specify a(2005) in terms of a(1)...?

Title: Re: FIND A(2005)
Post by pcbouhid on Dec 1^st, 2005, 10:44am

[hide]It may, at first, seem that the sequence is not uniquely defined! However, the constraint that the sequence consists of positive numbers allow to deduce the value of a(1).[/hide]

Title: Re: FIND A(2005)
Post by JocK on Dec 1^st, 2005, 10:51am

Ahhh... overlooked that particular word.. ::)

But in that case the solution is trivial, isn't it?

I go for [hide]a_n = 1 for all n.[/hide]

[hideb]Reason being that any variation between subsequent terms would 'explode' to positive and negative values, both large in magnitude.
(This is because the characteristic equation x² = 2 - x has a root -2.)
[/hideb]

Title: Re: FIND A(2005)
Post by pcbouhid on Dec 2^nd, 2005, 7:29am

[hide]You´re absolutely right, though I have a more deep proof that a(n) = 1, for all n>=0.[/hide]

Title: Re: FIND A(2005)
Post by JocK on Dec 2^nd, 2005, 3:13pm

on 12/02/05 at 07:29:34, pcbouhid wrote:

I have a more deep proof

.. educate me!

Title: Re: FIND A(2005)
Post by pcbouhid on Dec 3^rd, 2005, 4:42am

Not only you, Jock. Us. The solution isn´t mine.

There it is, in whole:

[hide]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 a1. We will show that, if a1 != 1, the sequence will eventually contain a negative number.

Letting a(1) = x, we find (===> means "imply"):

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.[/hide]
Let me know if there are mistakes in the transcription.

Title: Re: FIND A(2005)
Post by Icarus on Jan 23^rd, 2006, 4:13pm

An alternative way of showing the result: Note that if X and Y are two sequences satisfying a_n+2 = -a_n+1 + 2a_n, then cX + dY also satisfies the condition, for any real numbers c, d. Thus the set of all such sequences form a linear space. Since the sequences are all uniquely determined by their first two elements, the space is 2-dimensional. Hence, if we can identify 2 independent sequences X and Y satisfying the condition, all such sequences are of form cX + dY. Consider the sequence {rⁿ}, for some r. This sequence will satisfy the condition provided r² = -r + 2, or r² + r - 2 = 0. The quadratic has 2 solutions: r = 1, r = -2. So every sequence satisfying the formula has form c1ⁿ + d(-2)ⁿ = c + d(-2)ⁿ.

By choosing n > log₂ |c/d|, and of the appropriate parity, we get negative terms for any value of c and d except d = 0. Since the sequence in question is positive, d = 0, and the sequence is constant.