Solving Recurrence Relation: t(m,n) Formula

In summary, the conversation discusses the process of solving a recurrence relation and provides an example using recursion. The conversation also mentions different techniques for solving recurrence relations, such as using Z-transforms and Generating Functions. However, the individual seeking help ultimately finds the general expression they were looking for.
  • #1
heman
361
0
How do we actually solve the Recurrence relation...is there any procedure...
Suppose i want to solve:
t(m,n) = n.t(m-1,n) + t(m-1,n-1)
where t(1,*) = t(*,1) = 1.
How to do it?
 
Mathematics news on Phys.org
  • #2
i think the question is clear..
 
  • #3
heman said:
How do we actually solve the Recurrence relation...is there any procedure...
Suppose i want to solve:
t(m,n) = n.t(m-1,n) + t(m-1,n-1)
where t(1,*) = t(*,1) = 1.
How to do it?

Recurrence relations are solved via recursion. For example, t(3,2) is
t(3,2) = 2*t(2,2) + t(3,1) = 3*t(2,2) + 1
Now solve for t(2,2):
t(2,2) = 2*t(1,2) + t(1,1) = 2*1 + 1 = 3
Now plug this result into the equation for t(3,2):
t(3,2) = 2*t(2,2) + 1 = 2*3+1 = 7

This method will work for any positive integer values m,n so long as you have enough scratch paper (or computer memory) to record the placeholders. Modern computer languages do this for free:

function [r] = t(m,n)
if (m == 1) || (n == 1)
r = 1;
else
r = n*t(m-1,n) + t(m-1,n-1);
end
 
  • #4
Here are some values to try to discover a trend
Code:
1	1	1	1	1	1	1	1	1	1	1	1
1	3	4	5	6	7	8	9	10	11	12	13
1	7	15	24	35	48	63	80	99	120	143	168
1	15	52	111	199	323	489	703	971	1299	1693	2159
1	31	171	496	1106	2137	3746	6113	9442	13961	19922	27601
1	63	544	2155	6026	13928	28359	52650	91091	149052	233103	351134
1	127	1695	9164	32285	89594	212441	449559	872469	1581611	2713185	4446711
1	255	5212	38351	170589	569849	1576681	3808913	8301780	16688579	31426646	56073717
1	511	15891	158616	891296	3589683	11606616	32047985	78524933	175187570	362381685	704311250
1	1023	48184	650355	4615096	22429394	84835995	267990496	738772382	1830400633	4161386105	8814116685
1	2047	145575	2649604	23725835	139191460	616281359	2228759963	6916941934	19042778712	47605647788	1.09931E+11
1	4095	438772	10743991	121278779	858874595	4453160973	18446361063	64481237369	1.97345E+11	5.42705E+11	1.36678E+12
1	8191	1320411	43414736	617137886	5274526349	32031001406	1.52024E+11	5.98777E+11	2.03793E+12	6.1671E+12	1.6944E+13
1	16383	3969424	174979355	3129104166	32264295980	2.29492E+11	1.24822E+12	5.54102E+12	2.09781E+13	6.9876E+13	2.09495E+14
1	32767	11924655	703886844	15820500185	1.96715E+11	1.63871E+12	1.02153E+13	5.11174E+13	2.15322E+14	7.89614E+14	2.58382E+15
1	65535	35806732	2827472031	79806387769	1.19611E+12	1.16677E+13	8.33609E+13	4.70272E+14	2.20433E+15	8.90108E+15	3.17954E+16
 
Last edited:
  • #5
heman,
You have picked up quite a nasty recurrence relation as an example.

Try your hand at some simple recurrence relations like,
1. T(n) = T(n-1) + 1, T(0) = 1
2. T(n) = T(n-1) + n, T(0) = 0
3. T(n) = n*T(n-1), T(0) = 1

Try to solve these in as many ways as you can think of. Its pretty hard of finding several ways to solve recurrence relations. But it should help you notice patterns.

There are some techniques involving Z-transforms, Generating Functions etc. but really these are the extremes.

-- AI
 
  • #6
thanks guys but this is an some kind of algorithmic programme kind of thing...i was looking for the general expression but i have got that now...

Thanks all of you for your kindness
 

1. What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence of values based on the previous terms in the sequence. It is often used to describe the relationship between two or more variables in a mathematical model.

2. How do you solve a recurrence relation?

To solve a recurrence relation, you need to find a formula that describes the relationship between the terms in the sequence. This can be done by using various techniques such as substitution, iteration, or the master theorem.

3. What is the purpose of solving a recurrence relation?

The purpose of solving a recurrence relation is to find a closed-form solution that can be used to calculate any term in the sequence without having to go through all the previous terms. This can save time and resources when dealing with large or complicated sequences.

4. What is the difference between a linear and a non-linear recurrence relation?

A linear recurrence relation is one in which the next term in the sequence can be calculated by a simple linear combination of the previous terms. A non-linear recurrence relation, on the other hand, involves more complex operations such as multiplication, division, or exponentiation.

5. How do you determine the complexity of a recurrence relation?

The complexity of a recurrence relation can be determined by analyzing the growth rate of the sequence. This can be done by finding the asymptotic behavior of the sequence using techniques such as big-O notation or by solving the recurrence relation using various methods and analyzing the solution.

Similar threads

  • General Math
Replies
12
Views
2K
Replies
3
Views
981
Replies
3
Views
1K
  • General Math
Replies
11
Views
1K
Replies
13
Views
1K
Replies
6
Views
944
Replies
2
Views
987
  • Linear and Abstract Algebra
Replies
8
Views
908
  • General Math
Replies
4
Views
999
Replies
1
Views
2K
Back
Top