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?
Best Answer
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.