I can't work out how to prove this equation is true by proof of mathematical
Use mathematical induction to prove that, for $n \ge 3$
$$\sum_{j=3}^n \binom{j-1}{2} = \binom{n}{3}$$
Please help, thanks
Asked
Active
Viewed 62 times
-2
-
An easier combinatorial argument: Count how many three-element subsets there are of $\{1,2,3,\dots,n\}$ 1) Directly 2) By breaking into cases based on the largest element appearing. – JMoravitz Jul 20 '18 at 02:23
-
Related: [Hockey Stick Identity](https://math.stackexchange.com/questions/1490794/proof-of-the-hockey-stick-identity-sum-limits-t-0n-binom-tk-binomn1). – JMoravitz Jul 20 '18 at 02:24
-
Possible duplicate of [Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$](https://math.stackexchange.com/questions/1490794/proof-of-the-hockey-stick-identity-sum-limits-t-0n-binom-tk-binomn1) – JMoravitz Jul 20 '18 at 02:24
-
The original question did ask for you to prove something similar to Hockey-Stick identity. $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$ before this equation – Harry Michael Kirwan Jul 20 '18 at 03:21
-
Some other related posts: [Evaluate $\sum\limits_{k=1}^n k^2$ and $\sum\limits_{k=1}^n k(k+1)$ combinatorially](https://math.stackexchange.com/q/43317) and [Simplify triangular sum of triangular numbers: $\sum_{i=1}^{n}(\frac12i(i+1))$](https://math.stackexchange.com/q/1642906). Also other posts [linked to the latter](https://math.stackexchange.com/questions/linked/1642906) might be of interest. – Martin Sleziak Jul 20 '18 at 08:08
1 Answers
0
Assume $$\sum_{j=3}^n \binom{j-1}{2} = \binom{n}{3}$$ is true. Let's prove $$\sum_{j=3}^{n+1} \binom{j-1}{2} = \binom{n+1}{3}$$ So $$\sum_{j=3}^{n+1} \binom{j-1}{2} = \sum_{j=3}^{n} \binom{j-1}{2} + \binom{n}{2} = \binom{n}{3}+ \binom{n}{2} = \frac{n!}{3!(n-3)!}+\frac{n!}{2!(n-2)!} = \frac{(n+1)!}{3!(n-2)!} = \binom{n+1}{3}$$
Ahmad Bazzi
- 11,929
- 2
- 14
- 29
-
You can't assume true for the original equation, I'm trying to prove that the original equation is true. – Harry Michael Kirwan Jul 20 '18 at 03:18
-
1@HarryMichaelKirwan that's how induction works. You assume that it is true for $n$ and prove that it being true for $n$, implies it is true for $n+1$. You must also prove that it is true for smallest possible value of $n$. In this case that is $n=3$. – Sonal_sqrt Jul 20 '18 at 03:28
-
@HarryMichaelKirwan, I could have told you it is true for $n-1$, then i'd do the same steps to prove it for $n$. Try it yourself !!! – Ahmad Bazzi Jul 20 '18 at 03:31
-
@AhmadBazzi actually yeah my bad sorry, but what I don't understand is where you got the $\binom{n}{2}$ going from $\sum_{j=3}^{n+1} \binom{j-1}{2} $ – Harry Michael Kirwan Jul 20 '18 at 03:33
-
-
@AhmadBazzi Yes I understand now... the ending term of the sum will be that. Thank you – Harry Michael Kirwan Jul 20 '18 at 03:53