1. ## [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

2. btw, all numbers are subnumbers, except for the second difference one (delta squared) and it is a sub n+1 - a sub 1

3. ## Sequence

Hello amma0913
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 $\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.