Discrete math induction problem.

Question

I am stuck at this step in the inductive process and I was wondering if someone can help me out from where I am stuck.

Question:

if $n$ is a positive integer, prove that,

$$1\cdot2+2\cdot3+3\cdot4+\cdots+n\cdot(n+1) = \frac{n(n+1)(n+2)}3$$

Basic step is $1$, then assume $k$ is true and we get,

$$1\cdot2+2\cdot3+3\cdot4+\cdots+k\cdot(k+1) = \frac{k(k+1)(k+2)}3$$

After that I am stuck because the answer key is telling me that the next step is to add $(k+1)(k+2)$, but I don't know why we do that. Aren't we supposed to just plugin $k+1$ into all $k$ variables. Why are we adding $(k+1)(k+2)$ to both sides?

Answer 1

So we want to prove that

$$1\cdot2+2\cdot3+3\cdot4+\cdots+n(n+1)=\sum_{i=1}^{n}{i(i+1)}=\frac{n(n+1)(n+2)}{3}\forall n\in\mathbb{N}$$

The base case ($n=1$):

Note that $1\cdot2=2$ and that $\frac{1\cdot2\cdot3}{3}=2$. Thus the base case holds.

Suppose that $\exists k\in\mathbb{N}$ such that $\sum_{i=1}^{k}{i(i+1)}=\frac{k(k+1)(k+2)}{3}$. Now consider the case that $n=k+1$:

$$\sum_{i=1}^{k+1}{i(i+1)}=(n+1)(n+2)+\sum_{i=1}^{k}{i(i+1)}$$.

By the induction hypothesis (we claimed that for $n=k$ the formula held) we have:

$$\sum_{i=1}^{k+1}{i(i+1)}=(k+1)(k+2)+\frac{k(k+1)(k+2)}{3}=\frac{k^3+6k^2+11k+6}{3}=\frac{(k+1)(k+2)(k+3)}{3}$$

Therefore, by induction, the formula is true $\forall n\in\mathbb{N}$

Answer 2

Finishing up the induction proof,\begin{align} 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + (k+1)(k+2) &= [1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + k(k+1)]+(k+1)(k+2) \\ &= \frac{k(k+1)(k+2)}{3}+(k+1)(k+2) \\ &= \frac{k(k+1)(k+2)}{3}+\frac{3(k+1)(k+2)}{3} \\ &= \frac{k(k+1)(k+2)+3(k+1)(k+2)}{3} \\ &= \frac{(k+1)(k+2)(k+3)}{3} \end{align} where the last equality is by hypothesis. Now simplify the last expression accordingly and you will get your result.

Answer 3

Based on hypothesis: $$\sum_{i=1}^{k}i\left(i+1\right)=\frac{1}{3}k\left(k+1\right)\left(k+2\right)$$ it must be shown that: $$\sum_{i=1}^{k+1}i\left(i+1\right)=\frac{1}{3}\left(k+1\right)\left(k+2\right)\left(k+3\right)$$ Here $k+1$ is 'plugged in' for $k$.

That is the inductionstep. How to do that? Well, $$\sum_{i=1}^{k+1}i\left(i+1\right)=\sum_{i=1}^{k}i\left(i+1\right)+\left(k+1\right)\left(k+2\right)=\frac{1}{3}k\left(k+1\right)\left(k+2\right)+\left(k+1\right)\left(k+2\right)$$ (in the last equality you are using the hypothesis)

So if you can show that the RHS of this indeed equals: $$\frac{1}{3}\left(k+1\right)\left(k+2\right)\left(k+3\right)$$ then you are ready. Working out the RHS comes to adding $(k+1)(k+2)$ to $\frac{1}{3}k\left(k+1\right)\left(k+2\right)$.

Answer 4

You suppose that your formula is true for $k$ and prove that it is true for $(k+1)$. That is, suppose that: $$ 1\times2+\cdots+k\times(k+1)=\dfrac{k(k+1)(k+2)}{3}, $$ and prove for $(k+1)$: $$ 1\times2+\cdots+k\times(k+1)+(k+1)\times(k+2)=\dfrac{(k+1)(k+2)(k+3)}{3}. $$

Note that by assumption you have:

$$ 1\times2+\cdots+k\times(k+1)=\dfrac{k(k+1)(k+2)}{3}. $$

Hence: $$ \begin{equation} \begin{split} 1\times2+\cdots+(k+1)\times(k+2)&=\dfrac{k(k+1)(k+2)}{3}+(k+1)\times(k+2)\\&=\dfrac{k\color{red}{(k+1)(k+2)}+3\color{red}{(k+1)(k+2)}}{3}\\&=\dfrac{\color{red}{(k+1)(k+2)}(k+3)}{3}.\mathrm{QED} \end{split} \end{equation} $$

Answer 5

Hint $\: $ It is very easy to inductively prove the following basic theorem on additive telescopy

$$\rm\ g(n)\ =\, \sum_{i\: =\: 1}^n\:\ f(i)\ \iff\ \ g(n) - g(n\!-\!1)\ =\ f(n)\ \ for\ \ n> 1,\,\ \ g(1)=f(1)$$

Your is special case $\rm\ f(n) = n(n\!+\!1),\ \ g(n) = n(n\!+\!1)(n\!+\!2)/3,\, $ which is easily checked to satisfy the above. Indeed, $\rm\,g(n)-g(n\!-\!1) = n(n\!+\!1)((n\!+\!2)-(n\!-\!1))/3 = n(n\!+\!1)\ $ and $\rm\ g(1) = f(1) $

The inductive proof of the general theorem is easier than that for your special case because the cancellation that occurs is much more obvious at this level of generality, whereas it is usually obfuscated by details of specific instances. Namely, the proof of the general theorem is just a rigorous inductive proof of the following telescopic cancellation

$$\rm \underbrace{\overbrace{g(1)}^{\large f(1)}\phantom{-g(1)}}_{\large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{-\,g(1)\!+\!\phantom{g(2)}}^{\large f(2)}\!\!\!\!\!\!\!\!\! \underbrace{g(2) -g(2)}_{\large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\phantom{-g(2)}+ g(3)}^{\large f(3)}\!\!\!\!\!\!\!\!\!\!\underbrace{\phantom{g(3)}-g(3)}_{\large =\ 0}\!+\:\cdots +\!g(n)\ =\ g(n) $$

This theorem reduces the inductive proof to simply verifying the RHS equalities, which is trivial polynomial arithmetic when $f(n),g(n)$ are polynomials in $n$. The above theorem is an example of telescopy, also known as the Fundamental Theorem of Difference Calculus, depending on context. You can find many more examples of telescopy and related results in other answers here.

Answer 6

I see lot's of good math here, but your repeated question of "Why are we adding (k+1)(k+2)?" leads me to believe you're looking for something a little different. (Of course, I could be completely wrong. If so, then pardon my rambing here.)

Try this:

Induction proofs often start with a formula that looks like

EQ $1.$ $\ $ term$_1$ + term$_2$ + ... + term$_n$ = $f(n)$

where $f(n)$ is a relatively simple function of $n$. We prove true for $1$, which is usually trivial, then assume it holds for $k$, so we have

EQ $2.$ $\ $ term$_1$ + term$_2$ + ... + term$_k$ = $f(k)$

Then we're supposed to prove it's true for $k+1$. OK, here's what no one is explicitly telling you. When you want to prove it's true for $k+1$, we take advantage of the fact that we know what those terms that make up the left-hand side of EQ $1$ look like, and that if we add the $k+1$ term to both sides of EQ $2$, then the new left-hand side looks like the first half of what we're trying to prove:

$\ $ term$_1$ + term$_2$ + ... + term$_k$ + term$_{k+1}$ = $f(k)$ + term$_{k+1}$

So, if we can do the algebra and rearrange that right hand side so it looks like $f(k+1)$ is supposed to , then we've got our proof. Here's where you plug $k+1$ into $f()$, to see what you're trying to manipulate that right-hand side to look like. If we can use algebra (or some other method) to show that

$f(k)$ + term$_{k+1} = f(k+1)$

then we've shown that adding the $k+1$ term makes the sequence equal to $f(k+1)$, which is what it means for the formula to be "true" for $k+1$.

Once you understand this, then the real trick to any of these is finding the right cool algebra trick to rearrange $f(k)$ + term$_{k+1}$ to get what you want, which is why so many of the answers you're getting focus on that aspect. It's the common question implied when someone says they don't get a particular induction proof.

(Note: This is a simple model with additive terms. Sometimes the pattern on the left is more complex and you have to figure out what you have to do to both sides to get from the $k$ to the $k+1$ case.)

(Also Note: This is just a verbose and somewhat less generalized case of what some of the above answers already say. However, I find that often students don't translate the symbology as readily as we "experts" (heh), especially in the early stages of learning a new concept, so I thought one more exposition from another tact might help.)