Help with discrete math proof I'm having trouble with the following:
$\ a_1=1$ and $a_n=1+\sum_{i=1}^{n-1} a_i$ for $n>1$
How should I go about proving the below? Any hints?
$a_n = 2^{n-1}$

Induction is the obvious choice in these kinds of problems.


*

*For $n=1$, the statement is obviously true.

*Now, we should prove the statement for $n+1$ by assuming it is true for all values $k\leq n$. That is, we know that $a_k = 2^{k-1}$ for all values $k\leq n$. Then, we have $$a_{n+1} =1 + \sum_{i=1}^n a_i = 1 + \sum_{i=1}^n 2^{i-1}$$
Can you now prove that $a_{n+1} = 2^n$?

