Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

My answer
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$
End of my answer

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

share|improve this question
1  
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Hopefully that made sense :)

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.