Confusion with variables when solving a recurrence equation

In summary, the conversation discusses a recurrence equation and how to find its pattern by substituting values. It is shown that the solution is \(T(n) = T(mk) = ma + ((\sum\limits_{i=1}^mi)-1)ck\), which can also be written as \(T(n) = T(mk) = ma + (\frac{m}{2}(m+1)-1)ck\). The goal is to prove that \(T(n) = \Theta(n^{2})\), but there is confusion with the variable names since the leading term is \(m^{2}\) but the goal is to show a leading term of \(n^{2}\).
  • #1
JimmyK
9
0
If I have a recurrence equation of the following form:

$$T(n) = T(km) = a, m = 1$$
$$T(n) = T(km) = T(k) + T(k(m-1)) + cn, m > 1$$

Where a is simply a constant, and k is an integer constant > 0.

Now I begin substituting to find the pattern:
$$T(k) = a$$
$$T(2k) = a + [a] + c2k$$
$$T(2k) = 2a + 2ck$$
$$T(3k) = a + [2a + 2ck] + c3k$$
$$T(3k) = T(3k) = 3a + 5ck$$
$$T(4k) = a + [3a + 5ck] + c4k$$
$$T(4k) = 4a + 9ck$$

So it looks like the solution is:
$$T(n) = T(mk) = ma + ((\sum\limits_{i=1}^mi)-1)ck$$
$$T(n) = T(mk) = ma + (\frac{m}{2}(m+1)-1)ck$$

Now what I want to do is show that $$T(n) = \Theta(n^{2})$$

I can see in my solution that expanding it out, we end with a leading term of: $$m^{2}$$

Now my problem is, I have myself completely confused due to the variable names. T(n) = T(mk) and then the leading term is m^2, but I want to show that T(n) = Theta(n^2) and I don't think I've fully shown that because while m is dependent on n, it's not n. Any explanation of how I go about relating the two would be appreciated.
 
Physics news on Phys.org
  • #2
marobin said:
If I have a recurrence equation of the following form:

$$T(n) = T(km) = a, m = 1$$
$$T(n) = T(km) = T(k) + T(k(m-1)) + cn, m > 1$$

Where a is simply a constant, and k is an integer constant > 0.

Now I begin substituting to find the pattern:
$$T(k) = a$$
$$T(2k) = a + [a] + c2k$$
$$T(2k) = 2a + 2ck$$
$$T(3k) = a + [2a + 2ck] + c3k$$
$$T(3k) = T(3k) = 3a + 5ck$$
$$T(4k) = a + [3a + 5ck] + c4k$$
$$T(4k) = 4a + 9ck$$

So it looks like the solution is:
$$T(n) = T(mk) = ma + ((\sum\limits_{i=1}^mi)-1)ck$$
$$T(n) = T(mk) = ma + (\frac{m}{2}(m+1)-1)ck$$

Now what I want to do is show that $$T(n) = \Theta(n^{2})$$

I can see in my solution that expanding it out, we end with a leading term of: $$m^{2}$$

Now my problem is, I have myself completely confused due to the variable names. T(n) = T(mk) and then the leading term is m^2, but I want to show that T(n) = Theta(n^2) and I don't think I've fully shown that because while m is dependent on n, it's not n. Any explanation of how I go about relating the two would be appreciated.

Hi marobin, :)

It seems that your recurrence relation is in fact a constant sequence since \(T(n) = T(km)=a\mbox{ for }m\geq 1\).

Kind Regards,
Sudharaka.
 

Related to Confusion with variables when solving a recurrence equation

What is a recurrence equation?

A recurrence equation is a mathematical equation that defines a sequence in which each term is calculated based on the previous terms. It is commonly used to model real-life situations where the value of a variable depends on its previous values.

What are variables in a recurrence equation?

Variables in a recurrence equation refer to the unknown quantities that change from one term to another. They represent the values that we want to find in the sequence.

Why is there confusion with variables when solving a recurrence equation?

Confusion with variables can arise when there are multiple variables in a recurrence equation, and it is not clear which variable to solve for. It can also occur when the recurrence equation involves complex functions or expressions.

How do you solve a recurrence equation?

The most common approach to solving a recurrence equation is by using a substitution method, where the equation is repeatedly substituted with its own previous terms until a pattern emerges. Another method is to use generating functions, which transform the recurrence equation into a power series for easier manipulation.

What are some common techniques for simplifying recurrence equations?

Some common techniques for simplifying recurrence equations include using algebraic manipulations, identifying and using recurrence relations, and using boundary conditions to find the initial terms of the sequence. Another useful technique is to convert the recurrence equation into a closed-form solution, which is a non-recursive formula for calculating any term in the sequence directly.

Similar threads

I How to calculate expectation and variance of kernel density estimator?
    • Set Theory, Logic, Probability, Statistics
Replies
9
Views
2K
MHB Solve Recurrence $$T(n)=aT(n-1)+bn^c$$
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Proving Recurrence Relations and Set Elements: T Function and Natural Numbers
    • Set Theory, Logic, Probability, Statistics
Replies
0
Views
1K
MHB Recurrence relation - initial condition
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Proving by Induction: Solving Recurrence Relation
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
I Enumerating a Large Ordinal: Can We Find a Limit to the Continuum?
    • Set Theory, Logic, Probability, Statistics
Replies
27
Views
3K
MHB Solving for specific variable when solving a recurrence equation
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
MHB Solve Recurrence Equation w/2 Base Cases Same Result
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
MHB Upper Bound for Recurrence Relation: $T(n) \leq c n^2 \log^2 n$
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
B An elementary confusion on discrete or continuous variable
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K

Hot Threads

Recent Insights

Back
Top