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
*

lampShadelampShade
99311 gold badge1212 silver badges1717 bronze badges
$endgroup$
1
Add a bình luận |

4 Answers 4


Active Oldest Votes
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
Improve sầu this answer
Follow
answered Feb 18 "11 at 0:44
*

HenryHenry
134k99 gold badges108108 silver badges212212 bronze badges
$endgroup$
Add a bình luận |
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
1,23911 gold badge99 silver badges2222 bronze badges
answered Jan 11 "16 at 0:12
*

AdamAdam
21122 silver badges22 bronze badges
$endgroup$
1
Add a phản hồi |
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
Improve this answer
Follow
answered Feb 18 "11 at 1:19
*

Bill DubuqueBill Dubuque
250k3333 gold badges249249 silver badges799799 bronze badges
$endgroup$
Add a bình luận |
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
10122 bronze badges
$endgroup$
2
Add a phản hồi |

Your Answer


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

Please be sure to lớn answer the question. Provide details & chia sẻ your research!

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.

To learn more, see our tips on writing great answers.

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
Draft discarded

Sign up or log in


Sign up using Google
Sign up using Facebook
Sign up using Thư điện tử & Password
Submit

Post as a guest


Name
Email Required, but never shown


Post as a guest


Name
E-Mail

Required, but never shown


Post Your Answer Disthẻ

By clicking “Post Your Answer”, you agree khổng lồ our terms of service, privacy policy & cookie policy


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
Linked
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
Subscribe khổng lồ RSS
Question feed To subscribe khổng lồ this RSS feed, copy và paste this URL inlớn your RSS reader.


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
*

Your privacy

By clicking “Accept all cookies”, you agree Staông chồng Exchange can store cookies on your device và discđại bại information in accordance with our Cookie Policy.


Chuyên mục: