Explicit solution to a recurrence relation

Question

How would one reduce the following recurrence relation to an explicit formula $T(n)$?

$$n * T(n)=c + (n + 1) * T(n - 1)$$ $$T(1) = 0$$

Answer 1

Another way to do it:

$nT(n) = c + (n+1)T(n-1)$

Define $T(n) = (n+1)F(n)$.

$n(n+1)F(n) = c + (n+1)(n)F(n-1)$

$F(n) = \frac{c}{n(n+1)} + F(n-1)$

Therefore $F(n) = c\sum_{k=2}^{n} \frac{1}{k(k+1)} = \frac{c(n-1)}{2(n+1)}$

Unrolling, $T(n) = (n+1)F(n) = \frac{n+1}{1} \cdot \frac{c(n-1)}{2(n+1)} = \frac{c(n-1)}{2}$

Answer 2

The first few cases (n=2,3,4,5) suggest a pattern which you can then prove by induction.

Alternatively, assume there is a simple solution of the form T(n) = an + b for constants a and b. T(1)=0 tells you that b=-a so T(n) = a(n-1). Then use the recurrence relation to find a.

Answer 3

Trying to compute explicitly for small $n$ makes us conjecture $T(n) = \frac{(n-1)c}{2}$

• Base case : Trivial.
• Inductive case, assuming true up to $n$. $$(n+1)T(n+1) = c + (n+2)\cdot \frac{(n-1)c}{2} \Longleftrightarrow T(n+1) = \frac{c}{n+1} + (n+2)\cdot \frac{(n-1)c}{2(n+1)} \overset{(*)}{=} \frac{cn}{2} $$ $(*)$ Skipping the annoying algebra...