1

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?

Krimson
  • 591
  • 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 03 '13 at 02:13
  • oh right yes, corrected it! – Krimson May 03 '13 at 02:30

2 Answers2

1

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.

parsiad
  • 25,154
1

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 :)

Sidharth Ghoshal
  • 16,771