Proving the Summation Problem using Combinations: A Step-by-Step Guide

  • Thread starter MathematicalPhysicist
  • Start date
  • Tags
    Summation
In summary, the conversation discusses the use of the binomial theorem and the expansion of (1+x)^n(1+x)^n=(1+x)^2n to prove that n sum [C(n,k)]^2=C(2n,n). The conversation also explores finding coefficients by equating two different expressions and using the example of (1+x)^4 to illustrate this method.
  • #1
MathematicalPhysicist
Gold Member
4,699
371
i have to prove that:

n
sum [C(n,k)]^2=C(2n,n)
k=0
i have in my text a hint that i need to use:

(1+x)^n(1+x)^n=(1+x)^2n
but i got that:

n 2n
sum [C(n,k)]^2= sum [C(2n,k)]
k=0 k=0

how do i get out of this mess?
 
Physics news on Phys.org
  • #2
it should be
2n
sum C(2n,n)
k=0

but i reackon you understood me the first time.
 
  • #3
Of course, you know that [itex](1+ x)^n= \sum_{i=0}^n _nC_i x^i[/itex] (the binomial theorem). What are the coefficients of (1+x)n(1+x)n in terms of nCi?
 
  • #4
2n_C_i

but still it the summation sign stays, unless i open it this way:

2n_C_1+2n_C_2+...+2n_C_2n
am i wrong here completely?
 
  • #5
Notice that you are multiplying two sums together.
(a+ bx+ cx2)(u+ vx+ wx2)= au+ avx+ awx2+ bux+ bvx2+ bwx3+ cux2+ cvx3+ cwx4= au+ (av+bu)x+ (aw+ bv+ cu)x2+ (bw+ cv)x3+ cwx4.

Each coefficient is a sum.
 
  • #6
but here we have (1+2x+x^2)^n=(1+(2x+x^2))^n=
n
=sum n_C_k (2x+x^2)^k
k=0

when x=1

n
sum (n_C_k)*3^k= (n_C_0)+3*(n_C_1)+...+3^n
k=0

now how do i get from this, the final answer:
2n_C_n
?
 
  • #7
[tex]\binom{2n}{n}[/tex]

is the coefficient of x^n in the expansion of (1+x)^{2n}

that is all the hint you need (oh, and to possibly forget what you'd done and start again).
 
  • #8
Are you allowed to give arguments about how the left side represents the number of ways to make some choice, and show tha the right side represents the same thing, thereby proving that both quantities are equal? The number of ways to choose n objects from a set of 2n is equal to the number of ways to:

choose 0 from the first n AND then n from the second n
OR
choose 1 from the first n AND then n-1 from the second n
OR
.
.
.
OR
choose k from the first n AND n-k from the second n
OR
.
.
.
OR
choose n from the first n AND choose 0 from the second n

=

choose 0 from the first n AND then 0 from the second n
OR
choose 1 from the first n AND then 1 from the second n
OR
.
.
.
OR
choose k from the first n AND k from the second n
OR
.
.
.
OR
choose n from the first n AND choose n from the second n

since the number of ways to choose n-k elements from n is the same as the number of ways to choose k.
 
  • #9
matt grime said:
[tex]\binom{2n}{n}[/tex]

is the coefficient of x^n in the expansion of (1+x)^{2n}

that is all the hint you need (oh, and to possibly forget what you'd done and start again).

i know that
2n
(1+x)^2n=sum (2n_C_k)x^k
k=0

but how do i get the coeffient only, that's my big q?
 
  • #10
what does 'get the coefficient' mean?

Write down the expression in two different ways, equate coefficients.

EXAMPLE.

(1+x)^4 = 1+4x+10x^2+4x^3+x^4 here are the 4Cr

it also equals ((1+x)^2)^2=(1+x+x^2)^2=(2C0+2C1x + 2C0x^2)^2

now can you see how to find the coeffiecients in two different ways?
 
  • #11
[tex](1+x)^n=\sum_{k=0}^{n} _nC_kx^k[/tex] and [tex](1+x)^{2n}=\sum_{k=0}^{2n} _{2n}C_kx^k[/tex]

and since [tex](1+x)^n(1+x)^n=(1+x)^{2n}[/tex] we have

[tex](1+x)^n(1+x)^n=\left( \sum_{k=0}^{n} _nC_kx^k\right) \left( \sum_{j=0}^{n} _nC_jx^j\right) = \sum_{k=0}^{2n} _{2n}C_kx^k = (1+x)^{2n}[/tex]

from here, multiply out

[tex]\left( \sum_{k=0}^{n} _nC_kx^k\right) \left( \sum_{j=0}^{n} _nC_jx^j\right)[/tex]

to get a sum of the form

[tex]\sum_{k=0}^{2n} a_kx^k[/tex]

where you need to figure out what the ak's are. It then follows that, equating coefficients of like powers of x, we must have

[tex]a_k= _{2n}C_k[/tex].
 
  • #12
matt grime said:
what does 'get the coefficient' mean?

Write down the expression in two different ways, equate coefficients.

EXAMPLE.

(1+x)^4 = 1+4x+10x^2+4x^3+x^4 here are the 4Cr

it also equals ((1+x)^2)^2=(1+x+x^2)^2=(2C0+2C1x + 2C0x^2)^2

now can you see how to find the coeffiecients in two different ways?

now i get it.
it took time, but thanks matt and halls, and also the new guy, benorin.
(-:
 

What is the Summation Problem?

The Summation Problem, also known as the Summation Formula, is a mathematical concept used to find the sum of a series of numbers. It is often denoted by the Greek letter sigma (Σ) and is commonly used in various fields of science, such as physics, engineering, and computer science.

What is the purpose of proving the Summation Problem using Combinations?

The purpose of proving the Summation Problem using Combinations is to provide a step-by-step guide for understanding and verifying the formula. By using combinations, we can show that the formula for finding the sum of a series of numbers is not just a random concept, but it is derived from a logical and mathematical process.

What is the process of proving the Summation Problem using Combinations?

The process involves breaking down the summation formula into smaller parts and using combinatorial identities to manipulate and simplify the equation. This eventually leads to a simplified form of the formula that can be easily proven using mathematical induction.

Why is it important to understand the proof for the Summation Problem using Combinations?

Understanding the proof for the Summation Problem using Combinations can help with a better understanding of the formula and its applications. It also allows for a deeper understanding of combinatorial identities and their role in mathematics. Additionally, understanding the proof can help in developing critical thinking and problem-solving skills.

Are there any real-world applications of the Summation Problem using Combinations?

Yes, the Summation Problem has many real-world applications, such as in calculating the total distance traveled by a moving object, finding the average of a set of numbers, and determining the total number of possible outcomes in a probability experiment. It is also commonly used in computer science algorithms and engineering calculations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
358
  • Calculus and Beyond Homework Help
Replies
6
Views
695
  • Calculus and Beyond Homework Help
Replies
1
Views
93
  • Calculus and Beyond Homework Help
Replies
6
Views
421
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
490
  • Calculus and Beyond Homework Help
Replies
4
Views
95
  • Calculus and Beyond Homework Help
Replies
17
Views
488
  • Calculus and Beyond Homework Help
Replies
17
Views
2K
Replies
23
Views
1K
Back
Top