# Recurrence relation with sum [duplicate]

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

## marked as duplicate by Raphael♦Mar 20 '13 at 11:54

• Did you follow the suggestion? Where did you get stuck? – Yuval Filmus Mar 19 '13 at 22:01
• As an aside, there is a general method to solve recurrence relations of this form, as long as they have an "explicit" closed-form solution. Try your favourite computer algebra system. – Yuval Filmus Mar 19 '13 at 22:01
• Closing as duplicate as the reference question has an answer for this problem. – Raphael Mar 20 '13 at 11:55

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