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.
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}$.