Recurrence Relation

[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