Solving recurrence relation without initial condition

1.9k Views Asked by At

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

1

There are 1 best solutions below

0
On

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