Problem Detail: This is a question about recurrence relation that contains sum inside the recursion.I am totally stuck. Can anyone help? The problem asks to solve the following recursion $T(n)=frac{1}{n} sum_{i=1}^{n-1}(T(i)+T(n-i))+cn$. The problem also warns that unwrapping is going to be the wrong approach and the right strategy would be to guess the solution and prove it by induction. As the first step it suggests to start with $nT(n) -(n – 1)T(n -1)$.
Asked By : 372
Answered By : vonbrand
The trick here is to get rid of the sum. Note that the sum is up and down, it can be replaced by twice up: $$ begin{align*} (n + 1) T(n + 1) &= 2 sum_{1 le k le n} T(k) + c (n + 1)^2 n T(n) &= 2 sum_{1 le k le n – 1} T(k) + c n^2 (n + 1) T(n + 1) – n T(n) &= 2 T(n) + c (2 n + 1) end{align*} $$ This is a linear, first order, non-homogeneous recurrence. Update: Solution to the recurrence. The recurrence can be written: $$ frac{T(n + 1)}{n + 2} – frac{T(n)}{n + 1} = c frac{2 n + 1}{(n + 1)(n + 2)} $$ This reduces to a sum: $$ begin{align*} frac{T(n)}{n + 1} &= T(0) + c sum_{0 le k le n – 1} frac{2 k + 1}{(k + 1) (k + 2)} &= T(0) + c sum_{0 le k le n – 1} left( frac{3}{k + 2} – frac{1}{k + 1} right) &= T(0) + 3 c (H_{n + 1} – 1 – frac{1}{2}) – c (H_n – 1) &= 2 c H_n + (T(0) – 2 c) + frac{3c}{n + 1} T(n) &= 2 c (n + 1) H_n + (T(0) – frac{7 c}{2}) (n + 1) + 3 c &sim 2 c n ln n end{align*} $$ Here $H_n$ is the $n$-th harmonic number: $$ H_n = sum_{1 le k le n} frac{1}{k} = ln n + gamma + O(1/n) $$ The recurrence $x_{n + 1} – a_n x_n = f_n$ can always be reduced to a telescoping sum at the left side by multiplying by the summing factor: $$ (a_n a_{n – 1} ldots a_0)^{-1} $$ $$ frac{x_{n + 1}}{a_n a_{n – 1} ldots a_0} – frac{x_n}{a_{n – 1} ldots a_0} = frac{f_n}{a_{n + 1} a_n ldots a_0} $$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10625
