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.

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 $...
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 = {...
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 ...
27
votes
1answer
781 views

Two interview questions

I recently came across two interview questions for admission in B.Math at an university. I gave the two questions a try and want to know if my solutions are correct or not. Q1: Given that $x^4-4x^3+...
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 \...
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 ...
18
votes
2answers
326 views

Is there a combinatorial proof that $e$ is finite?

I'm looking for an integer $N$ and a combinatorial proof either that $(n+1)^n<Nn^n$ or that $\sum_{k=0}^n \frac{n!}{k!}<N\cdot n!$. By "combinatorial proof of $a<b$" I mean exhibiting ...
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.
17
votes
2answers
3k views

Combinatorial proof of $\sum\limits_{k=0}^n {n \choose k}3^k=4^n$

Using the following equation: $$\sum_{k=0}^n {n \choose k}3^k=4^n$$ I need to prove that both sides of the equation solve the same combinatorial problem. It's easy to see that the right side of the ...
16
votes
5answers
3k views

Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that: $$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$ I was told this is supposed to use a ...
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\}...
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 ...
15
votes
2answers
8k views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. $2$-...
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 ...
13
votes
4answers
612 views

Proof Binomial Coefficient Identity: $\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$

Wolfram show that $\displaystyle\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$. click to see How to prove this identity? Thank you.
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 ...
13
votes
3answers
318 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}{...
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
1answer
266 views

A congruence in the number of certain ternary strings

Let $a_n$ be the number of ternary strings of length $n$ which do not contain three consecutive symbols that are all different. That is, $$a_n = \Bigl|\bigl\{\,(b_k)_{1\leq k\leq n}\in \{0,1,2\}^n\...
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 ...
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)=...
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}$$
10
votes
3answers
635 views

On a combinatorial identity involving elementary symmetric polynomials

I'm trying to prove that if we have the elementary symmetric polynomials that the following identity holds:(where $x = (x_1,..,x_n)$ is a vector of n variables) $$\sum_{k=0}^n e_k(x)^2 = x_1\cdots x_n ...
9
votes
2answers
379 views

Seeking a combinatorial proof of the identity$1+3+\cdots+(2n-1)=n^2$ [closed]

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $$1+3+\cdots+(2n-1)=n^2$$
9
votes
3answers
134 views

Prove that $\sum_{l=0}^{n} \binom{n}{l}^2 (x+y)^{2l} (x-y)^{2(n-l)} = \sum_{l=0}^{n} \binom{2l}{l} \binom{2(n-l)}{n-l} x^{2l}y^{2(n-l)}$

This problem derives from an expression of probability in random walk. I hope to prove that \begin{equation*} \sum_{l=0}^{n} \binom{n}{l}^2 (x+y)^{2l} (x-y)^{2(n-l)} = \sum_{l=0}^{n} \binom{2l}{l} \...
9
votes
1answer
166 views

What branch of math studies $g(\mathbf x) \leq g(\sigma \cdot \mathbf x)$?

Let $\mathbf{x} = (x_1, \cdots, x_n) \in \mathbb{R}^n$ such that $x_1 \leq \cdots \leq x_n$ and $g: \mathbb{R}^n \to \mathbb{R}$. I'm trying to prove a theorem which requires me to prove that my ...
8
votes
2answers
371 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
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 ...
8
votes
2answers
129 views

How can I get f(x) from its Maclaurin series?

I know how to get a Maclaurin series when $f(x)$ is given. I have to find $\sum_{n=0}^{\infty}\frac{f^{(k)}(0)}{k!}x^k$. But how can I get $f(x)$ from its Taylor series? The problem is $$f(x) = \...
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 ...
8
votes
0answers
91 views

Binomial sum which adds to $2^n n!$

I'm looking for a combinatorial interpretation for the identity $$ \sum_{k=0}^n\binom nk (2k-1)!!\,(2n - 2k - 1)!! = 2^n n! $$ where $(2n - 1)!! = (2n - 1)(2n - 3) \cdots 5 \cdot 3 \cdot 1$. ...
8
votes
1answer
162 views

Bijection between perfect matchings permutations with even cycles

It is possible to proof that the number of perfect matching on a set of $2n$ elements is $n!!$, and on the other hand, it is also possible to proof that the number of permutations $\varphi$ of a set ...
7
votes
4answers
1k views

Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$

I recently came across a question while studying for an exam. I haven't been able to solve it. We had to prove: $$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$ We had to use counting techniques. This was ...
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, ...
7
votes
4answers
435 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: $\...
7
votes
2answers
72 views

Is it valid to define $\binom{n}{n+k} = 0$

Is it valid to define $$\binom{n}{n+k} = 0$$ where $k$ is an integer in $\{k < -n\}\cup\{k > n\}$ ? I couldn't find anything on this notation via a quick google search, but I ran into it in ...
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}{...
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$.
7
votes
2answers
164 views

Seeking a combinatorial proof of the identity $1^3+2^3+3^3+\cdots+n^3=\{{}_{n+1}C_{2}\}^2$ [closed]

I would appreciate if somebody could help me with the following problem Q: show that combinatoric identity (using by combinatorial proof) $$1^3+2^3+3^3+\cdots+n^3=\{{}_{n+1}C_{2}\}^2$$
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$ ...
7
votes
1answer
301 views

Combinatorial Proof of Combinatorial Identity involving $(-1)^k \binom {n-1}{k}$

Given the following identity: $$\sum_{i=0}^k (-1)^i \binom ni = (-1)^k \binom {n-1}{k}.$$ This is provable by induction. However, I wonder if there is a way to prove this in a combinatorial fashion (...
7
votes
1answer
92 views

Combinatorial proof of $\binom{nk}{2}=k\binom{n}{2}+n^2\binom{k}{2}$

This identity was posted a while back but the question had been closed; the question wasn't asked elaborately, though the proof of the identity is a nice application of combinatorics and a good ...
7
votes
2answers
185 views

Number of integer solutions to $|x_1|+|x_2|+…+|x_n| \le m$

Show that the following two inequalities have the same number of integer solutions. (A) $|x_1|+|x_2|+...+|x_n| \le m$ (B) $|y_1|+|y_2|+...+|y_m| \le n$, where m and n are two positive integers. ...
7
votes
2answers
172 views

Bijective proof that $8+1=9$, or really $3^2-1=2^3$

Catalan's conjecture states that $8$ and $9$ are the only consecutive powers. This suggests to me that the identity $3^2-1=2^3$ might be purely "accidental". So here's the challenge: Is there any ...
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 ...
6
votes
3answers
1k views

Algebraic and combinatorial proof of an identity

For any two integers $2 \le k \le n-2$, there is the identity $$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$$ a) Give an algebraic proof of this identity, writing the binomial ...
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
4answers
240 views

Can anyone give a combinatorial proof of the identity ${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+…+(n-m+1){m \choose m}={n+2 \choose m+2}$

Can anyone give a combinatorial proof of the identity $${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+\ldots+(n+1-m){m \choose m}={n+2 \choose m+2}$$ I am finding difficult as $n$ is varying ...
6
votes
1answer
419 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\\ &...
6
votes
5answers
850 views

Verify the following combinatorial identity: $\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$ [duplicate]

$$\sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}$$ Nice, so I've proven some combinatorial identities before via induction, other more simple ones by committee selection models.... But ...