Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


any hint or how to solve?

share|cite|improve this question

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

share|cite|improve this answer
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$$


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


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


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

share|cite|improve this answer

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.

share|cite|improve this answer

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

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

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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