How to get the closed form of this recurrence?

In summary, the conversation revolved around finding a closed form for the expression T(k, n) = T(k, n-1) + (k-2)(n-1) + 1, with repeated substitution. The person was trying to find a pattern and determine the boundary condition, and eventually came up with the solution T(k,n) = n+c+(k-2)*1*2*...(n-1).
  • #1
zeion
466
1

Homework Statement



Hello,

This expression was derived from a polygon word problem and I need to find a closed form for it with repeated substitution (I think).

T(k, n) = T(k, n-1) + (k-2)(n-1) + 1

Homework Equations


The Attempt at a Solution



Get a pattern like:

= T(k, n-2) + (k - 2)(2n - 3) - 2 subs.
= T(k, n-3) + (k - 2)(3n - 6) - 3 subs.
= T(k, n-4) + (k - 2)(4n - 10) -4 subs.
.
.
.

I'm not sure how to express the 1, 3, 6, 10 sequence in terms of number of substitutions.
 
Physics news on Phys.org
  • #2
What is the boundary coundition?
This is what I got so far.
Assuming T(k, 0) = c

T(k,n) = n+c+(k-2)*1*2*...(n-1)
 
  • #3
Sorry I wrote the expression wrong; but I got the answer I think, thanks.
 

FAQ: How to get the closed form of this recurrence?

What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence recursively, meaning that each term of the sequence is defined in terms of previous terms. This type of relation is commonly used in computer science and mathematics to model and solve problems.

What is a closed form solution?

A closed form solution is a mathematical expression that gives an exact and finite solution to a problem, without the use of recursive definitions or limits. In other words, it is a formula that directly calculates the value of a sequence or function, without the need for iterative calculations.

Why is it important to find the closed form of a recurrence relation?

Finding the closed form of a recurrence relation allows us to directly calculate the value of a sequence or function, rather than having to recursively calculate each term. This not only saves time and resources, but it also provides a more efficient and accurate solution to a problem.

What strategies can be used to find the closed form of a recurrence relation?

Some common strategies for finding the closed form of a recurrence relation include the method of substitution, the method of iteration, and the method of generating functions. These methods involve manipulating the recurrence relation in various ways to simplify it and ultimately find a closed form solution.

Are there any limitations to finding the closed form of a recurrence relation?

Yes, it is not always possible to find a closed form solution for a recurrence relation. Some recurrence relations are inherently recursive and cannot be expressed in closed form. Additionally, some relations may have closed form solutions, but they may be very complex and difficult to find.

Similar threads

Engineering Closed Loop Stability Criterion: Find the values for closed loop stability
Replies
2
Views
1K
Comp Sci Blackjack program in javascript
Replies
10
Views
2K
Comp Sci Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?
Replies
32
Views
4K
Comp Sci Validating Braces Placement for Expression Evaluation
Replies
10
Views
2K
How to Create a Flowchart for Calculating GCD?
Replies
27
Views
4K
A How to Derive a Closed Form for a Double Sum with Stochastic Variables?
Replies
5
Views
1K
Proof with recursion and logarithms
Replies
11
Views
2K
Finding the closed form of a recursive LTI system
Replies
4
Views
2K
Engineering Signals in discrete form (scaling, shifting etc.)
Replies
3
Views
1K
Half life from two identical radioactive sources cpm
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top