# Prove using mathematical induction: $1 \cdot 2 \cdot 3 + \ldots + n \cdot (n+1) \cdot (n+2) = \frac{n(n+1)(n+2)(n+3)}{4}$

So I have the easy stuff done. However, I'm not sure how to go about doing the inductive step with such an awkward proof. :/

Statement: $$1 \cdot 2 \cdot 3 + … + n \cdot (n+1) \cdot (n+ 2) = \frac{n \cdot (n + 1) \cdot (n + 2) \cdot (n +3)}{4} .$$

Base step: $n = 1$: $$0 \cdot (0 + 1) \cdot (0 + 2) + 1 \cdot (1 + 1) \cdot (1 +2) = \frac{ 1 \cdot (1+ 1) \cdot (1 + 2) \cdot (1 + 3) }{4} .$$

$$0 \cdot (0 + 1) \cdot (0 + 2) +1 \cdot (1 + 1) \cdot (1 +2) = 0 + 6 = 6$$

$$\frac{ 1 \cdot (1+ 1) \cdot (1 + 2) \cdot (1 + 3) }{4} = \frac{24}{ 4} = 6 .$$

$$6 = 6.$$

Inductive step:

$n = n + 1$

-
Not to be too picky here, but: there is no part of mathematical induction in which we set $n$ equal to $n+1$! –  Pete L. Clark Sep 16 '11 at 3:13
–  Jonas Meyer Sep 16 '11 at 3:16
Actually, the base case is also not that right. In the left hand side, you are supposed to add $n$ terms starting with $1 \cdot 2 \cdot 3, 2 \cdot 3 \cdot 4$ and so on. So for $n=1$, you should have 1 term; namely, $1 \cdot 2 \cdot 3$. You added a spurious $0 \cdot 1 \cdot 2$ term. Well, I agree that extra term is just $0$, but in some other series, that might not be so and your base case could come out wrong. –  Srivatsan Sep 16 '11 at 3:17
I agree with Jonas. Just divide everything by six, and stare long and hard at Pascal's triangle. –  Jyrki Lahtonen Jul 7 '12 at 12:52

Recommendation 1. Never, ever, write "$n=n+1$". It's just wrong.

Recommendation 2. It's easier if you state the inductive step in two parts: state the induction hypothesis explicitly, then state what you need to prove.

(Recommendation 2 is my strongest recommendation, especially if you are beginning induction and are having some difficulty; it helps organize your thoughts, it helps you keep straight what you are assuming vs. what you want to prove, it helps prevent confusion between the inductive step and the theorem as a whole. It's a chore, perhaps, but I really do strongly recommend doing it).

Recommendation 3. It is often useful to prevent confusion by stating the inductive step using a letter different from what you are trying to prove, so that your "induction hypothesis" doesn't get confused with the theorem to be proven; using a letter that is not being used for anything else can help. (It also prevents writing things that bring such horror to a trained mathematician like "$n=n+1$"...) Here, the statement we are trying to prove uses $n$ for the variable and nothing else. To avoid getting confused, use $k$ for the induction hypothesis and $k+1$ for what you need to prove in the induction hypothesis.

This is purely aesthetical; it plays no mathematical role. It's just a way to prevent possible confusion, and nothing more.

Here, try this:

Inductive step.

Induction hypothesis: The result holds for $k$. That is, we assume that:

$$(1)(2)(3) + (2)(3)(4) + \cdots + (k)(k+1)(k+2) = \frac{k(k+1)(k+2)(k+3)}{4}$$ is true.

To be proven: The result holds for $k+1$; that is, we need to prove that:

$$\small (1)(2)(3) + (2)(3)(4) + \cdots + (k+1)\bigl((k+1)+1\bigr)\bigl((k+1)+2\bigr) = \frac{(k+1)(k+2)(k+3)(k+4)}{4}.$$ is true.

(The above is what I mean by "state the induction hypothesis explicitly, then state what you need to prove)

Okay let's try to prove that the second highlighted statement is true. With induction, we want to bring the Induction Hypothesis into play somehow; usually, by trying to think of the $k+1$ case as being "do the $k$-step and then do something else"; then we can use the induction hypothesis to simplify the "$k$-step". This works very well here.

We have: $$(1)(2)(3) + (2)(3)(4) + \cdots + (k+1)(k+2)(k+3).$$ In order to think about it as "the $k$-step and then a bit more", let's write the the $k$th summand as well as the $k+1$st: $$(1)(2)(3) + (2)(3)(4) + \cdots + k(k+1)(k+2)+ (k+1)(k+2)(k+3).$$ Now, we can do the sum by first adding the first $k$ summands, and then adding $(k+1)(k+2)(k+3)$ to the result of that; so the entire sum we have is equal to: $$\Biggl( (1)(2)(3)+(2)(3)(4)+\cdots+k(k+1)(k+2)\Biggr) + (k+1)(k+2)(k+3).$$ Now, we may realize that the stuff inside the big parenthesis is precisely the sum about which the Induction Hypothesis tells us something. The Induction Hypothesis says that: $$(1)(2)(3) + (2)(3)(4) + \cdots + (k)(k+1)(k+2) = \frac{k(k+1)(k+2)(k+3)}{4},$$ so we can replace that first parenthetical expression with $\frac{k(k+1)(k+2)(k+3)}{4}$. So, in summary, we have: \begin{align*} (1)(2)(3) &+ (2)(3)(4) + \cdots + k(k+1)(k+2)+ (k+1)(k+2)(k+3)\\ &=\Biggl( (1)(2)(3)+(2)(3)(4)+\cdots+k(k+1)(k+2)\Biggr) + (k+1)(k+2)(k+3)\\ &= \Biggl(\frac{k(k+1)(k+2)(k+3)}{4}\Biggr) + (k+1)(k+2)(k+3) \end{align*} with the first equality being just by associativity of the sum; and the second equality justified because we have applied the induction hypothesis.

That is, we have simplified the sum of the first $k$ terms through the use of the induction hypothesis.

Can you take it from here?

-
+1: Arturo, your ability to crank out these high quality answers nearly instantaneously is amazing "even" to me... –  Pete L. Clark Sep 16 '11 at 3:15
Here is a more random comment: I see that you endorse "switching from $n$ to $k$" in induction proofs, as is quite commonly done. I can never bring myself to do this, which means that I often get asked questions like "Is it okay that I used $k$ instead of $n$?" My somewhat crotchety position on this is that if you think you need to switch the name of the "dummy" variable then you haven't fully understood the logic of induction. (Also, what happens when there is also a $k$ in $P(n)$, e.g. when working with binomial coefficients??) What do you think about this? –  Pete L. Clark Sep 16 '11 at 3:19
@Pete: Thank you very much. To quote Faramir in "The Two Towers",'praise from the praiseworthy is beyond all rewards.' –  Arturo Magidin Sep 16 '11 at 3:23
@Pete: I recommend switching to a letter not being used only to prevent confusion between the statement of the theorem we are proving, the induction hypothesis, and what you need to prove; I should say that explicitly, though. My main and strongest recommendation for beginning students, though, is Recommendation 2: write out what your induction hypothesis is explicitly and have it handy; then write out explicitly what you are trying to prove, and have it handy. Then go on to prove it. But I certainly agree that if you think you have to change it, then you didn't really "get it". –  Arturo Magidin Sep 16 '11 at 3:27
Thanks guys. I appreciate the response. However your response could've had a little more clarification on your last equation, iit was confusing how you got there. Thanks though for the help! –  oorosco Sep 16 '11 at 4:03

For the record, the "correct" way to prove this identity is combinatorially. Written differently (after dividing both sides by $6$), it reads

$$\sum_{k=3}^{n+2} \binom{k}{3} = \binom{n+3}{4}.$$

This is because each $4$-subset of $[n+3]$ is composed of its maximum $k+1$ and a $3$-subset of $[k]$.

-

$$1 \cdot 2 \cdot 3 + \cdots + n(n+1)(n+2) = \frac{n(n + 1)(n + 2)(n + 3)}{4}.$$

Step 1: (Must prove that the given relation is true for $n=1$)

$$p(1): 1\cdot 2\cdot 3=\frac{1\cdot (1+1)\cdot (1+2)\cdot(1+3)}{4} \Rightarrow 1\cdot 2\cdot 3= 1\cdot 2\cdot 3.$$

The base case is true.

Step 2: Suppose thaat the given relation is valid for $n=k$.

$$p(k): 1\cdot 2 \cdot 3 + \cdots + k(k+1)(k+2) = \frac{k(k + 1)(k + 2)(k +3)}{4}.$$

Step 3: Now we must prove that the given relation is correct for $n=k+1$.

$$p(k+1): 1\cdot 2 \cdot 3 + \cdots + (k+1)(k+2)(k+3) = \frac{(k+1)(k+2)(k + 3)(k +4)}{4}.$$

The above relation can be written:

$$\underbrace{1\cdot 2 \cdot 3 + \cdots + k(k+1)(k+2)} + (k+1)(k+2)(k+3) = \frac{(k+1)(k + 2)(k + 3)(k +4)}{4}.$$

The underlined partion in fact is the step 2. So we have \begin{align*} & 1\cdot 2 \cdot 3 + \cdots + k(k+1)(k+2) + (k+1)(k+2)(k+3) \\ & = \frac{k(k + 1)(k + 2)(k +3)}{4} + (k+1)(k+2)(k+3) \\ & = \frac{k(k+1)(k+2)(k+3) + 4(k+1)(k+2)(k+3)}{4} \\ & = \frac{(k+1)(k+2)(k+3)(k+4)}{4}. \end{align*}

-
-1. Duplicates previous answer and errs seriously in using implications. –  Did Jul 15 '12 at 6:27