0

Prove by induction that for $1 \le n$:

$$\sum_{k=1}^n k(k + 1)(k + 2) = 6 + 24 + . . . + n(n + 1)(n + 2) = \frac 14 n(n + 1)(n + 2)(n + 3) $$

Basis step:

I got $n(1) = 6$ and $n(2) = 30 \ (24 + 6 = 30)$

Assumption:

$n = k$

$$\frac 14 k(k + 1)(k + 2)(k + 3) $$

$n = k + 1$

$\frac 14 (k + 1)((k + 1) + 1)((k + 1) + 2)((k + 1) + 3) = \frac 14(k + 1)(k + 2)(k + 3)(k + 4)$ <- This is what I'm suppose to get after my induction .

I'm still confused about induction so I don't really know the next step to take on this problem.

BigbearZzz
  • 15,084
milkbread
  • 45

4 Answers4

2

From the inductive hypothesis we have \begin{align} \sum_{j=1}^{n+1}j(j+1)(j+2)&=\sum_{j=1}^{n}j(j+1)(j+2)+(k+1)(k+2)(k+3)\\[4pt] &=\color{red}{\frac{1}{4}k}(k+1)(k+2)(k+3)+\color{blue}{1}\cdot(k+1)(k+2)(k+3)\\[4pt] &=\left(\color{red}{\frac{1}{4}k}+\color{blue}{1}\right)(k+1)(k+2)(k+3)\\ &=\frac{1}{4}(k+1)(k+2)(k+3)(k+4) \end{align}

Ángel Mario Gallegos
  • 19,882
2

You have understood the general idea but the way it is written isn't proper.

The question is to prove by induction that $$\sum_{k=1}^{n} k(k+1)(k+2) = \dfrac{1}{4} n(n+1)(n+2)(n+3)$$

It would be better to write it like this -

When $n=1$ both LHS and RHS are equal to 6

Let us assume that the equation is true for $n=l$. Then we need to show the equality at the stage $n=l+1$ $$ \sum_{k=1}^{l+1} k(k+1)(k+2) = \left(\sum_{k=1}^{l} k(k+1)(k+2) \right)+ (l+1)(l+2)(l+3) $$

Now apply the induction hypothesis at the $l^{\text{th}}$ stage to get $$ \sum_{k=1}^{l+1} k(k+1)(k+2) = \dfrac{1}{4}l(l+1)(l+2)(l+3) + (l+1)(l+2)(l+3) = \dfrac{1}{4}(l+1)(l+2)(l+3)(l+4)$$

Thus by induction you are done

R_D
  • 7,312
1

You assume

$$\sum_{k=1}^n k(k + 1)(k + 2) = \frac14 n(n + 1)(n + 2)(n + 3)$$

for a very specific $n$.

Therefore:

$$\begin{align} \sum_{k=1}^{n+1}k(k + 1)(k + 2) &= \left[\sum_{k=1}^nk(k + 1)(k + 2)\right] + (n+1)(n+1 + 1)(n+1 + 2)\\ &=\left[\frac14 n(n + 1)(n + 2)(n + 3)\right] + (n+1)(n+1 + 1)(n+1 + 2) \end{align}$$

and you have to prove that that is equal to:

$$\frac14 (n+1)(n+1 + 1)(n+1 + 2)(n+1 + 3)$$

This will show that if the condition is true for $n$, it is true for $n+1$.

grg
  • 1,017
fleablood
  • 124,253
1

Induction is a method to prove something over a countable set. In this case, you want to prove some claim for all natural numbers $n \geq 1$. So how would you approach about proving something for all those numbers?

Imagine all the different $n$ values satisfying $n \geq 1$ are dominoes. The domino falls if the statement is true for that $n$. How could you show that all the dominos will fall? Well, consider these two statements:

  1. The first domino falls
  2. Given that some nth domino falls, the (n+1)th domino will fall

Do you see how if you could prove these two statements true, then you have proven that all the dominoes will fall? This is how induction works.

Now for your base case, you need to show that "the first domino falls." If you plug in 1 to both sides, you see that they both equal 6.

For the second step, assume that the claim you are trying to prove holds for some $n \geq 1$. Namely, assume that $\sum_{k=1}^{n} k(k+1)(k+2) = \frac{1}{4}(n)(n+1)(n+2)(n+3)$. Then, we need to use this assumption to show that $\sum_{k=1}^{n+1} k(k+1)(k+2) = \frac{1}{4}(n+1)(n+2)(n+3)(n+4)$.

A trick to simplifying these things is to use the property of summations on the left side. In particular, $\sum_{k=1}^{n+1} k(k+1)(k+2) = \sum_{k=1}^{n} k(k+1)(k+2) + (n+1)(n+2)(n+3)$. By our assumption earlier, this equals $\frac{1}{4}(n)(n+1)(n+2)(n+3) + (n+1)(n+2)(n+3) = (\frac{1}{4}n + 1)(n+1)(n+2)(n+3) = \frac{1}{4}(n+1)(n+2)(n+3)(n+4)$.

By the principle of mathematical induction, we have shown that the statement is true for all $n \geq 1$.

nivekgnay
  • 653