Solving the recurrence relation that contains summation of nth term

Question

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

$$T(1)=1$$

any hint or how to solve?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.

Answer 6

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