Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc. They avoid complicated algebraic manipulations.
Questions tagged [combinatorial-proofs]
1225 questions
9
votes
2 answers
Seeking a combinatorial proof of the identity$1+3+\cdots+(2n-1)=n^2$
I would appreciate if somebody could help me with the following problem
Q: Seeking a combinatorial proof
$$1+3+\cdots+(2n-1)=n^2$$
Young
- 5,492
7
votes
2 answers
Seeking a combinatorial proof of the identity $1^3+2^3+3^3+\cdots+n^3=\{{}_{n+1}C_{2}\}^2$
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$$
Young
- 5,492
6
votes
1 answer
Provide a combinatorial proof of the identity $\sum_{k = 0}^n \frac{1}{k + 1}{n \choose k} = \frac{2^{n + 1} - 1}{n + 1}$
Provide a combinatorial proof of the identity $$\sum_{k = 0}^n \frac{1}{k + 1}{n \choose k} = \frac{2^{n + 1} - 1}{n + 1}$$
My Proof
I was able to demonstrate combinatorially that
\begin{align}
2^{n + 1} - 1 &= \sum_{k = 0}^n {{n + 1} \choose k}…
user1082389
5
votes
3 answers
Find the number of positive integral solutions of the equation $x_1+x_2+x_3+x_4+x_5=x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5$
Find the number of positive integral solutions of the equation $x_1+x_2+x_3+x_4+x_5=x_1\cdot x_2\cdot x_3\cdot x_4\cdot x_5$
This is one of the questions from the Indian Institution of Technology Joint Entrance Examination question. I have been…
Abhishek P
- 93
4
votes
3 answers
Combinatorial proof of the given identity
Provide a combinatorial argument for the given equation
$${^{n+1}C_4}= {{^{^{^nC_2}}C_2}\over 3} \text{, for } n\ge 4$$
HINT: Consider a group of $n+1$ terms of which one is considered special.
Argue that both sides of the above identity…
Ashwin B
- 159
3
votes
2 answers
proofs for combinatorial identities?
by using the identity $(1-x^2)^n=(1+x)^n(1-x)^n$, show that for each $m \in \Bbb N$ with $m < n$,
summation of
$$\sum_{i=0}^n(-1)^i\binom{n}i^2=\begin{cases}
0,&\text{if }n\text{ is odd}\\
(-1)^{n/2}\binom{n}{n/2},&\text{if }n\text{ is…
bbmas
- 63
- 6
3
votes
3 answers
Give a combinatorial proof for $\binom {n}{r}\binom {r}{k} = \binom {n}{k} \binom {n-k}{r-k}$
What I have tried so far:
Combinatorial Proof:
suppose there are $n$ people. first, we need to select a group of $r$ people. therefore, the number of ways to select $r$ people from $n$ people is $\binom {n}{r}$. Then, the number of ways to choose…
serendipity0217
- 187
3
votes
1 answer
Prove combinatorially that $\sum_{i=1}^n {i(n-i+1)} = {n+2 \choose 3}$
I'm having some trouble in finding a combinatorial way to prove the following expression:
$$\sum_{i=1}^n {i(n-i+1)} = {n+2 \choose 3}$$
I assume proving it in an algebraic way using the choose formula and induction is not too hard, but a…
ODV
- 33
2
votes
3 answers
Combinatorial proof of $ k{n \choose k} = n {n-1\choose k-1} $
I have to prove this using a combinatorial proof
$$
k{n \choose k}
= n {n-1\choose k-1} $$
What's the standard procedure on doing this? The only thing I managed was to split it into: (by fixing one element)
$$
k{n \choose k} =
k\bigg[ {n-1 \choose…
εν οίδα ότι ουδέν οίδα
- 1,138
2
votes
3 answers
Prove this combinatorial identity
$${n \choose k}{k \choose 1}{k-1 \choose 1} = n(n-1){n-2 \choose k-2}$$
hlapointe
- 1,610
2
votes
4 answers
Is there a simpler proof for the following identity: $\sum_{n=0}^x \frac{(n+x)!}{n!2^n} = x!2^x$
The proof I have constructed for this first proves that $\sum_{n=0}^\infty \frac{(n+x)!}{n!2^n} = 2(x!2^x)$ using what I believe is combinatorial geometry, then proves that the identity above is half of that (also using combinatorial geometry), but…
LogicCube
- 67
2
votes
2 answers
Combinatorial proof of $\sum\limits_{i=0}^{r} ({m \choose i}) = {{m + r}\choose m}$
I'm having trouble generating a combinatorial proof for the following equality:
$$\sum_{i=0}^{r} ({m \choose i}) = {{m + r}\choose m}.$$ That is, with no algebraic manipulation, what is an "example" that would sufficiently illustrate what these…
LackLuster
- 29
- 4
2
votes
1 answer
Prove that $\sum_{a_1+a_2+a_3=n}{n \choose {a_1,a_2,a_3}} = 3^n$
I am trying to find a combinatorial proof for the following expression $$\sum_{a_1+a_2+a_3=n}{n \choose {a_1,a_2,a_3}} = 3^n.$$
I have been stuck on this for a while, is there anyone who can help me? Thanks!
urpi
- 629
1
vote
2 answers
A (combinatorics?) problem about shoes
"30 shoes are arbitrary ordered in a row, 15 left and 15 right shoes. In this row there will always be 10 succeeding shoes such that 5 of theme are left shoes (and 5 of theme are right shoes. Prove this mathematically"
I suppose this is some kind of…
sorin dinesko
- 13
- 2
1
vote
1 answer
Given r blocks of one color and g blocks of another color a tower is made. Show that the max height of the tower is independent of the colors.
Given r blocks of one color and g blocks of another color, a tower is formed such that:
Each level of the tower has width(number of blocks) = width of previous(lower) level -
1 .
Each level of the tower has blocks of only 1 type of color.
Some…
