Solving Recurrence Relation: t(m,n) Formula

[heman]

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?

 

[heman]

i think the question is clear..

 

[D H]

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

 

[0rthodontist]

Here are some values to try to discover a trend

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

 

[TenaliRaman]

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

 

[heman]

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