Solve Summation Question: T(n) Recurrence Form

  • Thread starter jamesvanboxtel
  • Start date
  • Tags
    Summation
In summary, the conversation is discussing a recurrence and trying to simplify it by moving terms and summing over different indexes. The possibility of constructing a new series is also mentioned. The participants are seeking help and suggest using a website to find a pattern.
  • #1
jamesvanboxtel
2
0
I have the following recurrence that I am trying to come up with atleast a simplified version if not a closed form.

[tex]T(n) = T(n-1) + \sum_{i=1}^{(n-1)/2} [(n-(i+1)) * (i-1) * 2 + 2][/tex]

in addition if n is even I must add the following to T(n)
[tex]((n/2) - 1)^2[/tex]If any of you can help that would be awesome.

BTW this forum looks really cool.
 
Last edited:
Mathematics news on Phys.org
  • #2
This isn't all that clear but why not move the term on the right and have T(n) - T(n-1)
then sum over n from 1 to n (if summing over n with top limit n is confusing index to a different letter, it won't make a difference in the end)on both sides for a double sum on the right.
Then the left will be have T(n) - T(0) , the T(0) you may know.
As for the right since only multiplication seems to be involved prominently the original summational need not be a problem though I'm not sure of the second that I suggested(over n)
You'll need to consider separate cases for n odd or even also. Hope I interpreted correctly.
 
  • #3
Of course, the constant +2 can be taken out of the sum; summing +2 in a loop, 'm' times, is just adding 2*m.

One question: do you really need each and all T(n)? Because maybe you could sum the terms in pairs, that is, construct a new series 'A' where A(0)=T(0)+T(1), A(1)=T(2)+T(3), A(2)=T(4)+T(5) and so on, so that the special case for even/odd terms dissapears.
 
  • #4
Turns out I was able to enter the first few results here and come up with what the pattern was.

http://www.research.att.com/~njas/sequences/ [Broken]

Thanks for trying though guys.
 
Last edited by a moderator:

1. What is a T(n) recurrence form?

The T(n) recurrence form is a mathematical representation of a problem that involves recursively calculating a function's value. It is commonly used in the analysis of algorithms to determine the time complexity of a particular algorithm.

2. How do you solve a summation question in T(n) recurrence form?

To solve a summation question in T(n) recurrence form, you first need to identify the recurrence relation, which is the mathematical formula that describes how the function's value changes with each recursive step. Then, you can use techniques such as telescoping or substitution to simplify the summation and solve for the function's value.

3. What are some common techniques for solving T(n) recurrence form?

Some common techniques for solving T(n) recurrence form include telescoping, substitution, and iteration. Telescoping involves simplifying the summation by canceling out terms, while substitution involves replacing the summation with a simpler equation. Iteration involves repeatedly applying the recurrence relation until the function's value can be determined.

4. Can T(n) recurrence form be used for both time and space complexity analysis?

Yes, T(n) recurrence form can be used for both time and space complexity analysis. In time complexity analysis, T(n) represents the number of operations required to solve a problem of size n. In space complexity analysis, T(n) represents the amount of memory required to solve a problem of size n.

5. What are the limitations of using T(n) recurrence form?

One limitation of using T(n) recurrence form is that it assumes each recursive step takes the same amount of time or space, which may not always be the case in real-world scenarios. Additionally, T(n) recurrence form may not accurately capture the complexity of certain algorithms, such as those with multiple recursive calls or nested loops.

Similar threads

  • General Math
Replies
6
Views
804
  • General Math
Replies
12
Views
2K
  • General Math
Replies
4
Views
999
Replies
6
Views
943
Replies
7
Views
1K
Replies
3
Views
955
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Replies
3
Views
620
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Back
Top