3
$\begingroup$

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

1 Answer 1

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$
2
  • $\begingroup$ Thanks a lot for the insight. Do you have any idea what kind of function would fit into this recurrence ? $\endgroup$
    – 372
    Commented Mar 20, 2013 at 15:37
  • $\begingroup$ Please consider not reinforcing unwanted behaviour. $\endgroup$
    – Raphael
    Commented Mar 20, 2013 at 20:50

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