Question    My thought:  As far as the given equality is concerned, I can prove that the relation is true by calculating some general mathematics proving by L.H.S = R.H.S method(given in the picture below)    But I am curious if there is any specific formula of combinatorics which can fetch this equality.(without using this general LHS-RHS method)  Please help me into this.
16808
While thinking about  I found out that this equality might be useful there: $$n\cdot 1 + (n-1)\cdot 2 + \dots + 2\cdot (n-1) + 1\cdot n = \frac{n(n+1)(n+2)}6$$ To rewrite it in a more compact way: $$\sum_{k=1}^n k(n+1-k)=\frac{n(n+1)(n+2)}6.$$  This equality is relatively easy to prove: $$\sum_{k=1}^n k(n+1-k)= (n+1)\sum_{k=1}^n k - \sum_{k=1}^n k^2 = (n+1) \frac{n(n+1)}2 - \frac{n(n+1)(2n+1)}6  = n(n+1) \left(\frac{n+1}2-\frac{2n+1}6\right) = n(n+1)\frac{3(n+1)-(2n+1)}6 =  \frac{n(n+1)(n+2)}6.$$ (We only used the known formulas for the   and the .)   Are there some other nice proofs of this equality? (Induction, combinatorial arguments, visual proofs, ...)     EDIT: Now I found another question which asks about the same identity:  (I have tried to search before posting. But the answers posted here so far gave me some new ideas for good keywords to search which lead me to finding that question.) The questions are, in my opinion, not exact duplicates since the other question asks specifically about combinatorial proofs and my question does not have that restriction. But I agree that this is a very minor distinction. In any case, if you think that one of them should be closed as a duplicate, then you can vote to close. I will refrain from voting to close/reopen on this question. (If one of the two questions is voted to be a duplicate of the other one, they probably cannot be merged, since the summation variables are off by one.)
12731
I asked a similar question yesterday about well ordered sets, now I am having troubles with equivalence relations.   Could someone suggest an injection from a well known set of cardinality $2^{\aleph_{0}}$ to the set of all equivalence relations of $\mathbb{N}$?  Many thanks in advance!
115320
For $m,n\ge 0$,   $$\sum^m_{k=0} (n+k)\left[{n+k}\atop{k}\right]={{m+n+1}\brack m}\;.$$  I need to prove this combinatorially. I know the RHS counts the number of $m+n+1$ permutations with $m$ cycles. I'm stuck on how to show the LHS does so too.
42667
Is there a clever way to show that  $$|x| - |y| \leq |x-y|$$  I believe I can think of a way to solve this using cases, but the book I'm working out of said that "A very short proof is possible if you write things in the right way" which has motivated me to figure out this quick way, but I've failed thus far and any help would be appreciated
46073
Show by combinatorial arguments that:   $$\sum_{k = 0}^m \binom{m}{k}\binom{n}{r + k} = \binom{m + n}{m + r}$$  Hello ,  I want to prove this argument by double counting method, i kinda have an idea of proving by comb args. but not by double counting... Can someone give any clues or ideas? thanks :)
75040
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 order is not significant and repetitions are allowed. So you have $n$ people you form $r$ teams and select $r$ captains and select $(n-r)$ players.  The RHS divides up a team into 2 sets?
55489
$A$ and $B$ two sets. $|A|=k, |B|=n.$ I need to prove in a combinatoric way that the number of partial function from $A$ to $B$ is $(n+1)^k.$ I thing the number is $Σ(n^i),$ for $i=0$ to $k.$ but I have no idea how to show equality, and how to prove it in a combinatoric way.  If someone can show me the way or guide me that will be great!  thanks for helpers.
109455
I am reading  of the Book of Proof, and I'm stuck at the Exercise 10 of section 11.2. It is as follows.  Suppose $R$ and $S$ are two equivalence relations on a set $A$. Prove that $R \cap S$ is also an equivalence relation.  Thanks for helps!
65692
Accidentally, I had seen this relation. I tried to find the formula  Here is my try:-  $$f_0= {{0}\choose{0}}  $$  $$f_1={{1}\choose{0}} $$  $$f_2={{2}\choose{0}}+ {{1}\choose{1}} $$  $$f_3= {{3}\choose{0}}+ {{2}\choose{1}} $$  $$f_4= {{4}\choose{0}}+ {{3}\choose{1}}+{{2}\choose{2}} $$ $$...$$  Generalizing,  $$f_n=\sum_{s+r=n,s\ge r}{{s}\choose{r}}, 0\le s,r \le n $$  How to write the correct formula of n-th term. Why this pattern is coming. I could verify using calculation for upto n=10. How to give a rigorous proof?.
22460
I have been able to figure out the the distinct equivalence classes. Now I am having difficulties proving the relation IS an equivalence relation.   $F$ is the relation defined on $\Bbb Z$ as follows:      For all $(m, n) \in \Bbb Z^2,\ m F n \iff  4 | (m-n)$   equivalence classes: $\{-8,-4,0,4,8\}, \{-7,-3,1,5,9\} \{-6,-2,2,6,10\}$ and $\{-5, -1, 3, 7, 11\}$
111618
Given a set of natural numbers ($\Bbb N$), and the relation $R=\{(a,b)\in\Bbb N^2: 5\mid (2a+3b)\}$. Is $R$ an equivalent relation?   My answer: Yes, because $2a + 3b$ is divisible by $5$, if and only if, $2a + 3b − 5b$ is divisible by $5$.  Is my reasoning right?   If it is not, then how do I prove that this is an equivalent relation?
6930
I was reading a text book and came across the following:  Important Results (This comes immediately after LCM:) If 2 [integers] $a$ and $b$ are given, and their $LCM$ and $HCF$ are $L$ and $H$ respectively, then $L \times H = a \times b$  Can some please help me understand why the above result is true? Thanks in advance.
118439
Given $a, b \in \mathbb{R}$, prove that   $$\frac{|a + b|}{1 + |a + b|} \le \frac{|a|}{1 + |a|} + \frac{|b|}{1+|b|}$$  When does equality hold?  The only useful thing I could get (using the triangle inequality) is:  $$\begin{align}1 + \left|\left(a + \frac{ab}{2}\right) + \left(b - \frac{ab}{2}\right)\right| &amp;\le 1 + \left|a + \frac{ab}{2}\right| + \left|b - \frac{ab}{2}\right|\\ &amp;\le 1 + |a| + |b| + |ab|\\ &amp;=(1 + |a|)(1 + |b|)\end{align}$$  But it seems to be inapplicable! Any ideas?
86628
On my assignment, one of the questions ask to list all equivalence relations on S and count how many are of partial orders.   Let S = {u, v, w}. List all equivalence relations on S. How many of these are also partial orders?   Am I to assume the equivalence relations are the possible combinations of each pair S x S ({}, {{u, u}}, {{u, u}, {u, v}} ...) or should their always be a given relation?
2022
I am trying to prove a formula (for ways of distributing $n$ identical balls among $r$ persons when each person may get any number of balls) ${n+r-1}\choose{r-1}$. But I am not able to prove it. I may be doing something wrong but I am not able to figure out what exactly?  This is what I am doing.  I put $n$ identical balls in a line. Now there are $(n+1)$ spaces/gaps between these $n$ identical things including (left to the leftmost ball and the next to the rightmost ball). So now basically I just need to select any $(r-1)$ gaps from these $(n+1)$ gaps and I will be able to create $r$ groups.   So, my answer is ${n+1}\choose{r-1}$.  But the actual answer to this is ${n+r-1}\choose{r-1}$ as per   I want to know what am I doing wrong? Thanks!
120920
I want to prove that:  $$R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$$  where R is a Ramsey number. In the LHS, there are $k+1$ $3$'s, and in the RHS, there are $k$ $3's$. I really have no clue how to start this proof. Any help is appreciated!
5357
I was thinking if I could prove this relation by arranging the $(s − 1)(t − 1)$ in an $(s − 1) × (t − 1)$ 2-D grid and coloring an edge by color-1 if the two endpoints of the edge are in the same row and by color-2 if the two endpoints of the edge are in the same column. I'm not sure if this method will work, but any other approach would be really helpful.