• Support PF! Buy your school textbooks, materials and every day products Here!

Summation and nCk

  • Thread starter holezch
  • Start date
  • #1
251
0

Homework Statement


n+1 , n
[tex]\sum[/tex] (nCk-1) f(x)g(x) + [tex]\sum[/tex] (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
[tex]\sum[/tex] (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
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
955
The first thing I would do is factor out the "f(x)g(x)". This is
[tex]f(x)g(x)\left(\sum_{k=1}^{n+1} _nC_{k-1}+ \sum_{k=0}^n _nC_k\right)[/tex]

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

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 [itex]_nC_{k-1}= _nC_i[/itex]. That is, [itex]\sum_{k=1}^{n+1} _nC_{k-1}= \sum_{i=0}^n _nC_i[/itex] which is exactly the same as [itex]\sum_{k=0}^n _nC_i[/itex] so your sum is [itex]2f(x)g(x)\sum_{k=0}^n _nC_i[/itex].

And that sum is easy- why are those numbers called "binomial coefficients"?
 
  • #3
251
0
The first thing I would do is factor out the "f(x)g(x)". This is
[tex]f(x)g(x)\left(\sum_{k=1}^{n+1} _nC_{k-1}+ \sum_{k=0}^n _nC_k\right)[/tex]

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

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 [itex]_nC_{k-1}= _nC_i[/itex]. That is, [itex]\sum_{k=1}^{n+1} _nC_{k-1}= \sum_{i=0}^n _nC_i[/itex] which is exactly the same as [itex]\sum_{k=0}^n _nC_i[/itex] so your sum is [itex]2f(x)g(x)\sum_{k=0}^n _nC_i[/itex].

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?
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,833
955
Yes.
 

Related Threads on Summation and nCk

  • Last Post
Replies
4
Views
1K
Replies
5
Views
3K
Replies
3
Views
2K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
7
Views
1K
Top