1
$\begingroup$

This is a claim in a textbook that I'm using, although it was not proven.

When trying this for small $n$'s it is clear.

\begin{align} 2^2&=1+1+2^1=4\\ 2^3&=1+1+2+2^2\\ 2^4&=1+1+2+4+2^3 \end{align}

What I was thinking for the proof was $2^{n-1}=2(2^{n-2})=2^{n-2}+2^{n-2}$, but obviously that's not incorporating addition, so I don't know where to go on. Is it just expressing $2^{n-2}$ as the first summation?

$\endgroup$
2
  • 1
    $\begingroup$ Have you tried induction? $\endgroup$ – Don Thousand Jan 19 at 0:56
  • $\begingroup$ Just wondering: Why use $n-1$ and $n-2$ instead of $n$ and $n-1$? $\endgroup$ – David G. Stork Jan 19 at 1:37
1
$\begingroup$

It's because it's a geometric progression. Since

$$1+p_i+{p_i}^2+··· +{p_i}^{a_i} = \dfrac{{p_i}^{a_i+1}-1}{p_i-1}. $$

you just add an extra one at the start of the progression.

$\endgroup$
2
$\begingroup$

In binary, this is

$$1+1+10+100+...+1\underbrace{00...00}_{n-2\text{ times}}=1+\underbrace{11...11}_{n-1\text{ times}}=1\underbrace{00...00}_{n-1\text{ times}}$$

which in decimal is $2^{n-1}$.

$\endgroup$
2
$\begingroup$

What you suggest basically seems to work - I'm going to change the leading value into $n$ rather than $n-1$ for ease of reading:

First, $2^1 = 1+1$ and $2^2 = 1+1+2 = 1+2^0+2^1$

Then using induction, assuming that the summation holds for lower $n$, we can use your observation $2^n = 2^{n-1} + 2^{n-1}$ and change the first $2^{n-1}$ into the summation form, giving $2^{n} = 1+1 + 2 + \cdots + 2^{n-2} + 2^{n-1}$ as required.

$\endgroup$
1
  • $\begingroup$ Note that this answer is attempting to build on the OP's apparent attempt to use induction. $\endgroup$ – Joffan 2 days ago
1
$\begingroup$

Let me suggest 4 ways:

  1. $ a^{n}-b^{n}=(a-b)(a^{n-1} + ba^{n-2}+ ... + b^{n-1}) \Rightarrow 2^{n} = 2^{n} - 1 + 1 = 1+2+ ... +2^{n-1} +1 $

  2. Considering all subsets from set with $ n>1 $ elements and considering map between subsets and binary numbers

  3. Mathematical Induction

  4. Newton's binomial theorem

$\endgroup$
1
$\begingroup$

Let $$x = \sum_{m=2}^{n}2^{m-2},$$ and note that $$1 + x = 1 + 1 + 2 + 4 + \dotsb + 2^{n-3} + 2^{n-2}\tag{1}.$$ Then, multiplying $(1)$ by $2$, we have $$2+2x = 2 + 2 + 4 + \dotsb + 2^{n-2} + 2^{n-1}\tag{2}.$$ We can rewrite $(1)$ as $$1 + x = 2 + 2 + 4 + \dotsb + 2^{n-3} + 2^{n-2}\tag{3}.$$ Subtracting $(3)$ from $(2)$ gives us $$1 + x = 2^{n-1},$$ which is the same as $$2^{n-1} = 1 + 1 + 2 + 4 + \dotsb + 2^{n-2}.$$

$\endgroup$
0
$\begingroup$

Let $S:=1+2+4+\dots+2^{n-2}$.

Then, since it's a geometric series, we have $S=\dfrac{1-2^{n-1}}{1-2}=2^{n-1}-1\implies S+1=2^{n-1}$.

$\endgroup$

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.