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

• February 9th 2009, 08:11 PM
amma0913
[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
• February 9th 2009, 08:12 PM
amma0913
btw, all numbers are subnumbers, except for the second difference one (delta squared) and it is a sub n+1 - a sub 1
• February 10th 2009, 02:18 AM
Sequence
Hello amma0913
Quote:

Originally Posted by amma0913
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.

• February 10th 2009, 03:51 AM
CaptainBlack
Quote:

Originally Posted by amma0913
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