2

Show that the number of triples that can be chosen from $n$ items is precisely $$\frac{n(n−1)(n−2)}{6}.$$

Suppose n = k+1,

We want $\frac{(k+1)k(k-1)}{6}$ therfore,

$\frac{k(k-1)(k-2)}{6}$ + (k+1)

and then solve the rest.

What am I doing wrong here?

Mark
  • 335
  • Your LHS isn't a generic $n$; it's specifically of the form $k(k-1)/2$ - the sum is the sum of the first $k$ triangular numbers. – Steven Stadnicki Jan 22 '14 at 01:38
  • What exactly is your general sum? It's not exactly clear to me. – Cameron Williams Jan 22 '14 at 01:41
  • @Steven How would you be able to derive that from the pattern above? Is it just trial and error until you get that form? – Mark Jan 22 '14 at 01:41
  • @mark I recognize the numbers on past instinct - '1, 3, 6' is a familiar sequence. Without that, and assuming you had one more term (10) to work with, I'd look at the first differences: (1-0)=1, 2, 3, 4, ... - and then realize what was going on. Generally, though, it will be clear from context; where did you get this question from, and (if it was an external source) what was the exact text of it? – Steven Stadnicki Jan 22 '14 at 01:43
  • 1
    It looks like the problem statement should be $$1+3+6+\cdots+\frac{n(n+1)}{2}=\frac{n(n+1)(n+2)}{6}.$$ – Jeff Snider Jan 22 '14 at 02:34
  • @JeffSnider No, the question I was working on states "Show that the number of triples that can be chosen from n items is precisely $\frac{n(n-1)(n-2)}{6}$. Use mathematical induction." – Mark Jan 22 '14 at 02:36
  • @StevenStadnicki with the form you provided, the base case for the LHS doesn't equal the RHS when n=3. – Mark Jan 22 '14 at 02:40
  • In that case, $n=3$ is your base case and induction holds. You can apply my answer below without much alteration. – Jeff Snider Jan 22 '14 at 02:43
  • @JeffSnider How?

    I've tried

    when n=3

    $\frac{3(2)}{2}$ = $\frac{3(2)(1)}{6}$

    Which doesn't hold true.

     – Mark Jan 22 '14 at 02:47
  • @JeffSnider never mind, I see you changed it to n greater than or equal to 1. – Mark Jan 22 '14 at 02:52
  • The sum you're looking for is $0+0+1+3+6+\cdots+\frac{n(n-1)}{2}$, which is the number of new triples that can be picked by adding the $n$-th item. I.e., the number of triples that can be picked which include item $n$: that's $n \text{ choose } 2=\frac{n(n-1)}{2}$. – Jeff Snider Jan 22 '14 at 02:52
  • @JeffSnider This doesn't make any sense, I tried this n=1, both sides equal zero. Then I tried this with n=2, now they don't equal. – Mark Jan 22 '14 at 02:55
  • I was off-by-one: should be $\frac{(n-1)(n-2)}{2}$. I corrected my edit of the question. – Jeff Snider Jan 22 '14 at 02:59
  • @JeffSnider its still wrong. I'm not getting $\frac{(k-1)k(k+1)}{6}$ by induction based on your form of $\frac{(n-1)(n-2)}{2}$ – Mark Jan 22 '14 at 03:10
  • Is there anyone here who can help? – Mark Jan 22 '14 at 03:24
  • Stop looking at your $k$ equation. Look at the answer I wrote below. Simply subtract 2 from each $n$ and it will show what you need. – Jeff Snider Jan 22 '14 at 12:54
  • @JeffSnider I get $\frac{(n-1)(n-2)(n-3)}{6}$ which isn't what I want. I need $\frac{(n+1)(n)(n-1)}{6}$ – Mark Jan 22 '14 at 18:58
  • You should get: Assume for any $n-1$ we have that the sum holds: $$0+0+1+3+6+\cdots+\frac{(n-3)(n-2)}{2}=\frac{(n-3)(n-2)(n-1)}{6}$$ ... then ... $$...\text{stuff}...=\frac{(n-2)(n-1)n}{6}.$$ – Jeff Snider Jan 22 '14 at 21:05
  • @JeffSnider but that's not the claim. You cannot change the claim being asked in the question. The claim should be: the number of triples that can be chosen from N items = $\frac{N(N-1)(N-2)}{2}$ for $n\geq 3$ – Mark Jan 22 '14 at 23:26
  • Then start the base case from there. – Mark Jan 22 '14 at 23:27

1 Answers1

2

I will show how to prove $$1+3+6+\cdots+\frac{n(n+1)}{2}=\frac{n(n+1)(n+2)}{6}.$$

For $n=1$ we have $1=\frac{1\cdot2\cdot3}{6}=1$, so the base case holds.

Assume for any $n-1$ we have that the sum holds: $$1+3+6+\cdots+\frac{(n-1)n}{2}=\frac{(n-1)n(n+1)}{6}.$$ We need to show that by adding the next term $\frac{n(n+1)}{2}$ to the left and right hand sides the equality still holds. For the LHS it's obvious. For the RHS, in detail: $$\frac{(n-1)n(n+1)}{6}+\frac{n(n+1)}{2}=\frac{(n-1)n(n+1)+3n(n+1)}{6}=\frac{(n-1+3)n(n+1)}{6}=\frac{n(n+1)(n+2)}{6}.$$ Hopefully you see how to apply this to the proof you need. (Hint: subtract 2 from each $n$.)

Jeff Snider
  • 2,817