# Recurrence Relation

1. Feb 23, 2006

### 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?

2. Feb 23, 2006

### heman

i think the question is clear..

3. Feb 23, 2006

### D H

Staff Emeritus
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. Feb 23, 2006

### 0rthodontist

Here are some values to try to discover a trend
Code (Text):

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: Feb 23, 2006
5. Feb 23, 2006

### 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

6. Feb 24, 2006

### 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