1

I'm trying to find a simpler form for $\sum_{i=0}^{n} 2^x$ this is what I have so far:

$\sum_{i=0}^{n} 2^i = 1 +2(1+2(1+... + 2(1 + 2)))$

And from this I got the following recurrence formula $x_n=1+2x_{n-1} => x_n-2x_{x-1}-1=0$. Now I'm assuming $x_n$ has some exponential form $b^n$ and I'll further add a offset $a$ so that I can get a nice quadratic equation so $x_n$ should be $b^n+a$

Now I have: $b^n-2b^{n-1}-a-1=0 => b^{n-2}(b^2-2b)=a+1$ and now im using $a=-1$ so I can get a quadratic equation with solutions $b=2,0$ so now my sum should be $2^n -1$ which is incorrect.

Can someone point to me the mistakes I have made and some correction would be very much appreciated. Thanks.

oren revenge
  • 566
  • 4
  • 13
  • You need to assume it is of the form $cb^n + a$. – Mike Earnest Aug 17 '18 at 14:30
  • Did you mean $2^i$ as the summand? – lulu Aug 17 '18 at 14:31
  • If so, then if $x_n$ denotes your sum we have $2x_n=x_n-1+2^{n+1}\implies x_n=2^{n+1}-1$. – lulu Aug 17 '18 at 14:33
  • 1
    The mistake you make here is in the exponential form. You are right in that $x_n$ grows exponentially, but it still could have a multiplicative factor. Hence, including the "offset", you get $x_n=c \times b^n + a$ for some constants $a,b,c$. In this particular case it happens to be that $c=2$ and not 1 as you implicitly assumed in your derivation. – Ronald Blaak Aug 17 '18 at 15:07
  • is there any method to find $c$? – oren revenge Aug 17 '18 at 15:14
  • Sure, you only need 3 equations to find $a,b,c$. The simplest way of doing this is to consider the cases $n=0,1,2$. This gives $c + a=0$,$c b + a=3$, and $c b^2+a=7$. Of course any other three values of $n$ could have been chosen as well. – Ronald Blaak Aug 17 '18 at 15:27

2 Answers2

2

As Ronald Blaak explained well in the comments, you need to assume $x_n = cb^n + a$. The equation you had then becomes $$ cb^{n-1}(b-2) = a+1 $$ This implies that $b=2$, which further implies $a=-1$ as before. Therefore, you know $x_n=c2^n -1$. To solve for $c$, use the fact that you know $x_0=1$.

Mike Earnest
  • 75,930
0

$$1+1+2+4+8+16 \\=2+2+4+8+16 \\=4+4+8+16 \\=8+8+16 \\=16+16 \\=32$$

and

$$1+2+4+8+16=32-1.$$

The generalization is obvious.