Why Does the Binomial Theorem Summation Not Equal 2n When n Varies?

[Puzzedd]

Using summation((\stackrel{n}{k})x^ky^n-k) = (x+y)ⁿ, I let x = y = 1. This should then result in summation((\stackrel{n}{k})*1*1) = (1 + 1)ⁿ = 2ⁿ.

Expanding the summation, I get

(\stackrel{n}{0}) + (\stackrel{n}{1}) + ... +(\stackrel{n}{n}) = 2ⁿ.

Solving this results in

\frac{n!}{0!(n-0)!} + \frac{n!}{1!(n-1)!} + \frac{n!}{2!(n-2)!} + ... + \frac{n!}{(n-1)!(n-(n-1))!} + \frac{n!}{n!(n-n)!} = 2ⁿ

1 + n + \frac{n(n-1)}{2!} + \frac{n(n-1)(n-2)}{3!} + ... + n + 1 = 2ⁿ

2 + 2n + n(n-1) + \frac{n(n-1)(n-2)}{3} + ... = 2ⁿ

The issue I am having is that when I plug values of n into the left side I do not get the same answer with the right side.

n = 0 results in 2 + 2(0) + ... = 2, not 2⁰
n = 1 results in 2 + 2(1) + 1(1-1) + ... = 4, not 2¹
n = 2 results in 2 + 2(2) + 2(2-1) + \frac{2(2-1)(2-2)}{3} + ... = 8, not 2²
n = 3 results in 2 + 2(3) + 3(3-1) + \frac{3(3-1)(3-2)}{3} + ... = 16, not 2³

This seems as if (\stackrel{n}{0}) + (\stackrel{n}{1}) + ... +(\stackrel{n}{n}) = 2ⁿ should really be

(\stackrel{n}{0}) + (\stackrel{n}{1}) + ... +(\stackrel{n}{n}) = 2ⁿ⁺¹

Can anyone tell me why solving this summation is not consistent with the binomial theorem?

 

[JThompson]

Your problem lays in the fact that {n\choose k}={n\choose n-k}. While manipulating the expanded factorial form of the series you combined these coefficients, effectively doubling the terms for each choice of n. Whereas for n=0 there should be exactly one term, n\choose 0, you instead have two terms {n\choose 0}+{n\choose n}.
(Which is equal to 2{0\choose 0}).

 

[Yayness]

JThompson is right.

If you wish to combind \binom{n}{k} and \binom{n}{n-k} to get \binom{n}{k}+\binom{n}{n-k}=2\binom{n}{k}, you need to stop in the middle, or you will double the whole thing and get 2·2ⁿ=2ⁿ⁺¹.

If n is odd, you get:
2\binom{n}{0}+2\binom{n}{1}+\ldots+2\binom{n}{\frac{n-1}{2}}=2^n
So the last term should be when k = (n-1)/2. If n=1, the last term should be when k=0, which means there'll only be one term: 2\binom{1}{0}=2
If n=3, you get: 2\binom{3}{0}+2\binom{3}{1}=8 etc.

If n is even, you get:
2\binom{n}{0}+2\binom{n}{1}+...+2\binom{n}{\frac{n}{2}-1}+\binom{n}{\frac{n}{2}}=2^n
So the last term should not be multiplied by 2. That is when k = n/2. If n=0, k will also be 0 in the last term. Since it's the last term, it should not be multiplied by 2.
Exapmles where n is even:
n=0: \binom{0}{0}=1
n=2: 2\binom{2}{0}+\binom{2}{1}=4
n=4: 2\binom{4}{0}+2\binom{4}{1}+\binom{4}{2}=16

So if you wish to combind 2 terms to get fewer terms, remember to stop in the middle, and if n is even, don't multiply the last term by 2.
If you want, you could also just keep all the terms and not multiply any of them by 2.

 

[Puzzedd]

Thanks! I spent an hour thinking about it last night and couldn't see what I was doing wrong.