1
$\begingroup$

Prove that ${{n+1}\choose 3}-{{n-1}\choose 3}=(n-1)^2.$

I found the algebraic proof of the above statement. So we have to show that $$ \frac{(n+1)(n)(n-1)}{3\times 2}-\frac{(n-1)(n-2)(n-3)}{3\times 2} \stackrel{?}{=} (n-1)(n-1)$$ $$\implies \frac{(n+1)(n)}{3\times 2}-\frac{(n-2)(n-3)}{3\times 2} \stackrel{?}{=} (n-1) $$$$ \implies (n+1)n-(n-2)(n-3)\stackrel{?}{=}3 \times 2 (n-1), $$ which is true and we are done!

But I couldn't get the combinatorial proof. Any hints?

$\endgroup$
4
  • 1
    $\begingroup$ You say "THE combinatorial proof", do you know for sure there is one ? $\endgroup$ Jun 13 at 7:19
  • $\begingroup$ Actually, this problem was given as exercise in problem-solving methods in combinatorics, so I thought there is, but not sure. $\endgroup$ Jun 13 at 7:25
  • $\begingroup$ There is a combinatorial proof for sure, I can guarantee that. I had done it years ago, so I do not exactly remember it, but will let you know if it strikes again. $\endgroup$ Jun 13 at 7:43
  • $\begingroup$ @SunainaPati , even though I have given an answer, I am sorry it is not a hint, coz the hint in this case would just give away the problem, rest is just computation. You can just read the first para if you wanna do the computation yourself $\endgroup$ Jun 13 at 7:49
5
$\begingroup$

Yes, the proof is as follows, (I had done the same problem a few days back from the same book lol); Notice LHS is just number of ways to choose a team of $3$ ppl from $n+1$, where out of two people (say Pranjal and Rohan) one has to be in the team. So just break it into a few cases now,

Pranjal is in, Rohan is not : $\binom{n-1}{2}$

Rohan is in, Pranjal is not: $\binom{n-1}{2}$

Both are in : $\binom{n-1}{1} \ \ \ \ $(btw, this is the only case that is possible in the real world) (imo gold orz)

Add 'em and get the required result.

$\endgroup$
5
  • 2
    $\begingroup$ Niceee this works! Thanks ! And reading the first para is nice hint itself! Also rg and pranjal bhaiya :joy: $\endgroup$ Jun 13 at 8:04
  • $\begingroup$ also i think, there's a typo, u should write either of "pranjal or rg are must be in team." $\endgroup$ Jun 13 at 8:37
  • $\begingroup$ @SunainaPati , yes you are right, I don't know why I wrote the complement of the set, thanks! (btw sorry for the late response). Also, I just wanted to ask you a question, currently, I am really weak at combinatorics, I tried Pablo's book but after I saw IMO 2009/6 as one the first examples, I stopped doing that :( and Pranav's book is too tough rn... Could you please suggest a book (not OTIS excerpts) that might be useful for me? Thanks! $\endgroup$ Jun 15 at 16:56
  • $\begingroup$ I am too doing pablo! IMO 2009/6 isn't scary and the solution in the book is great and easy to understand. I heard combinatorics by murlidharan is great too! $\endgroup$ Jun 16 at 10:24
  • $\begingroup$ @SunainaPati oh, thanks. that book is really hard (read:impossible) to find lol. Also, IMO 2009/6's solution is prolly not very hard to understand (i havent seen it yet) but the tough part is to find it lol :( ! $\endgroup$ Jun 17 at 19:15
1
$\begingroup$

I would use Pascal's identity to get $$\binom{n+1}{3}-\binom{n-1}{3} = \left[\binom{n+1}{3} - \binom{n}{3}\right] + \left[\binom{n}{3}-\binom{n-1}{3}\right] = \binom{n}{2} + \binom{n-1}{2}.$$ This can be solved algebraically: $$\binom{n}{2} + \binom{n-1}{2} = \frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{2} = \frac{(n-1)[(n-2)+n]}{2} = (n-1)^{2}.$$ I'm shocked I figured this out so fast. Sometimes you just see the solutions when you read the problem and sometimes you get stuck on a wrong path. It's just the story of math :)

$\endgroup$
2
  • $\begingroup$ Really nice! Learnt something new.. $\endgroup$ Jun 13 at 7:40
  • 2
    $\begingroup$ The OP is asking for a combinatorial proof - your answer is certainly not that. $\endgroup$ Jun 13 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.