Proving 2^n = 1 + (n 1) + (n 2) + ... + (n n-1) + (n n) Using Math Induction

[JG89]

I'm just starting to get the hang of Mathematical induction and I was wondering if you guys could please check this proof just to make sure it is correct.

Before I start, I will use (n k) to represent the binomial coefficient.

-----------------

Prove 2^n = 1 + (n 1) + (n 2) + ... + (n n-1) + (n n)

I am first going to find the case for 2^(n+1).

Using the formula they just gave for 2^n, I will multiply both sides by 2. So,

2^(n+1) = 2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)]

I will call that equation, equation 1.

Now, using the binomial theorem, I will simplify it for (2 + 0) ^ (n+1)

(2 + 0)^(n+1) = (n+1 0)2^(n+1) + (n+1 1)(2^n(0)

We can stop right there since b = 0 , and we can say

(2 + 0)^(n+1) = (n+1 0)2^(n+1)

I will call that equation, equation 2.

Now I am going to equate equation 1 and equation 2 and see if they are the same.


2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)] = (n+1 0)2^(n+1)
2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)] = 2(2^n)(n+1 0)
1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n(n+1 0)
1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n * [(n+1)!/(n+1)!]
1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n

And that was the original formula that I was suppose to prove. So, now I check the case for 2^1 with the original formula. It works out to 2.

Therefore, the theorem is correct.

 

[HallsofIvy]

I'm just starting to get the hang of Mathematical induction and I was wondering if you guys could please check this proof just to make sure it is correct.

Before I start, I will use (n k) to represent the binomial coefficient.

-----------------

Prove 2^n = 1 + (n 1) + (n 2) + ... + (n n-1) + (n n)

I am first going to find the case for 2^(n+1).

Using the formula they just gave for 2^n, I will multiply both sides by 2. So,

2^(n+1) = 2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)]

I will call that equation, equation 1.

But how are you going to go from (n a) to (n+1 a)?

Now, using the binomial theorem, I will simplify it for (2 + 0) ^ (n+1)

(2 + 0)^(n+1) = (n+1 0)2^(n+1) + (n+1 1)(2^n(0)

We can stop right there since b = 0 , and we can say

(2 + 0)^(n+1) = (n+1 0)2^(n+1)

I will call that equation, equation 2.

You realize that equation is exactly 2^(n+1)= 2^(n+1) don't you?

Now I am going to equate equation 1 and equation 2 and see if they are the same.


2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)] = (n+1 0)2^(n+1)
2[1 + (n 1) + (n 2) + ... + (n n-1) + (n n)] = 2(2^n)(n+1 0)
1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n(n+1 0)
1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n * [(n+1)!/(n+1)!]
1 + (n 1) + (n 2) + ... + (n n-1) + (n n) = 2^n

And that was the original formula that I was suppose to prove.

No, that was the formula that, by the "induction hypothesis" you assumed was true.
What you want to prove is that 1+ (n+1 1)+ ...+ (n+1 n)+ (n+1 n+1)= 2^(n+1). You have NOT done that. Basically what you did was start with the induction hypothesis, do a little algebraic manipulation, cancel out all that manipulation and arrive aat exactly what you started with.

So, now I check the case for 2^1 with the original formula. It works out to 2.

Therefore, the theorem is correct.

You want to prove that 1+ (n 1)+ (n 2)+ ... + (n n)= 2^n for all n. You are using the induction hypothesis that it is true for some n. It is better to use "k" instead of "n" so that you do not confuse the two as you did above.

Assuming 1+ (k 1)+ ...+ (k k)= 2^k for some k, you want to prove that
1+ (k+1 1)+ ...+ (k+1 k+1)= 2^(k+1).

I assume you are required to use induction. There is a far simpler proof.

 

[JG89]

Nevermind...I will repost something later...

 

[HallsofIvy]

You will probably want to use the fact that, for i> 0, (n+1 i)= (n i-1)+ (n i). That equation is clear from Pascal's triangle and can be proved directly from the definition of the binomial coefficient.

It will also help to remember that (n 0)= 1= (n+1 0) and (n n)= 1= (n+1 n+1).

 

[JG89]

Alright, here is what I have.

Using the original binomial theorem:

2^(n+1) = (1+1)^(n+1) = (n+1 0) + (n+1 1) + (n+1 2) + ... + (n+1 n) + (n+1 n+1)

We will call this equation 1.

Now, if I take the original theorem and plug in 2^n, I get:

2^n = (1+1)^n = (n 0) + (n 1) + (n 2) + ... + (n n-1) + (n n)

Multiplying both sides by 2:

2^(n+1) = 2[(n 0) + (n 1) + (n 2) + ... + (n n -1) + (n n)]
= 2(n 0) + 2(n 1) + 2(n 2) + ... + 2(n n-1) + 2(n n)
= (n 0) + (n 0) + (n 2) + (n 2) + ... + (n n-1) + (n n-1) + (n n) + (n n)
= (n 0) + [(n 0) + (n 1)] + [(n 1) + (n 2)] + ... + [(n n-1) + (n n)] + (n n)

However, (n 0) = 0, (n k) + (n k + 1) = (n+1 k+1) and (n n) = (n+1 n+1)

Therefore:

= 1 + (n+1 0) + (n+1 1) + ... + (n+1 n) + (n+1 n+1)

Which is the same as if I plug 2^(n+1) into the original binomial theorem.

Now, I have to check if the formula I want to prove is true for 2^1, it is, and so it is proved for all n.

 

[HallsofIvy]

Alright, here is what I have.

Using the original binomial theorem:

2^(n+1) = (1+1)^(n+1) = (n+1 0) + (n+1 1) + (n+1 2) + ... + (n+1 n) + (n+1 n+1)

We will call this equation 1.

Now, if I take the original theorem and plug in 2^n, I get:

2^n = (1+1)^n = (n 0) + (n 1) + (n 2) + ... + (n n-1) + (n n)

Multiplying both sides by 2:

2^(n+1) = 2[(n 0) + (n 1) + (n 2) + ... + (n n -1) + (n n)]
= 2(n 0) + 2(n 1) + 2(n 2) + ... + 2(n n-1) + 2(n n)
= (n 0) + (n 0) + (n 2) + (n 2) + ... + (n n-1) + (n n-1) + (n n) + (n n)
= (n 0) + [(n 0) + (n 1)] + [(n 1) + (n 2)] + ... + [(n n-1) + (n n)] + (n n)

However, (n 0) = 0,

I presume you mean here (n 0)= (n+1 0). Other than that, it looks good.

(n k) + (n k + 1) = (n+1 k+1) and (n n) = (n+1 n+1)

Therefore:

= 1 + (n+1 0) + (n+1 1) + ... + (n+1 n) + (n+1 n+1)

Which is the same as if I plug 2^(n+1) into the original binomial theorem.

Now, I have to check if the formula I want to prove is true for 2^1, it is, and so it is proved for all n.

You posted this very, very quickly after I posted my comments about (n+1 i)= (n i-1)+ (n i) so I presume you found this on your own. I am impressed!

 

[JG89]

I presume you mean here (n 0)= (n+1 0). Other than that, it looks good.



You posted this very, very quickly after I posted my comments about (n+1 i)= (n i-1)+ (n i) so I presume you found this on your own. I am impressed!

Thanks for the words of encouragement!

When you first started learning basic analysis and induction and stuff along those lines, did you have trouble?

I am teaching myself on my own and I just started, and in Canada here, we don't have proofs or anything like this in high school, so it's new to me. So, it's taking me a little while to get a hang of things.

 

[HallsofIvy]

Oh, God, did I have trouble! One of my awful memories is when, early in my first semester in GRADUATE school, I was asked to present a proof from homework in class and turned out to have complete misinterpreted the question! It was about f^-1(A) where A is a set, and had assumed that f had to be an invertible function!