Combinatorics Question

M

MathStudent1999

Junior Member
Joined
Mar 18, 2012
Messages
76
If N is a whole number what is the following sum. Express your answer in terms of n.

nC0 + nC1 + nC2 + nC3 + ... + nCn.

I simplified it to 1 + n/1 + n(n-1)/2! + n(n-1)(n-2)/3! + ... + n!/n!

How do I simplify it further?
 
Pascal Explains this one - no?

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

and so on

1 = 1
1+1 = 2
1+2+1 = 4
1+3+3+1 = 8
1+4+6+4+1 = 16
1+5+10+10+5+1 = 32

I see it!
 
I believe that TKHunny's point is that the "binomial coefficients", \(\displaystyle _nC_i\), are so called because \(\displaystyle (x+ y)^n= \sum_{i=0}^n _nC_i x^iy^{n-i}\).

What do you get when you set x= y= 1?
 
Hello, MathStudent1999!

I\(\displaystyle \text{If }N\text{ is a natural number, what is the following sum?}\)
\(\displaystyle \text{Express your answer in terms of }n.\)

. . \(\displaystyle _nC_0 + _n\!C_1 + _n\!C_2 + _n\!C_3 +\:\cdots\:+ _n\!C_n\)
Click to expand...

Crank out a few cases and look for a pattern.

\(\displaystyle \begin{array}{ccc}n=1 \\ \hline _1C_0 &= & 1 \\ _1C_1 &=& 1 \\ \hline \text{Total}&=& \boxed{2} \end{array} \qquad \begin{array}{ccc}n=2 \\ \hline _2C_0 &= & 1 \\ _2C_1 &=& 2 \\ _2C_2 &=& 1\\ \hline \text{Total}&=& \boxed{4} \end{array} \qquad \begin{array}{ccc}n=3 \\ \hline _3C_0 &= & 1 \\ _3C_1 &=& 3 \\ _3C_2 &=& 3 \\ _3C_3 &=& 1\\ \hline \text{Total}&=& \boxed{8} \end{array}\)

. . . . . . \(\displaystyle \begin{array}{ccc}n=4\\ \hline _4C_0 &=&1 \\ -4C_1 &=& 4 \\ _4C_2 &=& 6 \\ _4C_3 &=& 4 \\ _4C_4 &=& 1 \\ \hline \text{Total} &=& \boxed{16} \end{array} \qquad \begin{array}{ccc} n=5 \\ \hline _5C_0 &=&1 \\ _5C_1 &=& 5 \\ _5C_2 &=& 10 \\ _5C_3 &=& 10 \\ _5C_4 &=& 5 \\ _5C_5 &=& 1 \\ \hline \text{Total} &=& \boxed{32} \end{array}\)


Do you see the pattern?
Now you have a target . . .
 
soroban said:
Hello, MathStudent1999!


Crank out a few cases and look for a pattern.

\(\displaystyle \begin{array}{ccc}n=1 \\ \hline _1C_0 &= & 1 \\ _1C_1 &=& 1 \\ \hline \text{Total}&=& \boxed{2} \end{array} \qquad \begin{array}{ccc}n=2 \\ \hline _2C_0 &= & 1 \\ _2C_1 &=& 2 \\ _2C_2 &=& 1\\ \hline \text{Total}&=& \boxed{4} \end{array} \qquad \begin{array}{ccc}n=3 \\ \hline _3C_0 &= & 1 \\ _3C_1 &=& 3 \\ _3C_2 &=& 3 \\ _3C_3 &=& 1\\ \hline \text{Total}&=& \boxed{8} \end{array}\)

. . . . . . \(\displaystyle \begin{array}{ccc}n=4\\ \hline _4C_0 &=&1 \\ -4C_1 &=& 4 \\ _4C_2 &=& 6 \\ _4C_3 &=& 4 \\ _4C_4 &=& 1 \\ \hline \text{Total} &=& \boxed{16} \end{array} \qquad \begin{array}{ccc} n=5 \\ \hline _5C_0 &=&1 \\ _5C_1 &=& 5 \\ _5C_2 &=& 10 \\ _5C_3 &=& 10 \\ _5C_4 &=& 5 \\ _5C_5 &=& 1 \\ \hline \text{Total} &=& \boxed{32} \end{array}\)


Do you see the pattern?
Now you have a target . . .
Click to expand...


Is think I see a pattern. 2^n. is this correct?
 
MathStudent1999 said:
Is think I see a pattern. 2^n. is this correct?
Click to expand...

Yes indeed. The sum \(\displaystyle \sum_{k=0}^n \binom{n}{k} = 2^n. \)

Do you need to prove this result, or is it enough to observe the pattern noted above?

If you need to prove it, one nice way is via the binomial theorem, which says \(\displaystyle (a+b)^n = \sum_{k=0}^n \binom{n}{k}a^{n-k}b^{k} \).

What happens if you let a and b both equal 1?
 
You must log in or register to reply here.
Top