# You Can't Handle the (Next) Proof!

March 18, 2014 5:23 PM Subscribe

Working through Apostol's Calculus Volume I for personal development. Stuck on a proof, again. Can you help?

Apologies for the ugly formula approximation. Difficulty: prove by induction.

(1 + 1/n)^n = 1 + Σ (k= 1 to n) {1/k! π (r = 0 to k-1) (1 - r/n) }

Yes, that's product notation after the 1/k! term. Any help appreciated, as I'm not seeing this one after leaving it uncompleted and circling back for a couple weeks.

Apologies for the ugly formula approximation. Difficulty: prove by induction.

(1 + 1/n)^n = 1 + Σ (k= 1 to n) {1/k! π (r = 0 to k-1) (1 - r/n) }

Yes, that's product notation after the 1/k! term. Any help appreciated, as I'm not seeing this one after leaving it uncompleted and circling back for a couple weeks.

Can you take a picture of the problem? Right now it's difficult to tell what everything is.

posted by semaphore at 6:32 PM on March 18, 2014

posted by semaphore at 6:32 PM on March 18, 2014

Expand the left-hand side using the binomial expansion. Then you have

(1 + 1/n)^n = Σ (k= 0 to n) { [n!/k!(n-k!)] (1/n)^k }

= 1 + Σ (k= 1 to n) { [n!/k!(n-k!)] (1/n)^k }

which you'll notice looks an awful lot like the right-hand side of the given equation. So to prove the formula, it would suffice to prove that

π (r = 0 to k-1) (1 - r/n) = [n!/(n-k!)] (1/n)^k

for all k (but fixed n). I haven't gone through this latter proof myself, but it looks pretty well-suited to proof by induction.

posted by Johnny Assay at 6:54 PM on March 18, 2014 [1 favorite]

(1 + 1/n)^n = Σ (k= 0 to n) { [n!/k!(n-k!)] (1/n)^k }

= 1 + Σ (k= 1 to n) { [n!/k!(n-k!)] (1/n)^k }

which you'll notice looks an awful lot like the right-hand side of the given equation. So to prove the formula, it would suffice to prove that

π (r = 0 to k-1) (1 - r/n) = [n!/(n-k!)] (1/n)^k

for all k (but fixed n). I haven't gone through this latter proof myself, but it looks pretty well-suited to proof by induction.

posted by Johnny Assay at 6:54 PM on March 18, 2014 [1 favorite]

Just went through the latter proof by induction; it proceeds pretty nicely. I don't want to spoil the answer if you want to figure it out on your own, but I'm happy to give you more pointers if you want them. Just say the word.

posted by Johnny Assay at 7:01 PM on March 18, 2014

posted by Johnny Assay at 7:01 PM on March 18, 2014

(Oh, and I suppose you could prove the binomial expansion itself via induction too, if you wanted to go whole-hog on the induction thing.)

posted by Johnny Assay at 7:16 PM on March 18, 2014

posted by Johnny Assay at 7:16 PM on March 18, 2014

Thanks, Johnny. Applying the binomial theorem before trying induction was what I was missing!

posted by bfranklin at 8:19 PM on March 18, 2014

posted by bfranklin at 8:19 PM on March 18, 2014

This thread is closed to new comments.

posted by ElliotH at 5:28 PM on March 18, 2014 [1 favorite]