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

• Did you follow the suggestion? Where did you get stuck? 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. 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.

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

• Thanks a lot for the insight. Do you have any idea what kind of function would fit into this recurrence ?
– 372
Mar 20 '13 at 15:37
• Please consider not reinforcing unwanted behaviour.
– Raphael
Mar 20 '13 at 20:50