# Proof that for a series $x_1 = 1,$ $x_{n+1} = \sum_{i=1}^n x_i$ for all $n>1$ $x_n = 2^{n-2}$

I am looking for a proof ( I think by induction) that for a series $x_1 = 1,$ $x_{n+1} = \sum_{i=1}^n x_i$ for all $n>1$ then $x_n = 2^{n-2}$ So, the series goes $1,1,2,4,8,16,32$ and onward.

I've tried many paths, all with induction, but can't seem to find what I'm supposed to do. My first step was the base case $n=2$ so $p(2)$. For that, $x_2 = x_{1+1} = x_1 = 1$ and $2^{2-2} = 1$ so $p(2)$ is true.

Thank you

• What is the first part of the induction proof? There is a standard first step. – Thomas Andrews Nov 16 '17 at 20:39
• Well if you're referring to the first step, if p(k) is my statement, then I would do p(2). $x_2 = x_{1+1} = x_1 = 1$ and $2^{2-2} = 1$ therefore p(2) is true. – Antoine Nov 16 '17 at 20:50
• Show your work in the question, not in comments. – Thomas Andrews Nov 16 '17 at 20:52
• Oh sorry, added it. – Antoine Nov 16 '17 at 21:07
• Hint: $$1+1+2+2^2+\cdots+2^{k-1}+2^k=2^{k+1}$$ – Did Nov 16 '17 at 21:10

$x_{n+1} = \sum_{i=1}^n x_i = \sum_{i=1}^{n-1} x_i+x_n =x_n+x_n =2x_n$.