# help in solving a recursion

EDIT: Turns out that the given solution has an error in it.

I have the following recursion question and following that is my answer. The problem is it doesn't seem to agree with the marking scheme. Can you help me by pointing out where i have gone wrong?

Question: Use substitution to solve the recurrence equation $a_n = a_{n-1}+n^2$ for $n\ge1$, given $a_0 = 7$

step 1: $a_n = a_{n-1}+n^2$
step 2: $a_n = a_{n-2}+(n-1)^2+n^2$
step 3: $a_n = a_{n-3}+(n-2)^2+(n-1)^2+n^2$
step i :$a_n = a_{n-i}+\sum_{j=0}^{i-1} (n-j)^2$

since $n-i=0$ then
$n=i$

therefore: $a_n=a_0+\sum_{j=0}^{n-1} (n-j)^2$
$a_n=7+\sum_{j=0}^{n-1} (n-j)^2$

Now the marking scheme has something totally different which i don't understand
So again, where am i going wrong?

-
In your expression it should be $(n-j)^2$ shouldn't it? In that case you'll end up with the sum of square of the first $n$ integers as in the given answer. There should also be a $6$ rather than a $2$ in the denominator of the answer supplied I believe. –  Scott H. May 3 '13 at 2:13
oh right yes, corrected it! –  Krimson May 3 '13 at 2:30

Should be

$$a_n = 7 + \sum_{j=0}^{n-1}\left(n-j\right)^2=7+\frac{1}{6}n\left(n+1\right)\left(2n+1\right)$$

provided solution simplified the series incorrectly.

-
oh ok, thanks for the confirmation! –  Krimson May 3 '13 at 2:32

So u have the the the difference between the nth term and (n-1)th term is n^2

And the zeroth term is 7,

Thus f(0) = 7, f(1) = 8, f(2) = 12, f(3) = 21

Now we know the difference is quadratic in the term number so the function itself will be (via integration) cubic. Thus it has form

F(n) = an^3 + bn^2 + cn + d

We know d = 7 from the initial case of F(0) = 7

So substituting each of the values from above into the equation we have:

F(1) = a(1)^3 + b(1)^2 + c(1) = 8

F(2) = a(2)^3 + b(2)^2 + c(2) = 12

F(3) = a(3)^3 + b(3)^2 + c(3) = 21

Thus:

a + b + c + 7 = 8

8a + 4b + 2c + 7 = 12

27a + 9b + 3c + 7 = 21

This is a a system of 3 linear equations in 3 unknowns (which simplifies to):

a + b + c = 1 8a + 4b + 2c = 5 27a + 9b + 3c = 14

It has a matrix representation of:

1 1 1 1

8 4 2 5

27 9 3 14

Which when put into reduced row echelon form (rref): is

1 0 0 1/3

0 1 0 1/2

0 0 1 1/6

Corresponding to a = 1/3, b = 1/2, c = 1/6

Therefore we conclude that for our sequence:

F(n) = 1/3(n^3) + 1/2(n^2) + 1/6(n) + 7

-
Whoops I made a really forgetful mistake let me edit –  frogeyedpeas May 3 '13 at 2:48
you are correct... this factors into the form that you have –  frogeyedpeas May 3 '13 at 2:51