Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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*}$$

share|improve this question
    
could you please type it as a text? –  Ilya Oct 14 '11 at 18:31
1  
@Gortaur: Sorry,I don't know LaTeX. Pardon me. –  Fahad Uddin Oct 14 '11 at 18:41
2  
@Akito: If you right-click on the LaTeX that I've been putting into your questions, and then click on "show source", you can see how to write the equations in LaTeX. While some of the fancier things (like align*) may be somewhat beyond you, it should be fairly easy for you to learn how to do at least some LaTeX-ing of text, instead of relying on cumbersome image or on other people typing them out. While your image occupies more than one screenful on my end, the typed-out formulas are easy to see at a glance (less than half the screen), making it easier to see what you are doing. –  Arturo Magidin Oct 14 '11 at 18:52
add comment

3 Answers 3

up vote 4 down vote accepted

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). $$

share|improve this answer
    
Just out of curiosity, does your username refer to the NBA All-Star player, and his ridiculous $126 million dollar contract? –  Ragib Zaman Oct 15 '11 at 12:31
1  
@Ragib: No. When I went to get my first e-mail account way back when, I tried all sorts of names that were taken. So, I simply typed in 'joe'. It suggested I take the name 'joe126', presumably because there were 125 others named Joe. I liked it and started using it for other things. When I registered here I wanted to use 'Joe Johnson', but that was under use. –  Joe Johnson 126 Oct 15 '11 at 12:38
    
O wow, I really didn't expect that. Quite a big coincidence then! Sorry to bother you. –  Ragib Zaman Oct 15 '11 at 12:45
    
@JoeJohnson126: I think as joe 126 had become a popular keyword so they had shown it to you. –  Fahad Uddin Oct 22 '11 at 10:24
    
@Ragib Zaman: No bother. –  Joe Johnson 126 Nov 11 '11 at 17:55
add comment

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.

share|improve this answer
    
Why do you need the telescopic cancellation? Shouldn't it be enough to note that $\sum_{i=1}^n f(i) = \sum_{i=1}^{n-1}f(i) + f(n)$? From that, $F(n)-F(n-1)$ is just a normal cancellation. –  celtschk Jul 5 '12 at 7:44
    
@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. –  Bill Dubuque Mar 8 at 19:25
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.