Repeated Substitution to solve a recurence.

  • Thread starter Kine
  • Start date
  • #1
1
0
I have to solve the following recurrence but I keep getting stuck.


T(n) = 1, n=0
T(n) = T(n-1) + n^2, when n>1

I start by plugging in (n-1) into the function again to get...

T(n)=(T(n-2)+(n-1)^2)+n^2

Which simplifies down to (T(n-2)+2n^2-2n+1.

I then do it again and get this...

T(n)=(T(n-3)+(n-2)^2))+2n^2-2n+1

Which comes out to...

T(n) = T(n-3) + 3n^2 - 6n + 5

By this point I noticed a bit of the pattern and tried to solve the recurrence

T(n) = T(n-k) + kn^2 - (k-1)kn

However, I don't know what to do about the value at the end of the function which more or less halts my progress...

Am I going about this the correct way or am I off base?
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
963
So far you have changed from one recurance to another but you haven't "solved" the equation.

If [itex]T(0)= 1[/itex] then [itex]T(1)= T(0)+ 1^2= 1+ 1= 2[/itex], [itex]T(2)= T(1)+ 2^2= 2+ 4= 6[/itex], [itex]T(3)= T(2)+ 3^2= 6+ 9= 15[/itex], [itex]T(4)= T(3)+ 4^2= 15+ 16= 31[/itex], [itex]T(5)= T(4)+ 5^2= 31+ 25= 56[/itex]. If you do not recognize that sequence, try fitting a third degree polynomial to it.

Let [itex]p(x)= ax^3+ bx^2+ cx+ d[/itex].
Taking x= 0, 1, 2, 3 will give 4 linear equations to solve for a, b, c, and d. Check to see if that also workds for x= 4 and x= 5.
 

Related Threads on Repeated Substitution to solve a recurence.

  • Last Post
Replies
3
Views
3K
Replies
18
Views
1K
Replies
2
Views
1K
Replies
18
Views
759
Replies
2
Views
10K
Replies
2
Views
1K
  • Last Post
Replies
17
Views
2K
Replies
3
Views
856
  • Last Post
Replies
20
Views
2K
Replies
3
Views
1K
Top