Problem: Consider the following recurrences defining function, $$f_2(n) = \lbrace 1\ if\ n = 0;\ 1 + \sum_{i=0}^{n-1} f_2(i)\ if\ n > 0\rbrace, f_2: N \to N $$
Prove $f_2(n) = 2^n$
My attempt: Proof by strong induction. so,
Base Cases: $$n = 0 \Rightarrow f_2(0) = 1 = 2^0,\ f_2(0)\ holds\\n = 1 \Rightarrow f_2(1) = 1 + \sum_{i=0}^{n-1} f_2(i) = 2 = 2^1,\ f_2(1)\ holds$$
Inductive step: let $n\ge2$. suppose $$f_2(j) = 2^j$$ whenever $0\le j < n$ (IH)
WTP: $f_2(n) = 2^n$, so
$$f_2(n) = 1 + \sum_{i=0}^{n-1} f_2(i)$$ $$= 1 + \sum_{i=0}^{n-1} 2^i$$ by (IH) $$= 1 + (2^0 + 2^1 + ... + 2^{n-1})$$
The next part is where I don't quite get what to do next. I know I have to somehow simplify that to $2^n$ but I have no idea how to do that. If anyone can help me with that that would be really appreciated.
Either you know the result on geometric series saying that $\sum\limits_{i=0}^{n} a^i =\frac{1-a^{n+1}}{1-a}$ which concludes your proof.
Or, another way is to notice that $$f_2(n)=1+\sum_{i=0}^{n-1}f_2(i)=\left(1+\sum_{i=0}^{n-2}f_2(i)\right)+f_2(n-1)=f_2(n-1)+f_2(n-1).$$ And you should be able to conclude from here.