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(0)=1 \\ T(n) = 1 + \sum_{j=0}^{n-1}T(j) \\ $

Show that $T(n) = 2^n$.

I know how to prove this by induction, but I would like to know how to show this using first principles.

Edit: The way I want to solve this problem is manipulate $T(n)$ in such a way that it ends up as $2^n$.

share|improve this question
3  
Induction is a first principle... It forms part of the standard axiomatization of the integers. –  Shakespeare Aug 9 at 20:42
1  
Okay, but I would like to show this without the prior knowledge that T(n) = 2^n. –  user168880 Aug 9 at 20:44
4  
In such a case, you can compute the first few terms pretty easily, which suggests a pattern. There is nothing wrong with doing that, that is a large part of mathematics. –  Simon Rose Aug 9 at 20:45

5 Answers 5

up vote 10 down vote accepted

Clearly, $$T(n+1)=1+T(n)+\sum_{j=0}^{n-1}T(j)=T(n)+T(n)=2T(n)$$ So, $(T(n))_n$ is a geometric progression with common ratio $2$ and starts at $1$. That is $T(n)=2^n$.

share|improve this answer

The ugliest piece in the definition $T_n = 1 + \sum\limits_{k=0}^{n-1} T_{k}$ is the sum. One should attempt to get rid of it first. We have $$T_{n+1} - T_n = \left( 1 + \sum_{k=0}^n T_k \right) - \left( 1 + \sum_{k=0}^{n-1}T_k \right) = T_n \quad\implies\quad T_{n+1} = 2T_n$$

The rest is obvious.

This is one common tactic to attack an problem. You identify the ugliest, hardest piece and attempt to get rid of it. If you can repeat this procedure and get rid of all the nasties, what should/could do next is usually obvious.

share|improve this answer

This is just the brute force method. It is obviously an overkill in this case, but I think it is worth to learn it. Put: $$ f(x)=\sum_{j=0}^{+\infty}T(j)\, x^j. $$ The recurrence relation then gives $f(0)=1$ and: $$\frac{f(x)}{1-x}=\sum_{j=0}^{+\infty}\left(\sum_{k\leq j}T(k)\right)x_j=\sum_{j=0}^{+\infty}(2T(j)-1)\,x^j = 2f(x)-\frac{1}{1-x},$$ hence: $$f(x)=\frac{1}{1-2x}=\sum_{j=0}^{+\infty}2^j\,x^j,$$ from which: $$T(j)=2^j$$ as wanted.

share|improve this answer

You could perhaps show that $2^n$ satisfies the same recurrence relation and initial condition, I suppose, by using the fact that $$ \frac{r^n - 1}{r-1} = r^{n-1} + r^{n-2} + \cdots + r + 1 $$

share|improve this answer

the second equality implies T[n+1] - T[n] = T[n] so T[n+1] = 2T[n]. Look for solutions of the form T[n] = c q^n. Substitution yields q = 2. The initial condition T[0] = 1 yields c = 1.

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.