How to get the closed form of this recurrence?

Click For Summary
SUMMARY

The recurrence relation T(k, n) = T(k, n-1) + (k-2)(n-1) + 1 can be solved using repeated substitution to derive a closed form. The pattern identified through substitutions leads to T(k, n) = n + c + (k-2) * 1 * 2 * ... * (n-1), where c is the boundary condition T(k, 0). The sequence of coefficients follows the triangular numbers, specifically 1, 3, 6, 10, which can be expressed in terms of the number of substitutions made.

PREREQUISITES
  • Understanding of recurrence relations
  • Familiarity with triangular numbers
  • Basic knowledge of mathematical induction
  • Experience with algebraic manipulation
NEXT STEPS
  • Study the properties of triangular numbers and their applications in combinatorial problems
  • Learn about solving recurrence relations using characteristic equations
  • Explore mathematical induction techniques for proving closed forms
  • Investigate advanced topics in combinatorial mathematics
USEFUL FOR

Mathematics students, educators, and anyone involved in algorithm analysis or combinatorial problem-solving will benefit from this discussion.

zeion
Messages
455
Reaction score
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
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.
 

Similar threads

Engineering Enumeration vs Bisection Strategy
  • · Replies 2 ·
Replies
2
Views
1K
Engineering Have I solved this structural engineering equation correctly?
  • · Replies 1 ·
Replies
1
Views
1K
PLL - How to find all the gains of a PI corrector and fix Ki ? MATLAB
  • · Replies 2 ·
Replies
2
Views
2K
Engineering Closed Loop Stability Criterion: Find the values for closed loop stability
  • · Replies 2 ·
Replies
2
Views
2K
Comp Sci Blackjack program in javascript
  • · Replies 10 ·
Replies
10
Views
3K
Comp Sci Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?
  • · Replies 32 ·
2
Replies
32
Views
5K
Comp Sci Validating Braces Placement for Expression Evaluation
  • · Replies 10 ·
Replies
10
Views
2K
How to Create a Flowchart for Calculating GCD?
  • · Replies 27 ·
Replies
27
Views
5K
Graduate How to Derive a Closed Form for a Double Sum with Stochastic Variables?
  • · Replies 5 ·
Replies
5
Views
2K
Finding the closed form of a recursive LTI system
  • · Replies 4 ·
Replies
4
Views
2K