Prove 2^n possibly with the binomial theorem

[gap0063]

Prove for all n[tex]\in[/tex][tex]N[/tex]
2ⁿ= ([tex]\stackrel{n}{0}[/tex])+([tex]\stackrel{n}{1}[/tex])+...+([tex]\stackrel{n}{n}[/tex])

So I used mathematical induction

base case: n=0 so 2⁰=1 and ([tex]\stackrel{0}{0}[/tex])=1

induction step: Let n[tex]\in[/tex][tex]N[/tex] be given, assume as induction hypothesis that 2ⁿ= ([tex]\stackrel{n}{0}[/tex])+([tex]\stackrel{n}{1}[/tex])+...+([tex]\stackrel{n}{n}[/tex])

I think I'm trying to prove 2ⁿ⁺¹= ([tex]\stackrel{n+1}{0}[/tex])+([tex]\stackrel{n+1}{1}[/tex])+...+([tex]\stackrel{n+1}{n}[/tex])


but I don't know how to apply the binomial theorem (if I'm even supposed to!)

 

[Office_Shredder]

This is really a combinatorics problem.

Think about how many ways there are to pick a subset out of a set of n elements.

 

[gap0063]

This is really a combinatorics problem.

Think about how many ways there are to pick a subset out of a set of n elements.

I don't understand... :/

 

[HallsofIvy]

Yes, use the binomial theorem! Let x= y= 1 in [itex](x+ y)^n[/itex].

 

[blue_raver22]

to prove this.

To prove this using the binomial theorem, we can rewrite 2^n as (1+1)^n and then apply the binomial theorem:

(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^{n-k} 1^k = \sum_{k=0}^{n} \binom{n}{k}

which is equivalent to (\stackrel{n}{0})+(\stackrel{n}{1})+...+(\stackrel{n}{n})

Now, we can substitute 2n into this expression to get:

(1+1)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k}

Since we know that 2n is equivalent to (\stackrel{n}{0})+(\stackrel{n}{1})+...+(\stackrel{n}{n}), we can substitute this in to get:

(1+1)^{2n} = \sum_{k=0}^{(\stackrel{n}{0})+(\stackrel{n}{1})+...+(\stackrel{n}{n})} \binom{2n}{k}

Using the properties of binomial coefficients, we can rewrite this as:

(1+1)^{2n} = \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k}

And since the binomial coefficients are symmetric, we know that \binom{n}{n-k} = \binom{n}{k}, so we can simplify this to:

(1+1)^{2n} = \sum_{k=0}^{n} [\binom{n}{k}]^2

Finally, we can substitute this back into our original expression and get:

2^{2n} = \sum_{k=0}^{n} [\binom{n}{k}]^2

which proves that 2^n = (\stackrel{n}{0})+(\stackrel{n}{1})+...+(\stackrel{n}{n}) for all n\inN.