Articles of combinatorial proofs

Combinatorial Proof -$\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$

I’m reading about combinatorics, specifically ‘Cohen’s Introduction to Combinatorial Theory’, and am stuck on one of the problems. I’m looking for a combinatorial proof for the following : $\ n \choose r $ = $\frac nr$$\ n-1 \choose r-1$ If anyone can offer me any help, it would be much appreciated. I haven’t been able […]

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}^{-1}=\frac{1}{1-2n}.$$ However, I am unable to furnish a proof for it ( though this result is just a conjecture ). Any ideas/suggestions/solutions are welcome.

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$

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+\cdots+n f_n=n f_{n + 2} – f_{n + 3} + 2$$

proving an invloved combinatorial identity

How to prove following Identity? $$\sum_{k=0}^n (-1)^k {n-k \choose k} m^k (m+1)^{n-2k} = \frac {m^{n+1}-1}{m-1}, m \ge 2$$ This seems very hard to me. Any idea about how to prove it combinatorialy? [P.S: for $k > \lfloor {\frac n 2}\rfloor$ L.H.S evaluates to $0$. ]

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

This question already has an answer here: Calculating $\sum_{k=1}^nk(k!)$ combinatorially [duplicate] 1 answer

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)=x^m(x-1)^m$. What I had hoped to do myself was provide a solution by interpreting $p(x)$ as a generating function, with the functional equation leading to some kind of counting […]

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 choosing a $3$ element subset and a $4$ element subset (each from a set of $n$ elements). But we multiply by $3$ by […]

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 derived by the method of common differences. This though is in the exercise sheet related to combinatorics and specifically the method of proof by double counting. I can’t […]

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

This question already has an answer here: Sum of binomial coefficients $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n – 2k}{n – 1} = 0$ 4 answers

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 divisor of non-adjacent vertices is constant. Below is one such hexagon. As an example, here we have that $4 \cdot 10 \cdot 15 = 6 \cdot 20 […]