Repeated Substitution to solve a recurence.

In summary, the conversation discusses solving a recurrence involving T(n) = T(n-1) + n^2 and finding a pattern in the sequence. The person attempts to solve the recurrence by substituting values and eventually arrives at a third degree polynomial. They suggest trying to fit this polynomial to the sequence in order to solve the recurrence.
  • #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?
 
Physics news on Phys.org
  • #2
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.
 

What is repeated substitution in solving a recurrence?

Repeated substitution is a method used to find the general solution to a recurrence relation. It involves replacing the recurrence relation with itself multiple times until a pattern can be identified and a closed form solution can be found.

How does repeated substitution work?

In repeated substitution, the recurrence relation is repeatedly substituted with itself, using the previous term as the new term. After multiple substitutions, a pattern can be identified and a closed form solution can be found.

What are the advantages of using repeated substitution?

Repeated substitution is a relatively simple method that can be used to find a closed form solution to a recurrence relation. It also allows for a deeper understanding of the relationship between the terms in the recurrence.

Are there any limitations to using repeated substitution?

Repeated substitution may not always work for complex recurrence relations or for those with non-constant coefficients. It also requires some intuition and trial-and-error to identify the pattern and find the closed form solution.

Can repeated substitution be used for all types of recurrence relations?

Repeated substitution can be used for linear recurrence relations, where each term is a linear combination of previous terms. It may not work for non-linear recurrence relations or those with non-constant coefficients.

Suggested for: Repeated Substitution to solve a recurence.

Replies
11
Views
1K
Replies
4
Views
340
Replies
12
Views
1K
Replies
6
Views
881
Replies
4
Views
740
Replies
3
Views
917
Replies
7
Views
933
Replies
18
Views
2K
Back
Top