1
$\begingroup$

I'm reading Book of Proof for a refresher on mathematical proofs and came across this problem:

If $n \in \mathbb{N}$, then $2^0 + 2^1 + 2^2 + 2^3 + \dots + 2^n = 2^{n+1} - 1$.

I know there have been similar questions on the site asking to prove this problem by induction, but I don't want to use induction because the book has not yet introduced it (even though I'm familiar, but not comfortable, with induction proofs). In fact, my book's answer key uses a direct proof:

Proof. We use direct proof. Suppose $n \in \mathbb{N}$. Let $S$ be the number:

$S = 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + \dots + 2^n$ (1)

In what follows, we will solve for $S$ and show $S = 2^{n+1} - 1$. Multiplying both sides of (1) by $2$ gives

$2S = 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + \dots + 2^{n+1}$ (2)

Now subtract Equation (1) from Equation (2) to obtain $2S - S = -2^{0} + 2^{n+1}$, which simplifies to $S = 2^{n+1} - 1$. Combining this with Equation (1) produces $2^0 + 2^1 + 2^2 + 2^3 + 2^4 + \dots + 2^n = 2^{n+1} - 1$, so the proof is complete.

I don't follow how the subtraction was performed. I think I'm very close to understanding this, but there's some key piece missing that's preventing me from articulating this proof.

I understand it a little better if I line up $S$ and $2S$ above each other diagrammatically, in which case it's clear that multiplying $S$ by $2$ is the same as shifting the bits to the right, such that we lose the $2^0$ we had before ($-1$) but gain an extra $2^{n+1}$ that was not there before, such that the total difference ends up being $2^{n+1} - 1$.

$S = \color{red}{2^0} + \color{blue}{2^1 + 2^2 + 2^3 + 2^4 + \dots + 2^{n-1} + 2^n}$

$2S = \color{blue}{2^1 + 2^2 + 2^3 + 2^4 + 2^5 \dots + 2^{n-1} + 2^n} + \color{red}{2^{n+1}}$

How can I express this intuitive understanding more formally? What am I missing? I'm having trouble actually performing the subtraction step.

Equivalently, I know I can translate this problem into one where we're dealing with binary strings, showing that $111...111$ is the same as $1000...000$ (with a leading $1$ in the $n+1$th bit) minus $0000...001$ (one), which produces a binary string with a $1$ in every place from $0$ to $n$. Is that an acceptable proof?

$\endgroup$
6
  • 1
    $\begingroup$ $S= 2S-S = $ (bottom sum) - (top sum) = ... quote various rules of elementary algebra to rearrange terms and associate them so the cancelling pairs are next to each other and all that's left are the two terms you want. What kind of formality do you want? $\endgroup$
    – Ned
    Oct 1, 2022 at 17:06
  • $\begingroup$ The binary string proof doesn't generalize well so I don't think it's as good. Better would be to examine how multiplying by $x$ over a polynomial shifts the terms, then deriving these other results as special case. In particular if you're given a polynomial $p(x)$ then consider $(x-1)p(x)$ which will shift then subtract a copy. What does that tell you about polynomials of the form $p(x) = \sum_{k=0}^n x^k$? $\endgroup$ Oct 1, 2022 at 17:17
  • $\begingroup$ You want us to evaluate a sum without summation? Please define that term. For example, @OscarLanzi wrote an answer using a telescoping series; are those banned? $\endgroup$
    – J.G.
    Oct 1, 2022 at 17:55
  • $\begingroup$ @Ned Huh. You're right. I'm not sure why I was overcomplicating this so much. I just looked at it again and it's actually straightforward: the $2^0$ becomes a $-2^0$ when subtracting. All other terms from $i=1$ to $i=n$ cancel out, leaving a positive $2^{n+1}$. $\endgroup$ Oct 1, 2022 at 17:59
  • 1
    $\begingroup$ @JeanMarie I guess I just feel that a choice of basis requires justification. It is not important to the argument made and I can see no purpose for it here. In fact, I feel this example in particular shows why generalizing is better than specializing. We can solve the same problem for polynomials and by the same techniques so why not go that direction instead? $\endgroup$ Oct 1, 2022 at 18:28

2 Answers 2

1
$\begingroup$

Telescoping

Render

$2^{n+1}=2×2^n=2^n+2^n;\therefore 2^n=2^{n+1}-2^n$

So

$2^0+2^1+2^2+...2^n=(2^1-2^0)+(2^2-2^1)+...+(2^{n+1}-2^n)$

and then cancel the $+2^1$ and $-2^1$ terms, then the $+2^2$ and $-2^2$ terms, and so on through the $+2^n$ and $-2^n$ terms, and you're left with just $+2^{n+1}$ and $-2^0=-1$ making up the sum.

$\endgroup$
1
  • $\begingroup$ The dictionary meaning of telescoping: "(with reference to an object made of concentric tubular parts) slide or cause to slide into itself, so that it becomes smaller" may help understand how the telescoping effect comes in. Also, the great Alexander Bogomolny's blogpost: cut-the-knot.org/m/Algebra/TelescopingSums.shtml has some lucidly written material. $\endgroup$ May 22, 2023 at 3:13
1
$\begingroup$

I kind of answered my own question when asking it. Figured I'd formally post an answer with the colored highlights:

$S = \color{red}{2^0} + \color{blue}{2^1 + 2^2 + 2^3 + 2^4 + \dots + 2^{n-1} + 2^n}$

$2S = \color{blue}{2^1 + 2^2 + 2^3 + 2^4 + 2^5 \dots + 2^{n-1} + 2^n} + \color{red}{2^{n+1}}$

(Just distribute the $2$ to every term in $S$, effectively raising each term's power by one. This is identical to taking an $n$-bit binary string and performing a bitwise shift of one place to the left.)

Then, take advantage of the fact that $2S - S = S$:

$2S - S = 2^{n+1} - 2^0 = 2^{n+1} - 1 = S$

Basically, all the blue terms cancel out when performing the subtraction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .