4
$\begingroup$

I am doing mathematical induction. I am stuck with the question below. The left hand side is not getting equal to the right hand side. Please guide me how to do it further.

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

Sol:

$P(n):\ 1\cdot 3 + 2\cdot 4 + 3\cdot 5 + \cdots + n(n+2) = \frac{1}{6}n(n+1)(2n+7)$.

$P(1):\ \frac{1}{6}(2)(9) = \frac{1}{2}(2)(3)$.

$P(1): 3$.

Hence it is true for $n=n_0 = 1$.

Let it be true for $n=k$.

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

We have to prove

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

Taking LHS: $\begin{align*} 1\cdot 3 + 2\cdot 4+\cdots + (k+1)(k+2) &= 1\cdot 3 + 2\cdot 4 + \cdots + k(k+2) + (k+1)(k+3)\\ &= \frac{1}{6}(k+1)(k+2)(2k+9) + (k+1)(k+3)\\ &= \frac{1}{6}(k+1)\left[(k+2)(2k+9) + 6k+18\right]\\ &= \frac{1}{6}(k+1)\left[2k^2 + 13k + 18 + 6k + 18\right]\\ &= \frac{1}{6}(k+1)\left[2k^2 + 19k + 36\right]. \end{align*}$

  • 0
    See also: http://math.stackexchange.com/questions/785355/proof-via-induction-1-cdot3-2-cdot4-3-cdot5-cdots-nn2-fracnn12015-07-27

3 Answers 3

3

As I understand it you are trying to show that for $n\geq 1$:

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

You first showed it for $n=1$:

$ 3=1\cdot 3=\frac{1}{6}(1)(2)(9)=3 $

Now we assume that the formula holds for some $n\geq 1$ and we have the statement for $n+1$

$ 3\cdot 1+\cdots +n(n+1)+(n+1)(n+3). $

By induction hypothesis the sum of the first $n$ terms is $\frac{1}{6}n(n+1)(2n+7)$. So

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

We may factor out an $n+1$ to get

$ \frac{1}{6}n(n+1)(2n+7)+(n+1)(n+3)=(n+1)\left(\frac{1}{6}n(2n+7)+n+3\right). $

Then factor out a $\frac{1}{6}$ to get

$ \frac{1}{6}(n+1)(n(2n+7)+6n+18)=\frac{1}{6}(n+1)(2n^2+7n+6n+18). $

Finally,

$ \frac{1}{6}(n+1)(2n^2+7n+6n+18)=\frac{1}{6}(n+1)(n+2)(2(n+1)+7). $

  • 0
    @Ragib Zaman: No bother.2011-11-11
12

HINT $\: $ First trivially inductively prove the Fundamental Theorem of Difference Calculus

$\rm\ F(n)\ =\ \sum_{i\: =\: 1}^n\:\ f(i)\ \ \iff\ \ \ F(n) - F(n-1)\ =\ f(n),\quad\ F(0) = 0$

Your special case now follows immediately by noting that

$\rm\ F(n)\ =\ \dfrac{n\ (n+1)\ (2\:n+7)}{6}\ \ \Rightarrow\ \ F(n)-F(n-1)\ =\: n\ (n+2)\:.\ $ Note that by employing the Fundamental Theorem we have reduced the proof to the trivial mechanical verification of a polynomial equation. Absolutely no ingenuity is required.

Note that the proof of the Fundamental Theorem is much more obvious than that for your special case because the telescopic cancellation is obvious at this level of generality, whereas it is usually obfuscated in most specific instances. Namely, the proof of the Fundamental Theorem is just a rigorous inductive proof of the following telescopic cancellation $\rm - F(0)\!+\!F(1) -F(1)\!+\!F(2) - F(2)\!+\!F(3)-\:\cdots - F(n-1)\!+\!F(n)\ =\:\: -F(0) + F(n) $ where all but the end terms cancel out. For further discussion see my many posts on telescopy.

  • 0
    @celtschk The point is that the telescopic viewpoint serves to abstract and unify these ubiquitous types of induction - making their proofs mechanical. Similarly, one doesn't need to know calculus to calculate areas under curves, but attempting to do so without using calculus will make the task much more difficult.2014-03-08
6

You used the wrong formula in your induction hypothesis. You are assuming that $1\cdot 3 + 2\cdot 4 + \cdots + k(k+2) = \frac{1}{6}k(k+1)(2k+7)$ but in your inductive argument, you wrote $1\cdot 3 + 2\cdot 4 + \cdots + k(k+2) + (k+1)(k+3) = \frac{1}{6}(k+1)(k+2)(2k+9) + (k+1)(k+3).$

That is, you substituted $1\cdot 3 + 2\cdot 4 + \cdots + k(k+2)$ with the formula for $k+1$, not the formula for $k$.