Take the 2-minute tour ×
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.

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

$$T(1)=1$$

any hint or how to solve?

share|improve this question

5 Answers 5

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|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 at 10:26

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|improve this answer

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

share|improve this answer

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

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

Your Answer

 
discard

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.