Summation and nCk Homework: Understanding the Formula and Its Application

[holezch]

Homework Statement

n+1 , n
\sum (nCk-1) f(x)g(x) + \sum (nCk) f(x)g(x)
k=1 , k = 0 (for first and second summations respectively) I can't just say that that is equal to:

n+1
\sum (n+1 C k) f(x)g(x)
k=0

since the (nC k-1) and (nC k) above are kind of illusionary, (n C k-1) starts at 1 and ends when k = n+1 so it's just exactly the same as the (nC k) summation

right?

thanks

Homework Equations

n+1 C k = n C k-1 + n C k

The Attempt at a Solution

see above

 

[HallsofIvy]

The first thing I would do is factor out the "f(x)g(x)". This is
f(x)g(x)\left(\sum_{k=1}^{n+1} _nC_{k-1}+ \sum_{k=0}^n _nC_k\right)

Then it might be a good idea to look at a couple of simple cases. For example, if n= 1, this is
f(x)g(x)\left(_1C_0+ _1C_1+ _1C0+ _1C_1\right)
= f(x)g(x)\left(1+ 1+ 1+ 1\right= 4f(x)g(x)
and if n= 2, this is
f(x)g(x)\left(_2C_0+ _2C_1+ _2C_2+ _2C_0+ _2C_1+ _2C_2\right)
= f(x)(g(x))\left(1+ 2+ 1+ 1+ 2+ 1\right)= 8f(x)g(x)

You cannot just add the binomial coefficients because they start and end with the different values of k but it certainly looks as if the two sums give exactly the same thing. You can try to prove that by changing the index on, say, the first sum. In the first sum, if we let i= k-1, then when k= 1, i=0 and when k= n+1, i= n. Also, k= i+ 1 so _nC_{k-1}= _nC_i. That is, \sum_{k=1}^{n+1} _nC_{k-1}= \sum_{i=0}^n _nC_i which is exactly the same as \sum_{k=0}^n _nC_i so your sum is 2f(x)g(x)\sum_{k=0}^n _nC_i.

And that sum is easy- why are those numbers called "binomial coefficients"?

 

[holezch]

The first thing I would do is factor out the "f(x)g(x)". This is
f(x)g(x)\left(\sum_{k=1}^{n+1} _nC_{k-1}+ \sum_{k=0}^n _nC_k\right)

Then it might be a good idea to look at a couple of simple cases. For example, if n= 1, this is
f(x)g(x)\left(_1C_0+ _1C_1+ _1C0+ _1C_1\right)
= f(x)g(x)\left(1+ 1+ 1+ 1\right= 4f(x)g(x)
and if n= 2, this is
f(x)g(x)\left(_2C_0+ _2C_1+ _2C_2+ _2C_0+ _2C_1+ _2C_2\right)
= f(x)(g(x))\left(1+ 2+ 1+ 1+ 2+ 1\right)= 8f(x)g(x)

You cannot just add the binomial coefficients because they start and end with the different values of k but it certainly looks as if the two sums give exactly the same thing. You can try to prove that by changing the index on, say, the first sum. In the first sum, if we let i= k-1, then when k= 1, i=0 and when k= n+1, i= n. Also, k= i+ 1 so _nC_{k-1}= _nC_i. That is, \sum_{k=1}^{n+1} _nC_{k-1}= \sum_{i=0}^n _nC_i which is exactly the same as \sum_{k=0}^n _nC_i so your sum is 2f(x)g(x)\sum_{k=0}^n _nC_i.

And that sum is easy- why are those numbers called "binomial coefficients"?

the sum of all nCk's is just 2^n, is that what you mean?

 

[HallsofIvy]

Yes.