# 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.

366 questions
817 views

### How do I prove this combinatorial identity

Show that ${2n \choose n} + 3{2n-1 \choose n} + 3^2{2n-2 \choose n} + \cdots + 3^n{n \choose n} \\ = {2n+1 \choose n+1} + 2{2n+1 \choose n+2} + 2^2{2n+1 \choose n+3} + \cdots + 2^n{2n+1 \choose 2n+1}$ ...
22 views

### Partitions of a set with n elements (proof)

I was reading a textbook about combinatorial mathematic which claimed that we can calculate the exact possible partitions of a set with n elements . I searched it on wikipedia and I read about bell ...
48 views

### Combinatorial proof for $\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$

I am trying to give a combinatorial proof for: $$\sum_{k=0}^p (-1)^k {n \choose k} = (-1)^p {n-1 \choose p}$$ Where $p$ and $n$ are natural numbers. We could easily see that if $p=n$ this reduces ...
52 views

### Combinatorial proof of fibonacci

I need to proof this expression combinatorially $f_{2n+1}= \sum_{i \geq 0} \sum_{j\geq 0} \binom{n-i}{j} \binom{n-j}{i}$ for all $n \geq 0$. As $f_1 = 1, f_2=2$ I dont know how to start combinatorial ...
73 views

### Combinatorics Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$

Proof of $\sum_{i=0}^n \sum_{j=0}^{i-1} j = {n+1 \choose 3}$ I am trying to generate a combinatorics proof of this identity, but have been stuck for hours. I've been trying to think of someway to ...
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 ...
49 views

### Combinatorial proof $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$

Give a combinatorial proof (double counting) that $\sum_i^{\lfloor{n/2}\rfloor} (-1)^i {n-i\choose i} 2^{n-2i} = n+1$ There was a hint that maybe $n$ bit binary numbers without 01 may help. (eg. 1001,...
39 views

### Prove your identity using a block-walking argument.

Prove that $\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2=\binom{2n}{n}$ by using a block-walking argument. I found the identity but I wasn't able to find a block-walking argument. Could ...
193 views

### Prove: $[k+y-1-v]{v \choose k}\geq \sum_{j=0}^a(-1)^j \left( \sum_{i=0}^k{v-i \choose k-i}r_i(j)\right)+\epsilon(a,k,p)$

I'm studying the ramsey numbers, especially $R(3,6)=18$ for Graver and Jackel, and i have tried to understand the theorem $2$ for quite some time but I have not succeeded. Theorem 1: Let $G$ be a ...
42 views

### Combinatorial proof of $\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$

Give a combinatorial proof for this identity for nonnegatif integer $k$ and $n$ such that $0 \leq k < n$ $\sum_{j=0}^{k} \binom{n}{j} = \sum_{j=0}^k \binom{n-1-j}{k-j}2^j$ My attempt: I tried to ...
22 views

### Proof by induction: summation inductive step

Disclaimer: This question is just a practice question and is not for marks. I am trying to prove the following statement (I'm skipping right to the inductive step here since the base case is trivial):...
94 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 ...
83 views

64 views

36 views

### How do I solve this combinatorial proof involving factorial (n)_k?

Let $n$ and $k$ be positive integers with $n \ge k$. Give a combinatorial proof that $$n_k = (n-1)_k + k(n-1)_{k-1},$$ where $n_k$ is a falling factorial: $n_k$ = $n(n-1)(n-2)\ldots(n-k+1)$. I know ...
20 views

### How to compute $T'=\{n + 1 - i : i \in T \}$ for lexicographic ordering?

I have a question that came up during one of my combinatorial algorithm lectures, and could use some help. One of the theorems our book provides states that: Let $S$ consist of all $k$-element ...
40 views

### Prove formula by combinatorially [closed]

$$\binom{r}{r} + \binom{r+1}{r}+\binom{r+2}{r} + \cdots + \binom{n}{r}=\binom{n+1}{r+1}$$ I knew that I had to prove from RHS and LHS RHS simply like: take $r+1$ out of $n+1$ elements But How can I ...
84 views

### Collection of less well-known, non-trivial, elegant story proofs (ie, “double counting proofs”) of combinatorial identities

By story proof I mean proving a combinatorial identity by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. The ...
58 views

### Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$ where $n\geq2$ using a combinatorial proof.

Prove the identity $\binom{2n}{2}$ = $\binom{n}{2}+\binom{n}{n-2}+n^2$, where $n\geq2$, using a combinatorial proof. I've tried to think of it in terms of a counting problem. I think that for the ...
65 views

80 views

### Evaluate $4^n = \sum_{k=0}^{n} {n \choose k} 3^k$

Prove $4^n = \sum_{k=0}^{n} {n \choose k} 3^k$, using a combinatorial proof of the set $S = \{(a_1, a_2)| a_1, a_2 \in \{1...n\}\}$. I'm having trouble figuring out how to prove $4^n$(LHS) using the ...
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: \sum_{j=0}^b\binom{b}{j}^2\binom{n+j}{...
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$. ...
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 ...
42 views

### How to make any natural numbers (placed in the chessboard cells) divisible by 10 by using the given tools [closed]

The original condition is: In all cells of a chessboard the natural numbers are placed. You can select a square 3 by 3 or 4 by 4 and add 1 to all numbers in the squares. Is it possible to make a ...
167 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+...
46k views

14 views

### Combinatorial proof that the number of even cardinality subsets is equal to the number of odd cardinality subsets

Given a set of cardinality $n\geq 1$, the number of subsets of even cardinality is equal to the number of subsets of odd cardinality I am looking for a combinatorial proof of this statement- I know ...
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 ...
31 views

### Words of weight 5 in in Ternary Golay Code

I'm not really good at doing this type of exercices. But I'd like to know how to prove that ther are 132 words of weight 5 in the Ternary Golay Code. I am not allowed to use the weight enumerator. I ...
60 views

### Proving $\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$

Use any method to prove that $$\binom{n+1+m}{n+1}=\sum_{k=0}^m(k+1)\binom{n+m-k}{n}$$ My Try: Base case: Let $m=1$ LHS$$\binom{n+1+m}{n+1}=\binom{n+2}{n+1}=(n+2)$$ RHS\sum_{k=0}^m(k+1)\binom{n+...
### Pigeonhole Principle: Proof that in an isosceles triangle with both side lengths 2 amongst 5 random points within there's two with distance $d < 1$
We're tasked to prove using the pigeonhole principle that, given an isosceles triangle with the two equal side lengths being $l = 2$, you can always choose $5$ random points of which two will have a ...
### value of $k$ in binomial expression
If $\displaystyle \binom{404}{4}-\binom{4}{1}\cdot \binom{303}{4}+\binom{4}{2}\cdot \binom{202}{4}-\binom{4}{3}\cdot \binom{101}{4}=(101)^k.$ Then $k$ is Iam trying to simplify it \$\displaystyle \...