Question

Prove that $\sum_{i=1}^s a_i=2^{n}-1-\sum_{i=s+1}^n a_i=2^s-1. Note that $\sum_{i=1}^n=2^n-1.

Answer 1

Answer on Question #69617 - Math - Combinatorics / Number Theory

Question

Prove that $\sum_{i=1}^{s} 2^i = 2(2^n - 1) - \sum_{i=s+1}^{n} 2^i = 2(2^s - 1)$

Note that $\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$

Solution

We shall prove

$$\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$$

by induction.

Base case: setting $n = 0$, we get

$$\sum_{i=0}^{0} 2^i = 2^0 = 1 = 2^{0+1} - 1$$

True

Induction step: Let $n$ be an arbitrary natural number and suppose that

$$2^0 + 2^1 + \cdots + 2^n = 2^{n+1} - 1$$

Then

$$\underbrace{2^0 + 2^1 + \cdots + 2^n}_{\text{Formula (1)}} + 2^{n+1} = \underbrace{2^{n+1} - 1}_{\text{Formula (1)}} + 2^{n+1} = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1,$$

hence

$$\sum_{i=0}^{n+1} 2^i = 2^{n+2} - 1$$

holds true.

By the principle of mathematical induction, we proved that

$$\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$$

Therefore

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

and

$$\sum_{i=1}^{s} 2^i = 2^{s+1} - 2 = 2(2^s - 1)$$

Next,

$$\sum_{i=0}^{n} 2^i = 2^0 + \sum_{i=1}^{n} 2^i = 1 + \sum_{i=1}^{s} 2^i + \sum_{i=s+1}^{n} 2^i = 2^{n+1} - 1,$$

hence

$$\sum_{i=1}^{s} 2^i = 2^{n+1} - 1 - 1 - \sum_{i=s+1}^{n} 2^i = 2(2^n - 1) - \sum_{i=s+1}^{n} 2^i$$

There are two ways to express $\sum_{i=1}^{s} 2^i$ if we use formulas (2) and (3):

$$\sum_{i=1}^{s} 2^i = 2(2^n - 1) - \sum_{i=s+1}^{n} 2^i = 2(2^s - 1)$$

Q.E.D.

Answer provided by https://www.AssignmentExpert.com