1
$\begingroup$

I have to find a close form of the following Recurrence Relations.

$P_{t+1} = P_t - \frac{p}{t}P_t$

With $P_{i+1}=\frac{p}{i}$, for some $i < t$.

I tried the unfolding method on Knuth, but it leads to me nowhere. This is not a homework problem, but came as a research problem I am trying to figure out. Can you please give me any idea how to solve it or at least provide me with tight bounds.

I am also interested in solving complex recurrence relations like this.

$\endgroup$

1 Answer 1

3
$\begingroup$

You have: $$ P_{t+1}=\left(1-\frac{p}{t}\right)P_t $$ hence: $$ P_{n+1} = P_1\cdot \prod_{j=1}^{n}\left(1-\frac{p}{j}\right).$$ Since $(1-p/j)\approx e^{-p/j}$, $P_n$ behaves like $\frac{1}{n^p}$.

$\endgroup$
1
  • $\begingroup$ Thanks you very much! I was expecting the result similar to this because the recurrence relation came from analyzing a power-law degree distribution. $\endgroup$
    – max
    Sep 25, 2014 at 17:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .