1

Suppose that $T(0) = 1$ and define $T(n)$ as follows $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j) $$ Show that $T(n) = 2^n$.

If I substitute values, I can see that the sequence goes like $1, 2, 4, 8, \dotsc$, that is that they are powers of $2$.

But how do I mathematically prove it? Any hints should be good too.

Mike Pierce
  • 18,938
Senthil Kumaran
  • 235

3 Answers3

2

HINT: Mathematical induction principle plus $1+2\dots+2^n=2^{n+1}-1$.

Kola B.
  • 2,465
2

We have $$T(n+1) = 1+\sum_{k=1}^n T(k) = \left(1 + \sum_{k=1}^{n-1} T(k) \right) + T(n) = T(n) + T(n) = 2T(n)$$ Hence, we have $$T(n+1) = 2T(n) = 2^2 T(n-1) = 2^3 T(n-2) = \cdots = 2^n T(1) = 2^{n+1} T(0) = 2^{n+1}$$

Adhvaitha
  • 20,259
1

You can use strong induction on $n$. For the inductive step, you assume $T(m)=2^m$ for every $m\leq n$. For $T(n+1)$, from the definition, you have: $$ T(n+1)=1+\sum_{j=0}^{n}T(j)=1+(1+2^1+\ldots+2^n)=1+\frac{1-2^{n+1}}{1-2}=2^{n+1} $$

Vinícius Novelli
  • 2,487
  • Thank you. Btw, is the sum of powers of 2 reduction, is something that needs to be kept in memory or can be derived too? – Senthil Kumaran Apr 25 '15 at 01:08
  • 1
    It can be derived. Say you have $1+2^{1}+\ldots+2^{n}=S$. Then, $1+2(1+2^{1}+\ldots+2^{n-1})=S$, but this product in the middle is $S-2^{n}$. Then, substituting it, you have $1+2(S-2^{n})=S$, so isolate $S$ and you get $S=2^{n+1}-1 = (1-2^{n+1})/(1-2)$ – Vinícius Novelli Apr 25 '15 at 01:12