# How to get the closed form of this recurrence?

• zeion
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).
zeion

## 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

## 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.

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)

Sorry I wrote the expression wrong; but I got the answer I think, thanks.

## 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.

Replies
2
Views
1K
Replies
10
Views
2K
Replies
32
Views
4K
Replies
10
Views
2K
Replies
27
Views
4K
Replies
5
Views
1K
Replies
11
Views
2K
Replies
4
Views
2K
Replies
3
Views
1K
Replies
1
Views
1K