2

Any idea on how I can approach this recurrence relation? It is very different to other questions I have encountered where there is only one term of $T(n)$ on the RHS, and the initial condition isn't given as well.

$$T(n)=\frac2n\big(T(0)+T(1)+\ldots+T(n-1)\big)+5n$$

for $n\ge 1$.

Brian M. Scott
  • 616,228

2 Answers2

2

Such recurrences can be solved easily using subtraction of consecutive terms. If the initial conditions are not given, it means that you have to write the solution in terms of the initial terms ($T(0)$ in this problem). Here is the solution:

Given

$$T(n)=\frac2n\big(T(0)+T(1)+\ldots+T(n-1)\big)+5n\qquad\text{ for }n\ge 1\;,$$

so also

$$T(n-1)=\frac2{n-1}\big(T(0)+T(1)+\ldots+T(n-2)\big)+5(n-1)\qquad\text{ for }n\ge 2\;.$$

Rewriting:

$$nT(n)=2\big(T(0)+T(1)+...+T(n-1)\big)+5n^2$$

and

$$(n-1)T(n-1)=2\big(T(0)+T(1)+...+T(n-2)\big)+5(n-1)^2\;.$$

By subtracting the second from the first we get:

$$nT(n) - (n-1)T(n-1) = 2T(n-1) + 5n^2 - 5(n-1)^2\;,$$

or

$$nT(n) = (n+1)T(n-1) + 5(2n-1)$$

Finally, dividing by $n$:

$$T(n) = \frac{(n+1)T(n-1) + 5(2n-1)}n\qquad\text{ for }n\ge 1$$

Now you have only one term of $T$ on the RHS. Solve in terms of $T(0)$.

Brian M. Scott
  • 616,228
Hadi Brais
  • 121
0

Use generating functions. Define $t(z) = \sum_{n \ge 0} T(n) z^n$, shift the recurrence and multiply out to get rid of fractions; multiply by $z^n$, sum over $n \ge 0$ and recognize resulting sums:

$\begin{align*} (n + 1) T(n + 1) &= \sum_{0 \le k \le n} T(k) + 5 (n + 1)^2 \\ \sum_{n \ge 0} (n + 1) T(n + 1) z^n &= \sum_{n \ge 0} z^n \sum_{0 \le k \le n} T(k) + 5 \sum_{n \ge 0} (n + 1)^2 z^n \\ \frac{1}{z} \sum_{n \ge 0} n T(n) z^n &= \sum_{n \ge 0} z^n \sum_{0 \le k \le n} T(k) + 5 \frac{1 + z}{(1 - z)^3} \\ \frac{1}{z} \cdot z t'(z) &= \frac{t(z)}{1 - z} + 5 \frac{1 + z}{(1 - z)^3} \end{align*}$

No need for any initial values here. Solve for $t(z)$:

$\begin{align*} t(z) &= \frac{10}{(1 - z)^2} + 5 \frac{1}{1 - z} \ln \frac{1}{1 - z} + \frac{c}{1 - z} \end{align*}$

Using the generalized binomial theorem and the generating function of the harmonic numbers:

$\begin{align*} (1 - z)^{-m} &= \sum_{n \ge 0} (-1)^n \binom{-m}{n} z^n \\ &= \sum_{n \ge 0} \binom{n + m - 1}{m - 1} z^n \\ H_n &= \sum_{1 \le k \le n} \frac{1}{n} \\ \sum_{n \ge 0} H_n z^n &= \frac{1}{1 - z} \ln \frac{1}{1 - z} \end{align*}$

we see that:

$\begin{align*} T(n) &= [z^n] t(n) \\ &= 10 \binom{n + 2 - 1}{2 - 1} + 5 H_n + c \\ &= 10 n + 5 H_n + c' \end{align*}$

Here $c' = T(0)$.

vonbrand
  • 27,812