# 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
add comment

## 5 Answers

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
add comment

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.

-
add comment

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

-
add comment

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

-
add comment

Take a look at Kelley and Peterson's textbook [1]. They provide a very good discussion of difference equations in this text. I believe you can relate the information in this book to answer your question.

You will find further discussion regarding the answers posted here by Moron and Ross Millikan.

Let me know if you still cannot figure it out!

[1] Kelley, W. & Peterson, A. (2001). Difference Equations: An Introduction with Applications (2nd Ed.). San Diego, CA: Academic Press.

-
add comment