Results 1 to 4 of 4

Thread: [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
    Thanks
    1

    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 $\displaystyle a_1 = 819$. Here's my solution - there may be a more elegant one!

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

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

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

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

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

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

    $\displaystyle = 3a_n -2a_{n-1} + 1 + 2$

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

    $\displaystyle = 4a_{n-1} - 3a_{n-2} + 1 + 2 + 3$

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

    $\displaystyle = \dots$

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

    When $\displaystyle n = 90$ and $\displaystyle i = 71$:

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

    $\displaystyle \Rightarrow a_{18} = 37$

    Using (1) in the format

    $\displaystyle a_n = 2a_{n+1} - a_{n+2} + 1$

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

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

    Putting $\displaystyle n = 1$ and $\displaystyle i = 17$:

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

    $\displaystyle = 819$

    I have checked this all out on an Excel spreadsheet, and it does indeed give $\displaystyle 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
    5
    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: Feb 7th 2011, 11:15 AM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM
  4. recurrence relations of given sequences
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Jun 4th 2008, 08:15 AM
  5. AIME I Question
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Mar 12th 2006, 02:14 PM

Search Tags


/mathhelpforum @mathhelpforum