Proof via induction $1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$

Question

(b) Prove that for every integer $n \ge 1$, $$1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$$

This is the second part of a two part question. Part (a) was the following: Write the sum: $1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2)$ using summation notation.

It was simple enough : $\sum k(k+2)$.

For this question, the base case $(n=1)$ holds, as $1\cdot(1+2) = 3 = (1\cdot2\cdot9)/6$.

Induction step: Assume the above holds for all $n = k$, prove that it holds for all $n = k+1$

I'm a bit lost from here, help?

Answer 1

Begin with $$\frac{n(n+1)(2n+7)}{6} = \sum^n_{i=1}n(n+2)$$ and then add $(n+1)(n+3)$ to both sides and try to rewrite the left side in form $$\frac{(n+1)(n+2)(2(n+1)+7)}{6}.$$

Answer 2

The sum for $k+1$ is

$$\sum_{j=1}^{k+1} j(j+2) = \sum_{j=1}^{k} j(j+2) + (k+1)(k+3) = \frac{k(k+1)(2k+7)}{6} + (k+1)(k+3).$$

Expand this out and notice it equals the wanted expression for $k+1$ i.e. $\frac{(k+1)(k+2)(2(k+1)+7)}{6}$. (By expanding them both out, it's ease to see they're the same. I used Wolfram Alpha to check it, but it isn't that big of a job in this case, just $3$rd degree polynomial.)

Answer 3

Part I: Big picture

The $\color{green}{\text{ess}}\color{blue}{\text{ence}}$ of the inductive proof is additive telescopy, which shines through when we view the problem in a more general setting.

Prove the following by induction: $$\sum_{k=n_0}^{n}f(k) = g(n) \text{ for } n \ge n_0$$

Base case: Show that $\color{green}{f(n_0) = g(n_0)}$

Inductive step:

1. Assume true for $n$, that is $\sum_{k=n_0}^{n}f(k) = g(n)$.
2. Show that $\color{blue}{f(n+1) = g(n+1) - g(n)}$

This will imply that the statement is true for $n+1$, since $$\begin{align}\sum_{k=n_0}^{n+1}f(k)=\sum_{k=n_0}^{n}f(k) + f(n+1) = \underbrace{g(n)}_{\text{from }1} + \underbrace{g(n+1) - g(n)}_{\text{from }2} = g(n+1)\end{align}$$

and it completes the proof by induction.

Remark: Notice how it gives us a straightforward algorithm to solve induction problems of this type. We just have to concentrate on proving two equalities (highlighted in $\color{green}{\text{co}}\color{blue}{\text{lor}}$ above), and the mechanics of the procedure takes care of the rest.

---

Part II: Small picture

In the given problem, we have $f(k) = k(k+2), g(n) = n(n+1)(2n+7)/6 \text{ and } n_0 = 1$, and the induction proof goes thus:

Base case: $\color{green}{f(1)} = 3 = \color{green}{g(1)}$

Inductive step:

1: Assume true for $n$, that is $\sum_{k=1}^{n}f(k) = g(n)\tag{1}$

2: Let $m = n+1$

$\begin{align}f(m) &= m(m+2) =m^2 + 2m\\\\ g(m) - g(m-1) &= m(m+1)(2m+7)/6 - (m-1)(m)(2m+5)/6\\&=m(2m^2 + 9m + 7 - 2m^2 - 3m + 5)/6\\&=m(6m+12)/6 \\&= m^2 + 2m\\\\\therefore f(m) &= g(m) - g(m-1)\\\text{i.e } \color{blue}{f(n+1)}&=\color{blue}{g(n+1) - g(n)}\tag{2}\end{align}$

We thus have $$\begin{align}\sum_{k=1}^{n+1}f(k)=\sum_{k=1}^{n}f(k) + f(n+1) = \underbrace{g(n)}_{\text{from }(1)} + \underbrace{g(n+1) - g(n)}_{\text{from }(2)} = g(n+1)\end{align}$$

implies that the statement is true for $n+1$.

Answer 4

Assume result is true for $n=k$ i.e. $$S_k=\frac {k(k+1)(2k+7)}6$$ Then, adding the next term gives: $$\begin{align} S_{k+1}&=S_k+(k+1)(k+2)\\ &=\frac {k(k+1)(2k+7)}6+(k+1)(k+3)\\ &=\frac{k+1}6 \left( k(2k+7)+6(k+3)\right)\\ &=\frac{k+1}6\left( 2k^2+13k+18\right)\\ &=\frac{(k+1)(k+2)(2k+9)}6\\ &=\frac{(\overline{k+1})(\overline{k+1}+1)(2\overline{k+1}+7)}6\\ \end{align}$$

i.e. result is also true for $n=k+1$.

As shown in the question, the result is true for $n=1$.

Hence, by induction, the result is true for all positive integer $n$.

Answer 5

Note that $$ k(k + 2) = k^2 + 2k = k^2 - k + 3k = 2{k \choose 2} + 3{k \choose 1} $$ Definition 1: Let $\{x_n\}$ a sequence. $\Delta x_n = x_{n+1} - x_n$.

Definition 2: If $\Delta X_n = x_n$, then $X_n = \Delta^{-1}x_n + C$ with $C \in \mathbb{R}$.

Proposition 1: $\Delta^{-1}$ is linear and

$$ \Delta \biggl(\sum_{k =n_0}^{n-1}x_k \biggr) = x_n \quad \text{and} \quad \Delta {n \choose p} = {n \choose p - 1} $$ Proof. Exercise.

Proposition 2: $\sum_{k =m}^{n-1}x_k = \Delta^{-1}x_n\biggl|_{m}^{n} = X_n - X_m$.

Proof. Exercise.

Proposition 3: $\Delta^{-1}{n \choose p} = {n \choose p+1} + C$.

Proof. Exercise.

Thus, $$ \sum_{k=1}^{n}k(k+2) = \sum_{k=1}^{n}\biggl[2{k \choose 2} + 3{k \choose 1}\biggr] = \biggl[2{k \choose 3} + 3{k \choose 2}\biggr]_{1}^{n+1} $$ $$ = 2{n+1 \choose 3} + 3{n+1 \choose 2} = \dfrac{1}{3}(n+1)n(n-1) + \dfrac{3}{2}(n+1)n $$ $$ =n(n+1)\biggl[\dfrac{n}{3} - \dfrac{1}{3} + \dfrac{3}{2}\biggr] = \dfrac{n(n+1)(2n+7)}{6} $$