# 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?

-

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
I just used this technique with a different recurrence relation, thanks. It is simple and good (when it works). – Erel Segal-Halevi Sep 17 '14 at 10:26

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

-

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.

-

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

-

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.

-

Take a look at the first few terms:

$$T(1)=1, T(2)=3, T(3)=9$$

and conclude that it is a geometric series. So, $$\sum_{i=1}^{n-1}=a(r^m-1)/(r-1)=\frac{3^{n-1}-1}{2}$$

Now, $$\boxed{T(n)}=1+2\sum_{i=1}^{n-1}=1+3^{n-1}-1 = \boxed{3^{n-1}}$$

-