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

  • 1
    $\begingroup$ What is the first part of the induction proof? There is a standard first step. $\endgroup$ – Thomas Andrews Nov 16 '17 at 20:39
  • $\begingroup$ 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. $\endgroup$ – Antoine Nov 16 '17 at 20:50
  • 1
    $\begingroup$ Show your work in the question, not in comments. $\endgroup$ – Thomas Andrews Nov 16 '17 at 20:52
  • $\begingroup$ Oh sorry, added it. $\endgroup$ – Antoine Nov 16 '17 at 21:07
  • $\begingroup$ Hint: $$1+1+2+2^2+\cdots+2^{k-1}+2^k=2^{k+1}$$ $\endgroup$ – 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 $.

  • $\begingroup$ @Ahmed S. Attaalla: I don't see why you deleted your answer. Just because it was similar to mine is no reason, as far as I am concerned. It looks like you derived it independently. $\endgroup$ – marty cohen Nov 16 '17 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.