Prove Summation: 2n= \sumnk (^{n}_{k}) (^{m-n}_{n-k}) = (^{m}_{n})

  • Thread starter Thread starter mynameisfunk
  • Start date Start date
  • Tags Tags
    Probability
Click For Summary
SUMMARY

The discussion focuses on proving the identity \(\sum_{k=0}^{n} \binom{n}{k} \binom{m-n}{n-k} = \binom{m}{n}\). Participants emphasize the relationship between the left-hand side, which represents combinations of subsets and their complements, and the right-hand side, which signifies the total combinations of a set of size \(m\) taken \(n\) at a time. The equation \(2^n = \sum_{k=0}^{n} \binom{n}{k}\) is also referenced, highlighting the combinatorial interpretation of binomial coefficients. The discussion seeks clarification on articulating the proof rather than providing a complete solution.

PREREQUISITES
  • Understanding of binomial coefficients, specifically \(\binom{n}{k}\)
  • Familiarity with combinatorial identities and their proofs
  • Basic knowledge of power sets and their properties
  • Experience with mathematical notation and summation
NEXT STEPS
  • Study the combinatorial proof of the Vandermonde identity
  • Explore the concept of generating functions in combinatorics
  • Learn about the binomial theorem and its applications
  • Investigate the relationship between subsets and their complements in set theory
USEFUL FOR

Mathematics students, educators, and anyone interested in combinatorial proofs and identities, particularly those studying binomial coefficients and their applications in combinatorial mathematics.

mynameisfunk
Messages
122
Reaction score
0

Homework Statement



prove that
[tex]\sum[/tex]nk=0 ([tex]^{n}_{k}[/tex]) ([tex]^{m-n}_{n-k}[/tex]) = ([tex]^{m}_{n}[/tex])

Homework Equations


2n=[tex]\sum[/tex][tex]^{n}_{k=0}[/tex] ([tex]^{n}_{k}[/tex])


The Attempt at a Solution


I know that every summand on the left hand side is a member of the power set times the combinations of it's complement and we can think of them in terms of the set changing with every possible combination, 1 element at a time and 2 at a time, 3 at a time, ..., n at a time. Or something like that... Definitely having trouble putting this into words let alone an equation. I certainly see the connection but am needing a little help on the proof. Please not the whole proof but just a little help putting it into words?
 
Last edited:
Physics news on Phys.org
Having some trouble getting my head around this still.
 

Similar threads

Show that the limit (1+z/n)^n=e^z holds
  • · Replies 6 ·
Replies
6
Views
3K
How to explain that n choose k is equal to n choose (n-k)?
  • · Replies 4 ·
Replies
4
Views
3K
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
  • · Replies 1 ·
Replies
1
Views
2K
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
  • · Replies 1 ·
Replies
1
Views
2K
Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
  • · Replies 3 ·
Replies
3
Views
2K
Proving that ##\lim [\sqrt{4n^2 +n} - 2n] = \frac{1}{4}##
  • · Replies 9 ·
Replies
9
Views
3K
Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
For any n, m given ##I_n \thicksim I_m##, prove that ## n=m##
  • · Replies 2 ·
Replies
2
Views
1K
Strong Induction: Proving Every Int n>1 is a Product of Primes
  • · Replies 5 ·
Replies
5
Views
2K
Lemma: Extracting a convergent subsequence
  • · Replies 11 ·
Replies
11
Views
2K