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.