How to solve a recurrence relation with full history $ T(n) = n + \sum_{i=1}^{n-1} \frac{2T(i)}{3i}$?

81 Views Asked by At

I have to solve a recurrence relation with full history given as: $$ T(n) = n + \sum_{i=1}^{n-1} \frac{2T(i)}{3i} \tag{1}$$

I tried to solve it using the method given here and here and expanded it like this: $$ T(n+1) = (n+1) + \sum_{i=1}^{n} \frac{2T(i)}{3i} \tag{2}$$

Subtracting $(1)$ from $(2)$ gives: $$ T(n+1) - T(n) = 1 + \frac{2T(n)}{3n} $$

which can be simplified as $$T(n+1) = 1 + T(n)\left(1 + \frac{2}{3n}\right)$$

I am lost after that. Please help.

1

There are 1 best solutions below

2
On BEST ANSWER

(Some result from WolframAlpha, acknowledged later in this answer)

Inspired by the closed form given by WolframAlpha, from the given recurrence and the particular solution $T(n) = 3n$ mentioned by @Sil:

$$\begin{align*} && T(n+1) &= 1 + T(n) \left(1+\frac{2}{3n}\right)\\ &(-)& 3(n+1) &= 1 + 3n \left(1+\frac{2}{3n}\right)\\ &\implies& T(n+1) - 3(n+1) &= \left[T(n) - 3n\right] \left(1+\frac{2}{3n}\right)\\ \end{align*}$$

So for the $T(n)$ term,

$$\begin{align*} T(n) - 3n &= \left[T(n-1) - 3(n-1)\right] \left(1+\frac{2}{3(n-1)}\right)\\ &\vdots\\ &= \left[T(1) - 3\cdot1\right]\prod_{i=1}^{n-1}\left(1+\frac{2}{3i}\right)\\ \end{align*}$$

I assume that, according to $(1)$ in the question,

$$\begin{align*} T(1) &= 1+(\text{Empty sum}) = 1\\ T(n) &= 3n - 2 \prod_{i=1}^{n-1}\left(1+\frac{2}{3i}\right) \end{align*}$$


Based on the last recurrence, WolframAlpha gives a closed form in terms of some fractional $\Gamma$:

$$T(n) = 3n - \frac{2\Gamma\left(n+\frac23\right)}{\Gamma\left(\frac53\right)\Gamma\left(n\right)}$$

Using generalisations of binomial coefficient $\binom xy$ with fractional $x$ and using the gamma function,

$$\begin{align*} T(n) &= 3n - \frac{2\Gamma\left(n+\frac23\right)}{\Gamma\left(\frac53\right)\Gamma\left(n\right)}\\ &= 3n - 2\binom{n-\frac13}{n-1}\\ &= 3n - 2\cdot\frac{\left(n-\frac13\right)\left(n-\frac43\right)\left(n-\frac73\right)\cdots \frac53}{(n-1)(n-2)(n-3)\cdots1}\\ &= 3n - 2 \prod_{i=1}^{n-1}\left(1+\frac{2}{3i}\right) \end{align*}$$