Discrete math combinatorial proofProve that for every positive integer n, ∑ k = 0 n...

Donna Flynn

Donna Flynn

Answered

2022-07-17

Discrete math combinatorial proof
Prove that for every positive integer n,
k = 0 n ( n k ) 2 = l = 0 n r = 0 n l 2 ( n l ) ( n l r ) ( n l r r )
I know that k = 0 n ( n k ) 2 = ( 2 n n ) but I can't seem to find a way to connect it to the right side.

Answer & Explanation

Tamoni5e

Tamoni5e

Expert

2022-07-18Added 14 answers

Step 1
The lefthand side is the number of pairs ⟨A,B⟩ such that A and B are subsets of [ n ] = { 1 , , n }, and | A | = | B | .
Step 2
You can classify these pairs according to the number of elements that they have in common. Suppose that C = A B; then A∖C and B∖C must be disjoint subsets of [n]. Think of setting = | C | and r = | A C | = | A B | .

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?