# How to prove a formula for the sum of powers of 2 by induction?

Here is where I"m getting off traông chồng. Lets look at the right side of the last equation: \$2^n+1 -1\$ I can rewrite this as the following.

Bạn đang xem: How to prove a formula for the sum of powers of 2 by induction?

\$2^1(2^n) - 1\$ But, from our hypothesis \$2^n = 2^n+1 - 1\$ Thus:

\$2^1(2^n+1 -1) -1\$ This is where I get lost. Because when I distribute through I get this.

\$2^n+2 -2 -1\$ This is wrong is it not? Am I not applying the rules of exponents correctly here? I have the solution so I know what I"m doing is wrong. Here is the correct proof. summation induction
Share
Cite
Improve sầu this question
Follow
edited Mar 8 "15 at 4:14
user147263
asked Feb 18 "11 at 0:37 \$endgroup\$
1

21
\$egingroup\$
Both

Inductive Step khổng lồ prove sầu is: \$ 2^n+1 = 2^n+2 - 1\$Our hypothesis is: \$2^n = 2^n+1 -1\$

are wrong & should be

Inductive sầu Step lớn prove sầu is: \$ 2^0 + 2^1 + ... + 2^n + 2^n+1 = 2^n+2 - 1\$Our hypothesis is: \$ 2^0 + 2^1 + ... + 2^n = 2^n+1-1\$

Add \$2^n+1\$ to both sides of the hypothesis and you have the step lớn prove since \$2^n+1-1 +2^n+1 = 2^n+2 - 1\$

Share
Cite
Follow
answered Feb 18 "11 at 0:44 HenryHenry
\$endgroup\$
21
\$egingroup\$
An easy way to lớn vày this is using binary. Here"s an idea of what I mean:

\$2^0\$ in binary is \$1\$\$2^1\$ in binary is \$10\$\$2^2\$ in binary is \$100\$

For a general rule:

\$2^n\$ in binary is \$100cdots0\$ (n zeros)

Add those together & you get \$2^0 + 2^1 + ... + 2^n\$ in binary is \$11...11\$ (\$n+1\$ ones).

Now it"s obvious that adding 1 to lớn that gives you\$\$100cdots00 quad ext (\$n+1\$ zeros)\$\$Which as we all know is \$2^n+1\$.

Thus \$2^n+1 - 1\$ is equal so the sum of powers of two up lớn \$2^n\$.

Share
Cite
Follow
edited Jan 11 "16 at 0:30 JnxF
answered Jan 11 "16 at 0:12 \$endgroup\$
1
9
\$egingroup\$
HINT \$ \$ Here"s the inductive proof for summing a general geometric series.

THEOREM \$ mquad 1 + x + cdots + x^n-1 = dfracx^n-1x-1\$

Proof \$ \$ Base case: It is true for \$ m n = 1:,:\$ viz. \$ m 1 = (x-1)/(x-1):\$.

Inductive step: Suppose it is true for \$ m n = k:. \$ Then we have

\$\$ m x^k + (x^k-1 +: cdots: + 1): =: x^k +fracx^k-1x-1 = fracx^k+1-1x-1\$\$

which implies it is true for \$ m: n = k+1:,:\$ thus completing the inductive sầu proof.

Xem thêm: Bài 20: Thu Hoạch Bảo Quản Và Chế Biến Nông Sản, Thu Hoạch Bảo Quản Và Chế Biến Nông Sản

The proof you seek is just the special case \$ m x = 2 \$.

Share
Cite
Follow
answered Feb 18 "11 at 1:19 Bill DubuqueBill Dubuque
\$endgroup\$
0
\$egingroup\$
I don"t see the answer I like here, so I"m writing my own.

Basic proof:

We wish to prove \$2^0 + 2^1 + ... + 2^n-1 = 2^n - 1\$ for all \$n\$. We can verify by inspection this is true for n=1. Next, assume that \$2^0 + 2^1 + ... + 2^n = 2^n+1 - 1\$.

\$(2^0 + 2^1 + ... + 2^n) + 2^n+1 = (2^n+1 - 1) + 2^n+1 = 2 cdot 2^n+1 - 1 = 2^n+2 - 1\$, so we have shown \$2^0 + 2^1 + ... + 2^n-1 = 2^n - 1\$ is true for all n.

Share
Cite
Follow
edited Jan 18 at 7:52
Community♦
1
answered Atruyền thông quảng cáo 9 "18 at 4:12
EratosthenesEratosthenes
\$endgroup\$
2

Thanks for contributing an answer to pgdtxhoangmai.edu.vnematics Staông chồng Exchange!

But avoid

Asking for help, clarification, or responding to other answers.Making statements based on opinion; baông xã them up with references or personal experience.

Use pgdtxhoangmai.edu.vnJax to format equations. pgdtxhoangmai.edu.vnJax reference.

Xem thêm: Giải Bài Tập Sinh Học 8 Bài 38 : Bài Tiết Và Cấu Tạo Hệ Bài Tiết Nước Tiểu

Draft saved

Submit

### Post as a guest

Name
Email Required, but never shown

### Post as a guest

Name
E-Mail

Required, but never shown

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

Featured on Meta
16 votes · comment · stats
0
How to lớn prove sầu by induction that \$sum^n_i=12^i-1=2^n-1\$?
1
Proof by induction (exponents)
4
Find all positive sầu integers \$n\$ such that \$frac2^n-1+1n\$ is integer. Where I'm wrong?
1
Proof By Induction Help?
0
No disjoint partition for \$2^1, 2^2, …,2^15\$ such the sum of elements in all partitions is the same
1
Proof by induction that \$sum_j=0^n 2^j = 2^n+1 - 1\$
0
By induction, show that for ∀n∈N, it is true that:
Related
2
Prove by induction (formula for \$sum^n(3i-1)^2\$)
0
Prove by induction \$ sum^n_i=1(i-1/2) = n^2/2 \$
0
Trying to correctly write the proof using *strong* induction of the sum of the nth positive integer
1
Proof of closed khung for finite sums by induction.
0
Proof by Induction of an ineunique with a sum
1
Am I properly using induction (specifically the induction hypothesis)?
1
Inductive sầu proof on a sequence
0
Induction on powers of powers.
1
How bởi vì I prove that the phối of rational functions is closed under composition by structural induction?
Hot Network Questions more hot questions

Question feed

pgdtxhoangmai.edu.vnematics
Company
Stack Exchange Network
site design / biểu tượng logo © 2021 Staông xã Exchange Inc; user contributions licensed under cc by-sa. rev2021.7.8.39684

pgdtxhoangmai.edu.vnematics Stachồng Exchange works best with JavaScript enabled 