# Homework Help: Summation and nCk

1. Nov 6, 2009

### holezch

1. The problem statement, all variables and given/known data
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

2. Relevant equations

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

3. The attempt at a solution

see above

2. Nov 6, 2009

### 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"?

3. Nov 6, 2009

### holezch

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

4. Nov 7, 2009

Yes.