Recurrance

[vaibhav]

I am stuck on this question from cormen(unsolved of course) and need your help

p(n)={1 ifn=1
{summation of k=1 to n-1 P(k)P(n-k) ifn>=2

Prove that solution of this recurrance is omega(2^n) by substitution.

[SilentStrike]

I think your problem is that it's not.

Experimentally...

i, p(i), p(i)/p(i-1)

>>> for i in range(2, 40): print i, p(i), float(p(i)) / p(i - 1)
... 
2 1 1.0
3 2 2.0
4 5 2.5
5 14 2.8
6 42 3.0
7 132 3.14285714286
8 429 3.25
9 1430 3.33333333333
10 4862 3.4
11 16796 3.45454545455
12 58786 3.5
13 208012 3.53846153846
14 742900 3.57142857143
15 2674440 3.6
16 9694845 3.625
17 35357670 3.64705882353
18 129644790 3.66666666667
19 477638700 3.68421052632
20 1767263190 3.7
21 6564120420 3.71428571429
22 24466267020 3.72727272727
23 91482563640 3.73913043478
24 343059613650 3.75
25 1289904147324 3.76
26 4861946401452 3.76923076923
27 18367353072152 3.77777777778
28 69533550916004 3.78571428571
29 263747951750360 3.79310344828
30 1002242216651368 3.8
31 3814986502092304 3.8064516129
32 14544636039226909 3.8125
33 55534064877048198 3.81818181818
34 212336130412243110 3.82352941176
35 812944042149730764 3.82857142857
36 3116285494907301262 3.83333333333
37 11959798385860453492 3.83783783784
38 45950804324621742364 3.84210526316
39 176733862787006701400 3.84615384615

Looks like omega(4^n) to me.

>>> print float(p(500))/ p(499)

3.988