Expert: Paul Klarreich - 4/4/2008

Question
I know something and I'm looking for a proof of it.

Consider this recurrence relation.
a(n+1)=a(n)+p*n+q
a(0)=a0

I know that the answer is a second order polynomial but I need a proof of that.

If so, I can assume a(i) = a*i^2+b*i+c

Then I can solve a,b,c by the initial condition and first few terms of the sequence.

Thanks in advance,

Answer
Questioner:   Ali
Category:  Advanced Math
Private:  No
 
Subject:  Recurrene Relations
Question:  I know something and I'm looking for a proof of it.

Consider this recurrence relation.
a(n+1)=a(n)+p*n+q
a(0)=a0

I know that the answer is a second order polynomial but I need a proof of that.

If so, I can assume a(i) = a*i^2+b*i+c

Then I can solve a,b,c by the initial condition and first few terms of the sequence.

Thanks in advance,
...................................
Hi, Ali,

I am not sure what you require here, but try this:
If  a(i) = ai^2 + bi + c

Then a[i+1] = a(i + 1)^2 + b(i + 1) + c

a[i+1] = a(i^2 + 2i + 1) + b(i + 1) + c

a[i+1] = ai^2 + 2ai + a + bi + b + c

a[i+1] = ai^2  + bi + c + 2ai + a + b
        <--- a[i] --->
a[i+1] = a[i] + 2ai + a + b

Now you can take  2a as  p, and  a+b  as q.

Does that do it?