The recursion is $T_n=\frac{b}{n+b}+T_{n-1}$ and $T_1=1$. When expanding the recursion we have $T_n=\frac{b}{b+n-1}+\frac{b}{b+n-2}+...+\frac{b}{b+1}+1$. However, the solution shows $T_n=b({\psi _0}(b + n) - {\psi _0}(b))$ where ${\psi _0}$ is the digamma function. The solution indicates ${\psi _0}(b + n) - {\psi _0}(b)=\frac{1}{b+n-1}+\frac{1}{b+n-2}+...+\frac{1}{b+1}+\frac{1}{b}$.

For instance, when $n=4,b=1$, ${\psi _0}(5) - {\psi _0}(1) = \frac{{25}}{{12}}$, and $\frac{1}{b+n-1}+\frac{1}{b+n-2}+...+\frac{1}{b+1}+\frac{1}{b}=\frac{25}{12}$ as well, so I believe the solution is correct.

I am not familiar with digamma function so I checked Wikipedia, but I still cannot understand this equation. Hope someone can help show why the equation ${\psi _0}(b + n) - {\psi _0}(b)=\frac{1}{b+n-1}+\frac{1}{b+n-2}+...+\frac{1}{b+1}+\frac{1}{b}$ holds. Thank you.

The restriction is that $n$ is positive integer and $b>0$.

  • $\begingroup$ Which equation in particular would you like demonstrated? $\endgroup$ – Chappers Mar 31 '15 at 20:12
  • $\begingroup$ @Chappers Thanks for your reply. I have refined the question. $\endgroup$ – Tony Mar 31 '15 at 20:14

Right, the definition of the Gamma function is $$ \Gamma(z) = \int_0^{\infty} x^{z-1}e^{-x} \, dx, $$ for $z>0$. It is easy to show, using integration by parts, that $$ \Gamma(z+1) = z \Gamma(z), \tag{1} $$ and $\Gamma(1)=1$ is also easy (it follows that $\Gamma(n)=(n-1)!$ for $n$ a positive integer, but I'm not going to need that.)

The digamma function (unhelpfully written $\psi(z)$) is defined as $$ \psi(z) = \frac{\Gamma'(z)}{\Gamma(z)} = \frac{d}{dz} \log{\Gamma(z)}. $$ Now, taking logarithms of both sides of (1) and differentiating, we find that $$ \log{\Gamma(z+1)} = \log{z}+\log{\Gamma(z)}\\ \psi(z+1) = \frac{1}{z} + \psi(z). $$ Therefore, $\psi(z+1)-\psi(z) = \frac{1}{z}$, and we can iterate this to get $$ \psi(z+2)-\psi(z) = (\psi(z+2)-\psi(z+1))+(\psi(z+1)-\psi(z)) = \frac{1}{z+1} + \frac{1}{z}, $$ and doing the same trick to $\psi(b+n)-\psi(b)$, we get to $$ \psi(b+n)-\psi(b) = \frac{1}{b+n-1} + \dotsb + \frac{1}{b+1} + \frac{1}{b}. $$

Say if there's a step you'd like more detail on.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.