Results 1 to 4 of 4

Math Help - [SOLVED] Help please, AIME question: sequences and recurrence relations

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    57

    [SOLVED] Help please, AIME question: sequences and recurrence relations

    For any sequence of numbers A = (a1, a2, a3, ), define ΔA to be the sequence (a2- a1, a3 a2, a4 a3­,) whose nth term is an+1 an. Suppose Δ2A = (1,1,1,1,...) and a19 = 0 = a92. Find a1.

    If anyone can help or provide any information that would be great. I have no clue where to start. I think finite calculus makes this significantly easier.

    Thanks,
    Andrew
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2009
    Posts
    57
    btw, all numbers are subnumbers, except for the second difference one (delta squared) and it is a sub n+1 - a sub 1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Sequence

    Hello amma0913
    Quote Originally Posted by amma0913 View Post
    For any sequence of numbers A = (a1, a2, a3, ), define ΔA to be the sequence (a2- a1, a3 a2, a4 a3*,) whose nth term is an+1 an. Suppose Δ2A = (1,1,1,1,...) and a19 = 0 = a92. Find a1.

    If anyone can help or provide any information that would be great. I have no clue where to start. I think finite calculus makes this significantly easier.

    Thanks,
    Andrew
    This is a most interesting problem. I have the solution. It is a_1 = 819. Here's my solution - there may be a more elegant one!

    \Delta^2A = \Delta(\Delta(A))= ((a_3 - a_2)-(a_2 - a_1), (a_4-a_3)-(a_3-a_2), \dots)

    =(a_3 - 2a_2 +a_1, a_4-2a_3+a_2, \dots) where the n^{th} term is a_{n+2} - 2a_{n+1} + a_n

    So if \Delta^2A = (1, 1, 1, \dots), we have the recurrence relation

    a_{n+2} - 2a_{n+1} + a_n = 1, n \ge 1 (1)

    \Rightarrow a_{n+2} = 2a_{n+1} - a_n + 1

    = 2(2a_n-a_{n-1} +1) -a_n +1

    = 3a_n -2a_{n-1} + 1 + 2

    = 3(2a_{n-1} - a_{n-2} + 1) -2a_{n-1} +1 + 2

    = 4a_{n-1} - 3a_{n-2} + 1 + 2 + 3

    = 5a_{n-2}-4a_{n-3} + 1 + 2 + 3 + 4

    = \dots

    = (3+i)a_{n-i} - (2+i)a_{n-(i+1)} + \tfrac{1}{2}(i+2)(i+3), i \ge -1

    When n = 90 and i = 71:

    a_{92} = 74a_{19} - 73a_{18} + \tfrac{1}{2}\times 74\times 73

    \Rightarrow a_{18} = 37

    Using (1) in the format

    a_n = 2a_{n+1} - a_{n+2} + 1

    we can now create, in exactly the same way, a similar formula that gives a_n in terms of a_{n+i} and a_{n+(i+1)}; namely:

    a_n = (i+1)a_{n+i} - i a_{n+(i+1)} + \tfrac{1}{2}i(i+1), i \ge 1

    Putting n = 1 and i = 17:

    a_1 = 18a_{18} - 18a_{19} + \tfrac{1}{2}\times 17\times 18

    = 819

    I have checked this all out on an Excel spreadsheet, and it does indeed give a_{92} = 0. The spreadsheet is not terribly tidy, but I attach it for your perusal.

    Grandad
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by amma0913 View Post
    For any sequence of numbers A = (a1, a2, a3, ), define ΔA to be the sequence (a2- a1, a3 a2, a4 a3­,) whose nth term is an+1 an. Suppose Δ2A = (1,1,1,1,...) and a19 = 0 = a92. Find a1.

    If anyone can help or provide any information that would be great. I have no clue where to start. I think finite calculus makes this significantly easier.

    Thanks,
    Andrew
    The second differences are constant, so the first differences are linear in the index in fact increasing by 1 for each increment in the index, and the original series is a quadratic in the index. Then the rest is trivial.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Probability question involving recurrence relations
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: May 5th 2011, 01:07 PM
  2. Simple recurrence relations question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 7th 2011, 11:15 AM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  4. recurrence relations of given sequences
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 4th 2008, 08:15 AM
  5. AIME I Question
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: March 12th 2006, 02:14 PM

Search Tags


/mathhelpforum @mathhelpforum