3
$\begingroup$

This question already has an answer here:

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

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Did you follow the suggestion? Where did you get stuck? $\endgroup$ – Yuval Filmus Mar 19 '13 at 22:01
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 19 '13 at 22:01
  • $\begingroup$ Closing as duplicate as the reference question has an answer for this problem. $\endgroup$ – Raphael Mar 20 '13 at 11:55
2
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.