Binomial Theorem related proof: sum [i=0 to n][nCi] = 2^n

[daon]

Sometime during my previous semester, I was assigned a proof that I couldn't complete. Looking through my papers today, I found it and am trying it once again, but I keep getting stuck...

The question is: Prove that

\(\displaystyle \L \sum _{i=0}^{n} (^n_i) = 2^n\)

So I figure the proof must be by induction. Anything I try in the inductove step, I always end up with a \(\displaystyle (^n_{-1})\) or \(\displaystyle (^n_{n+1})\).. which I believe are 'illegal', right? I was able to construct a proof using these 'illegal' moves, but of course the Professor caught it and I didn't receive credit...

I really only need a "push" in the right direction, please don't complete the proof for me if you know the answer.

Thanks!

EDIT:
For example, something like this usually happens:

(Inductive step)

\(\displaystyle \L

\sum _{i=0}^{n+1} (^{n+1} _i) = (^{n+1}_0) + \sum _{i=1}^{n+1} (^{n+1}_i)

\\
...
\\
= 1 + \sum _{i=1}^{n+1} [(^{n}_{i-1}) + (^{n}_{i})]
\\
...
\\ = 1 + \sum _{i=1}^{n+1} (^{n}_{i-1}) + \sum _{i=1}^{n+1} (^{n}_{i})\)

See what I mean (the last term)? No matter what I try and do I end up with a similar result...

 

[pka]

Daom, you have been away!
Will you take the standard proof? I hate induction when not necessary.
Recall that \(\displaystyle \L
\left( {x + y} \right)^n = \sum\limits_{k = 0}^n {{n \choose k} x^{n - k} y^k }\)
Now let x=1 and y=1.


P.S. You might look at my LaTeX to see the 'choose option'.

 

[galactus]

Hey Daon:

Probability isn't my forte'(I'm learning more), but I think induction would

be messier than just a committee argument.

Committee:

We choose a committee from n people. Since each person has 2 choices,

be on the committee or off the committee---therefore, the number of

ways to form the committee is \(\displaystyle 2^{n}\).


OTOH, the committee can have i people for any i from 0 to n. there are

C(n,i) ways to choose from n people a committee of i people. The total

number of committees by this way is:

\(\displaystyle \L\\\begin{pmatrix}n\\0\end{pmatrix}+\begin{pmatrix}n\\1\end{pmatrix}

+\begin{pmatrix}n\\2\end{pmatrix}+......+\begin{pmatrix}n\\n\end{pmatrix}\)

So, we have:

\(\displaystyle \L\\\begin{pmatrix}n\\0\end{pmatrix}+\begin{pmatrix}n\\1\end{pmatrix}

+\begin{pmatrix}n\\2\end{pmatrix}+....+\begin{pmatrix}n\\n\end{pmatrix}=2^{n}\)


If you must use induction, I'd maybe start with the identity:

\(\displaystyle \L\\\begin{pmatrix}n\\i\end{pmatrix}=\begin{pmatrix}n-1\\i\end{pmatrix}+\begin{pmatrix}n-1\\i-1\end{matrix}\)

 

[daon]

Pka,
Yes, I have been quite busy, but I'll be around more often though. I'll be going through an abstract algebra book that I want to finish this summer..

Thank you for that tip (I never thought to use the actual Binomial Thm.), so I will also try it by your method. However, I have been trying to do this problem by Induction, so I'd like to complete it that way as well, since I think that is the way our Professor intended us to do it.

I guess I'm just stubborn!

Galactus,
Thanks for the response, but I really want to complete this using Induction. I tried using the idenity you mentioned but I end up having problems like the one I showed above.

Oh, and, do you think "proof by committe argument" would be an acceptable method in my undergraduate classes? (joking, joking..)


Thanks

 

[galactus]

Hey Daon:

Using the identity I mentioned:

Since \(\displaystyle \L\\\sum_{k=0}^{n+1}\begin{pmatrix}n-1\\k\end{pmatrix}+\sum_{k=0}^{n+1}\begin{pmatrix}n-1\\k-1\end{pmatrix}=\sum_{k=0}^{n+1}\begin{pmatrix}n\\k\end{pmatrix}\)

Perhaps you could add \(\displaystyle \L\\\sum_{k=0}^{n+1}\begin{pmatrix}n\\k-1\end{pmatrix}\) to both sides

This gives

\(\displaystyle \L\\\sum_{k=0}^{n+1}\begin{pmatrix}n+1\\k\end{pmatrix}\)

Which equals \(\displaystyle 2^{n+1}\)

Just a thought, maybe something to start with. Good luck.

 

[pka]

PROBLEM!
\(\displaystyle \L
\sum\limits_{k = 0}^{n - 1} {n+1 \choose k-1}\) is not defined for k=0.

 

[daon]

Just a thought, maybe something to start with. Good luck.

Thats similar to the mistake I made when I first submitted it.

However, In addition to what pka mentioned,

\(\displaystyle \sum_{k=0}^{n+1} {n \choose k}\) has an undefined value (I think so, anyway..) for \(\displaystyle {n \choose {n+1}}
\\\)

Same thing for:
\(\displaystyle \sum_{k=0}^{n+1} {{n-1} \choose k} \,\, and \,\, \sum_{k=0}^{n+1} {{n-1} \choose {k-1}}\)

I'll keep working on it... Maybe there's no way to do it by this method. I just e-mailed my Professor, hopefully she gets back to me soon..

Thanks again.

 

[galactus]

OK Daon. Please post your inductive proof when you get it. I'd like to see it.

I don't see why our approach doesn't work. Seems OK. The numbers check. If it's undefined at 0, use 1. Oh well.

I think we need to liberalize mathematics. That way we could just say it's OK and the heck with the glitches :lol:

Mathematical pluralism: All solutions are true(as not to hurt the other solutions feelings).

 

[daon]

OK Daon. Please post your inductive proof when you get it. I'd like to see it.

I don't see why our approach doesn't work. Seems OK. The numbers check. If it's undefined at 0, use 1. Oh well.

I think we need to liberalize mathematics. That way we could just say it's OK and the heck with the glitches :lol:

Mathematical pluralism: All solutions are true(as not to hurt the other solutions feelings).

Will do.

If you were serious asking why its undefined, its because given \(\displaystyle {n \choose k}\) n must be greater-than or equal to k and k must be greater than or equal to zero.

This is why.. If k > n then n-k<0 and we have:
\(\displaystyle {n \choose k} = \frac{n!}{k!(n-k)!}\). Because n-k < 0 we have a negative factorial. Similarly, if k<0 we have the same thing.

 

[galactus]

I knew what you meant, Daon. Just havin' fun. It seemed so viable though.

\(\displaystyle \L\\\sum_{k=1}^{n+1}\begin{pmatrix}n-1\\k-1\end{pmatrix}=\sum_{k=1}^{n}\begin{pmatrix}n-1\\k-1\end{pmatrix}=\sum_{k=0}^{n}\begin{pmatrix}n-1\\k-1\end{pmatrix}=\sum_{k=0}^{n+1}\begin{pmatrix}n-1\\k-1\end{pmatrix}\)


\(\displaystyle \L\\\sum_{k=0}^{n+1}\begin{pmatrix}n\\k-1\end{pmatrix}=\sum_{k=1}^{n+1}\begin{pmatrix}n\\k-1\end{pmatrix}\)


\(\displaystyle \L\\\sum_{k=0}^{n+1}\begin{pmatrix}n-1\\k\end{pmatrix}=\sum_{k=0}^{n}\begin{pmatrix}n-1\\k\end{pmatrix}\)


\(\displaystyle \L\\\sum_{k=0}^{n+1}\begin{pmatrix}n\\k\end{pmatrix}=\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}\)

If you enter an integer value into the formulas we spoke of, you do get

\(\displaystyle 2^{n+1}\), regardless.

Maybe write it in its equivalent factorial form and solve algebraically.

Try it this way, the result is the same:

\(\displaystyle \L\\\sum_{k=0}^{n+1}\begin{pmatrix}n-1\\k\end{pmatrix}+\sum_{k=1}^{n+1}\begin{pmatrix}n-1\\k-1\end{pmatrix}+\sum_{k=1}^{n+1}\begin{pmatrix}n\\k-1\end{pmatrix}=\sum_{k=0}^{n}\begin{pmatrix}n\\k\end{pmatrix}+\sum_{k=1}^{n+1}\begin{pmatrix}n\\k-1\end{pmatrix}=\sum_{k=0}^{n+1}\begin{pmatrix}n+1\\k\end{pmatrix}=2^{n+1}\)

Oh yeah, almost forgot, the committee argument should be accepted. I learned it in combinatorics and graph theory class. Besides, you'll find it in textbooks as a viable method. Take care and good luck with your induction.

 

[daon]

Well, I saw this topic and gave it another attempt.. And I think I got it!!

Okay.. I'm writing this as a complete proof, so that if anyone stumbles upon this thread it will be easy to understand..

Proposition: \(\displaystyle For \,\, n, \,\, i \,\, \in \,\, \mathbb{N} \,\, with \,\, i \,\,\) \(\displaystyle \le \,\, n\),

\(\displaystyle \L \,\,\,\,\,\, \sum_{i=0}^{n} {{n} \choose i } = 2^{n}\)

Proof: by induction on n

Initial case: n = 0

\(\displaystyle \L \,\,\,\,\,\, \sum_{i=0}^{0} {{0} \choose i } = {{0} \choose {0}} = 1 = 2^0\)

Inductive case: With the hypothesis that\(\displaystyle \L \,\,\,\,\,\, \sum_{i=0}^{n} {{n} \choose i } = 2^n\),
we will show that \(\displaystyle \L \,\,\,\,\,\, \sum_{i=0}^{n+1} {{n+1} \choose i } = 2^{n+1}\).
---------------------------------------------------------------------------

By the definition of \(\displaystyle \sum\),

\(\displaystyle \L \,\,\,\,\,\,\,\, \sum_{i=0}^{n+1} {{n+1} \choose i } = {{n+1} \choose{0}} + \sum_{i=1}^{n} {{n+1} \choose i } + {{n+1} \choose {n+1}}\,\,\)[1]

By the definition of \(\displaystyle {{n} \choose {k}}\), \(\displaystyle \sum{{n+1} \choose {i}} = \sum({{n} \choose {i}} + {{n} \choose {i-1}})\).

Secondly, by the definiton of \(\displaystyle \sum\), \(\displaystyle \sum({{n} \choose {i}} + {{n} \choose {i-1}}) = \sum{{n} \choose {i}} + \sum{{n} \choose {i-1}}\).

Make these substitutions into [1], then:

\(\displaystyle \L \,\,\,\,\,\,\,\, \sum_{i=0}^{n+1} {{n+1} \choose i } = {{n+1} \choose{0}} + \sum_{i=1}^{n} {{n} \choose i } + \sum_{i=1}^{n} {{n} \choose {i-1} } + {{n+1} \choose {n+1}}\,\,\) [2]

Since \(\displaystyle {{n+1} \choose {0}} = {{n} \choose {n}}\) and \(\displaystyle {{n+1} \choose {n+1}} = {{n} \choose {0}}\), make these substitutions into [2]. This yeids:

\(\displaystyle \L \,\,\,\,\,\,\,\, \sum_{i=0}^{n+1} {{n+1} \choose i } = {{n} \choose{0}} + \sum_{i=1}^{n} {{n} \choose i } + \sum_{i=1}^{n} {{n} \choose {i-1} } + {{n} \choose {n}} \,\,\) [3]

By the definition of \(\displaystyle \sum\), \(\displaystyle \sum_{i=1}^{n} {{n} \choose {i-1} } = \sum_{i=0}^{n-1} {{n} \choose {i} }\). Applying this change to [3] gives:

\(\displaystyle \L \,\,\,\,\,\,\,\, \sum_{i=0}^{n+1} {{n+1} \choose i } = {{n} \choose{0}} + \sum_{i=1}^{n} {{n} \choose i } + \sum_{i=0}^{n-1} {{n} \choose {i} } + {{n} \choose {n}} \,\,\) [4]

We can now combine the first two terms together and the latter two terms together by the definition of \(\displaystyle \sum\) . Making this change to [4] yeilds:

\(\displaystyle \L \,\,\,\,\,\,\,\, \sum_{i=0}^{n+1} {{n+1} \choose i } = \sum_{i=0}^{n} {{n} \choose i } + \sum_{i=0}^{n} {{n} \choose {i} } \,\,\) [5]

FINALLY (*sigh*), by our induction hypthesis, we can rewrite [5] as:

\(\displaystyle \L \,\,\,\,\,\,\,\, \sum_{i=0}^{n+1} {{n+1} \choose i } = 2^n + 2^n = 2(2^n) = 2^{n+1}\)


-Daon

 

[pka]

It looks like that you have done it.
However, I still maintain that this is very poor problem to do by induction!
The way that I suggested shows clearly the connection between the binominal coefficients and powers of 2.

 

[daon]

However, I still maintain that this is very poor problem to do by induction!
The way that I suggested shows clearly the connection between the binominal coefficients and powers of 2.

I agree. The problem was that, having never completed this (the way it was assigned), I felt the problem silently tauning me.. Its now a boulder of my back.