# Solving the recurrence relation that contains summation of nth term

$$T(n)=1+2\sum_{i=1}^{n-1}T(i) , \quad n > 1$$

$$T(1)=1$$

any hint or how to solve?

-
Is the sum over $T(i)$ or $(T(i) + 1)$? –  Raphael Nov 21 '10 at 10:46
sum is over T(i) only. –  Eric Nov 21 '10 at 11:03
I rearranged your expression to be clearer. –  Ｊ. Ｍ. Nov 21 '10 at 11:46

Hint: Consider $T(n) - T(n-1)$ in case the $1$ is outside of the sum.

Consider $\frac{T(n)}{n-1} - \frac{T(n-1)}{n-2}$ if you sum also over the $1$.

-
Or maybe $T(n)-2T(n-1)$? –  Jonas Meyer Nov 21 '10 at 10:48
Works out nicely without the additional factor $2$ (assuming we do not sum over $1$, too). For more complex recurrences with history, you have to adapt this ansatz, obviously. –  Raphael Nov 21 '10 at 10:53

HINT $\quad$ Solve it the same way you would solve $\rm\ f(x)\ =\ 1 + 2 \int f(x)\ dx\$ but instead of $\rm\ d/dx\$ apply $\rm\ \Delta_n\: f(n) = f(n+1) - f(n)\$ to eliminate (invert) the $\rm\: \sum = \Delta^{-1}\:,\$ i.e. employ the the fundamental theorem of difference calculus.

-

You can also use generating functions.

if $$\displaystyle f(x) = \sum_{n=1}^{\infty} T(n) x^n$$

Then

$$\displaystyle \frac{2f(x)}{1-x} = \sum_{n=1}^{\infty} (2\sum_{k=1}^{n} T(k)) x^n$$

i.e.

$$\displaystyle \frac{2f(x)}{1-x} = \sum_{n=1}^{\infty} (3T(n) - 1) x^n = 3f(x) - \frac{1}{1-x} + 1$$

This gives us

$$\displaystyle f(x) = \frac{x}{1-3x} = \sum_{n=1}^{\infty} 3^{n-1} x^n$$

Hence

$$\displaystyle T(n) = 3^{n-1}$$

-

Using a spreadsheet, I note that $T(n)=3^{(n-1)}$ This is easily verified by induction.

$T(1)=1=3^0$.
Then if it is true up to $n$, $$T(n+1)=1+2\sum_{i=0}^{n-1}3^i=1+2\frac{3^n-1}{3-1}$$

-