Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorial-proofs]

Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc. They avoid complicated algebraic manipulations.

60
votes
6answers
46k views

Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$

I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$. I already know the logical Proof: $${n \choose k}^2 = {...
15
votes
4answers
9k views

Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$ I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its ...
4
votes
2answers
955 views

Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.
20
votes
5answers
2k views

Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially

$$\text{Evaluate } \sum_{k=1}^n k^2 \text{ and } \sum_{k=1}^{n}k(k+1) \text{ combinatorially.}$$ For the first one, I was able to express $k^2$ in terms of the binomial coefficients by considering a ...
3
votes
2answers
1k views

Evaluate $\sum\limits_{k=0}^n \binom{n}{k}$ combinatorially

Please help me to evaluate combinatorially the following sum: $$\sum_{k=0}^n \binom{n}{k}$$ Thank you.
16
votes
4answers
7k views

Combinatorial interpretation of sum of squares, cubes

Consider the sum of the first $n$ integers: $$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$ This has always made the following bit of combinatorial sense to me. Imagine the set $\{*,1,2,\ldots,n\}...
69
votes
2answers
6k views

Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even

In my answer here I prove, using generating functions, a statement equivalent to $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$ when $n$ is even. (Clearly the sum is $...
3
votes
2answers
267 views

$\sum_{k=-m}^{n} \binom{m+k}{r} \binom{n-k}{s} =\binom{m+n+1}{r+s+1}$ using Counting argument

I saw this question here:- Combinatorial sum identity for a choose function This looks so much like a vandermonde identity, I know we can give a counting argument for Vandermonde. However much I try ...
17
votes
3answers
609 views

Show that $\sum\limits_{k=0}^n\binom{2n}{2k}^{\!2}-\sum\limits_{k=0}^{n-1}\binom{2n}{2k+1}^{\!2}=(-1)^n\binom{2n}{n}$

How can I prove the identity: $$ \sum_{k=0}^n\binom{2n}{2k}^2-\sum_{k=0}^{n-1}\binom{2n}{2k+1}^2=(-1)^n\binom{2n}{n}? $$ Maybe, can we expand $$ f(x)=(1+x)^{2n}? $$ Thank you.
6
votes
4answers
462 views

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$ [duplicate]

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant ...
7
votes
1answer
143 views

Calculating $\sum_{k=1}^nk(k!)$ combinatorially [duplicate]

The sum $\sum_{k=1}^nk(k!)$ can be easily calculated by noting $k(k!)=(k+1)!-k!$. Is there a way to calculate the sum nicely using a combinatorial argument. Is it possible to notice it is $(n+1)!-1$ ...
8
votes
2answers
372 views

Combinatorial proof that $\frac{({10!})!}{{10!}^{9!}}$ is an integer

I need help to prove that the quantity of this division : $\dfrac{({10!})!}{{10!}^{9!}}$ is an integer number, using combinatorial proof
3
votes
2answers
316 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
2
votes
4answers
4k views

Fermat's Combinatorial Identity: How to prove combinatorially? [duplicate]

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} = \binom{n+1}{r+1}$$ I don't have much experience with combinatorial proofs, so I'm grateful for all the hints. (Presumptive) ...
14
votes
4answers
1k views

Combinatorial proof that binomial coefficients are given by alternating sums of squares?

A student recently asked whether there was a combinatorial proof of the following identity: $\begin{equation*} \sum^n_{k=1}(-1)^{n-k}k^2 = {n+1 \choose 2}. \end{equation*}$ I was in a rush and ...
6
votes
3answers
6k views

Combinatorial Proof of Multinomial Theorem - Without Induction or Binomial Theorem

I've been trying to rout out an exclusively combinatorial proof of the Multinomial Theorem with bounteous details but only lighted upon this one - see P2. Any other helpful ones? $(x_1+\cdots+x_k)^...
8
votes
2answers
2k views

Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$. In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where ...
7
votes
4answers
436 views

Combinatorial proofs of the following identities

I've been trying to find combinatorial proofs of the following two identities: 1: $\displaystyle\sum_{i=0}^{k} \binom{n}{i} = \sum_{i=0}^{k} \binom{n-1-i}{k-i} 2^i$ with $0 \le k \le n-1$ 2: $\...
5
votes
4answers
1k views

Give the combinatorial proof of the identity $\sum\limits_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
6
votes
1answer
420 views

Combinatorial interpretation of a sum identity: $\sum_{k=1}^n(k-1)(n-k)=\binom{n}{3}$

I solved $\sum_{k=1}^n(k-1)(n-k)$ algebraically \begin{eqnarray*} \sum_{k=1}^n(k-1)(n-k)&=&\sum_{k=1}^n(nk-n-k^2+k)\\ &=&\sum_{k=1}^nnk-\sum_{k=1}^nn-\sum_{k=1}^nk^2+\sum_{k=1}^nk\\ &...
2
votes
1answer
590 views

Combinatorial proof for $\sum_{k = 0}^n \binom {r+k} k = \binom {r + n + 1} n$ [duplicate]

I'm trying to figure out a combinatorial proof for: $$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$ I've tried the committee counting thing, but that didn't work.
7
votes
4answers
1k views

A combinatorial proof of the identity: $\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$?

Give a combinatorial proof of the identity: $$\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$$ I am not exactly sure where to start. Since $\binom{n}{k}^2 = \binom{n}{k}\binom{n}{k}$, thus, ...
10
votes
3answers
563 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
4
votes
3answers
375 views

Proof of (complicated?) summation equality

This is a simplified case of something I'm trying to prove. Suppose that $N,h$ are even. I want to show that $$ \sum_{k=1}^{(N-h)/2} \frac{2^{2k}}{kN^{\underline{2k}}}\left(\frac{N}{2}\right)^{\...
7
votes
1answer
331 views

Prove ${n \choose k}^2 = \sum_{i=0}^{k}{n \choose i}{n-i \choose k-i}{n-k \choose k-i}$ using a combinatorial argument

I've been studying for a final exam. I have gotten stuck on this one question that asks us to prove using a double-counting proof that $${n \choose k}^2 = \sum_{i=0}^{k}{n \choose i}{n-i \choose k-i}{...
0
votes
2answers
484 views

Combination proof $\sum_{k=1}^nk\binom{n}{k}^2=n\binom{2n-1}{n-1}$

How can I show that k and n being integers $\sum_{k=1}^nk\dbinom{n}{k}^2=n\dbinom{2n-1}{n-1}$ the following is true using a combination proof. I am not sure how to do this. on the right hand side ...
6
votes
1answer
1k views

How to begin combinatorial proof of $\sum_{k=1}^n k \binom nk^2 = n \binom{2n-1}{n-1}$

The question states to give a combinatorial proof for: $$\sum_{k=1}^{n}k{n \choose k}^2 = n{{2n-1}\choose{n-1}}$$ Honestly, I have no idea how to begin. I want to do a two-way counting proof, ...
6
votes
2answers
848 views

Stirling numbers combinatorial proof

This is a Homework Question. I am required to give a Combinatorial proof for the following. $$S(m,n)=\frac 1{n!} \sum_{k=0}^{n} (-1)^k\binom nk (n-k)^m$$ Hint given is : Show that $n!S(m,n)$ ...
4
votes
1answer
161 views

Combinatorial Identity Proof

What is a combinatorial proof for this identity: $1 \times 1! + 2 \times 2! + ... + n \times n! = (n + 1)! - 1$ I am trying to figure out what are both sides trying to count.
5
votes
4answers
493 views

Combinatorial Proof

I have trouble coming up with combinatorial proofs. How would you justify this equality? $$ n\binom {n-1}{k-1} = k \binom nk $$
4
votes
3answers
125 views

How to prove with double counting technique that $1+2+\dots+2^n=2^{n+1} -1$?

How to prove with double counting technique that $1+2+\dots+2^n=2^{n+1} -1$? I can see, for example, that the right-hand side of the equation counts the cardinality of the powerset of a set with n+1 ...
2
votes
3answers
2k views

Combinatorial Proof of falling factorial and binomial theorem

For $n,m,k \in \mathbb{N}$, prove the equality $$(n+m)^{\underline{k}}=\sum^{k}_{i=0}\binom ki \cdot n^{\underline{k-i}} \cdot m^{\underline{i}}$$ Here, $x^{\underline{j}}$ denotes a falling ...
37
votes
5answers
9k views

The Hexagonal Property of Pascal's Triangle

Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that: the product of non-adjacent vertices is constant. the greatest common ...
13
votes
3answers
319 views

Combinatorial interpretation of identity: $\sum\limits_{j=0}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2$

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently: \begin{equation} \sum_{j=0}^b\binom{b}{j}^2\binom{n+j}{...
22
votes
5answers
2k views

Is there a combinatorial interpretation of the triangular numbers?

The triangular numbers count the number of items in a triangle with $n$ items on a side, like this: This can be calculated exactly by the formula $T_n = \sum_{k=1}^n k = \frac{n(n+1)}{2} = {n+1 \...
13
votes
3answers
506 views

Prove $1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3}$

Prove that: $$ 1^2+2^2+\cdots+n^2 = {n+1\choose2}+2{n+1\choose3} $$ Now, if I simplify the right hand combinatorial expression, it reduces to $\frac{n(n+1)(2n+1)}{6}$ which is well known and can be ...
13
votes
3answers
560 views

Strange combinatorial identity $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0$ [duplicate]

I need to find a combinatorial proof of this identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2n-2k}{n-1}=0.$$ I think inclusion exclusion is the best method here. But I"m having a really hard ...
11
votes
1answer
362 views

Combinatorial Proof of $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$ for $n \geq 4$

For $n \geq 4$, show that $\binom{\binom{n}{2}}{2} = 3 \binom{n}{3}+ 3 \binom{n}{4}$. LHS: So we have a set of $\binom{n}{2}$ elements, and we are choosing a $2$ element subset. RHS: We are ...
5
votes
3answers
296 views

Understanding the combinatorial argument for $\binom{\binom{n}{2}}{2} = 3 \binom{n+1}{4}$.

I was playing around the expression for $\binom{\binom{n}{2}}{2}$, and I discovered that it equals $3\binom{n+1}{4}$. I couldn't come up with any combinatorial argument, but found various ones on this ...
4
votes
4answers
108 views

Proof of a combination identity: $\sum\limits_{i=0}^m\sum\limits_{j=0}^m\binom{i+j}{i}\binom{2m-i-j}{m-i}=\frac {m+1}2\binom{2m+2}{m+1}$

I'm studying the special case of question Finding expected area enclosed by the loop when $m=n$ and $A=2n$. I found $f_{n,n}(2n)=S(n-2)$, where $S$ is defined as $$S(m)=\sum_{i=0}^m\sum_{j=0}^m\...
4
votes
2answers
202 views

A Curious binomial identity

While playing around with random binomial coefficients , I observed that the following identity seems to hold for all positive integers $n$: $$ \sum_{k=0}^{2n} (-1)^k \binom{4n}{2k}\cdot\binom{2n}{k}^...
4
votes
3answers
274 views

Use combinatorial arguments to prove the following binomial identities

Can anyone help prove this binomial identities by using the combinatorial arguments, I have no clue to get start. Thanks. $$\binom{2n+1}{n}=\sum_{k=0}^{n}\binom{n+k}{k}$$
3
votes
1answer
214 views

Seeking a combinatorial proof of the identity$1 f_1+2 f_2+\cdots+n f_n=n f_{n + 2} - f_{n + 3} + 2$ [closed]

I would appreciate if somebody could help me with the following problem Q: $f_1=f_2=1, f_{n+2}=f_{n+1}+f_n(n\geq 2)$ Show that combinatoric identity (using by combinatorial proof) $$1 f_1+2 f_2+\...
11
votes
1answer
266 views

Does the functional equation $p(x^2)=p(x)p(x+1)$ have a combinatorial interpretation?

A recent question asked about polynomial solutions to the functional equation $p(x^2)=p(x)p(x+1)$. Subsequently, Robert Israel posted an answer showing that solutions are necessarily of the form $p(x)=...
8
votes
3answers
281 views

A peculiar binomial coefficient identity

While inventing exercises for a discrete math text I'm writing I came up with this $$ \binom{\binom{n}{2}}{2}=3\binom{n+1}{4} $$ It's an easy result to prove, but it got me wondering Is this pure ...
7
votes
1answer
86 views

Combinatorial argument for $1+\sum_{r=1}^{r=n} r\cdot r! = (n+1)!$ [duplicate]

Combinatorial argument for $$1+\sum\limits_{r=1}^{r=n} \ r\cdot r! = (n+1)!$$ The algebraic proof is easy as $r=(r+1)-1$.
6
votes
2answers
359 views

Combinatorial proof that central binomial coefficients are the largest ones

We can easily show that the central binomial coefficients in a row of Pascal's triangle, i.e. $\binom{2n}n$ in even rows and $\binom{2n+1}n=\binom{2n+1}{n+1}$ in odd rows, have the largest values - ...
6
votes
1answer
214 views

Combinatorial proof of a certain alternating sum of binomial coefficients

The following identity appeared as a question earlier today $$\displaystyle\sum\limits_{k=0}^n (-1)^k\binom{m+1}{k}\binom{m+n-k}{n-k} = \begin{cases} 1\ \text{if}\ n=0 \\ 0\ \text{if}\ n>0 \end{...
4
votes
2answers
138 views

An identity involving binomial coefficients and rational functions

While going through some exercises in my analysis textbook, I came up with an equation which looks like an identity. I strongly believe that this is the case, but I couldn't prove this. $$\sum_{0\...
3
votes
2answers
166 views

Is there an algebraic proof for $\sum_{m=k}^{n-k} \binom{m}{k}\binom{n-m}{k} = \binom{n+1}{2k+1}, n\ge2k\ge0$

$\sum_{m=k}^{n-k} \binom{m}{k}\binom{n-m}{k} = \binom{n+1}{2k+1}, n\ge2k\ge0$ An combinatorial proof of the identity above states as follow: (1)Number of ways of picking (2k+1) numbers from 1 to (n+...