4
$\begingroup$

This is a homework problem, so please do not give the answer away. I must prove the following using mathematical induction:

$\forall n\in\mathbb{Z^+},\;2+4+6+\cdots+2n=n^2+n.$

This is what I have so far:

Let $P\left(n\right)$ represent $2+4+6+\cdots+2n=n^2+n$. Since $P\left(1\right)=\left(1\right)^2+1=2$, $P\left(1\right)$ is true. If $P\left(k\right)$ is true for $k\in\mathbb{Z^+}$, then $P\left(k+1\right)$ is true. Hence \begin{align} n^2+n & = \left(k+1\right)^2+\left(k+1\right)\notag\\ & = k^2 + 2k + 1 + k + 1\notag\\ & = k^2+3k + 2\notag\\ &=\left(k+2\right)\left(k+1\right).\notag \end{align}

I feel the last few steps do not do justice. Could you provide a hint to get me back on track? Thank you for your time,

$\endgroup$
  • 1
    $\begingroup$ I'd formulate it as follow: Suppose $P(k)$ is true, then $2+\ldots+2(k+1)=$...(computations)...$=(k+1)^2+(k+1)$ which shows that $P(k+1)$ is true. $\endgroup$ – Surb Mar 13 '15 at 14:22
  • 3
    $\begingroup$ If $P$ is a proposition, it is generally dangerous to write: $P(1)=1^2+1=2$. $P(1)$ is not a number, it is a statement. Better to write "$P(1)$ is $2=1^2+1$, which is true." $\endgroup$ – Thomas Andrews Mar 13 '15 at 14:23
  • $\begingroup$ @ThomasAndrews That makes sense, thanks! $\endgroup$ – jm324354 Mar 13 '15 at 14:26
  • 2
    $\begingroup$ Also: "If $P(k)$ is true for $k\in\mathbb Z^+$ then $P(k+1)$ is true." sounds like you are asserting this is true. Following with the word "Hence" gives the impression that you are deducing something from this fact. But you haven't proven this fact, and this fact is exactly what you are trying to prove. $\endgroup$ – Thomas Andrews Mar 13 '15 at 14:27
  • 2
    $\begingroup$ "If $P\left(k\right)$ is true for $k\in\mathbb{Z^+}$, then $P\left(k+1\right)$ is true". This is what you want to prove, yet you simply stated it as it being true. Don't write this in the middle of the proof. You should rather write something like "Suppose $P(k)$ is true" and after this you need to somehow conclude that $P(k+1)$ is true. Your computations are fine up to $k^2+3k + 2$. At this point you should try to massage what you have in order to use the induction hypothesis. Write $k^2+3k + 2=(k^2+k)+2k+2$ and proceed. $\endgroup$ – Git Gud Mar 13 '15 at 14:27
1
$\begingroup$

A little late to the party here, but I thought I might weigh in to share something useful I learned about summation/product identities when I first learned about induction, especially since this question has the proof-writing tag (I'm only going to focus on the inductive step, as you have already established the base case).

For most basic problems, the idea is to "peel off the $k+1$th summand" and then use the inductive hypothesis appropriately, etc. I'll give you an example concerning your problem specifically (since you have already accepted an answer, I imagine you have already proved the result).

You are trying to show that $$ 2+4+6+\cdots+2n=n^2+n\tag{1} $$ for all $n\geq 1$, where $n\in\mathbb{Z^+}$. Notice that we can represent $(1)$ by using $\Sigma$-notation: $$ \sum_{i=1}^n 2i=n^2+n.\tag{2} $$ Thus, we are really trying to prove that $(2)$ holds for all $n\in\mathbb{Z^+}$. To this end, let $P(n)$ denote the statement $$ P(n) : \sum_{i=1}^n 2i=n^2+n. $$ Fix some $k\geq 1$ and assume $P(k)$ to be true; that is, $$ P(k) : \sum_{i=1}^k 2i=k^2+k $$ holds. To be shown is that $P(k+1)$, where $$ P(k+1) : \sum_{i=1}^{k+1} 2i=(k+1)^2+(k+1), $$ follows. Beginning with the left-hand side of $P(k+1)$, \begin{align} \sum_{i=1}^{k+1} 2i &= \underbrace{\sum_{i=1}^k 2i + 2(k+1)}_{\text{"peel off the $k+1$th summand"}}\tag{by definition of $\Sigma$}\\[1em] &= (k^2+k) + 2(k+1)\tag{by $P(k)$, the ind. hyp.}\\[1em] &= (k+1)^2+(k+1),\tag{manipulate expression} \end{align} we end up with the right-hand side of $P(k+1)$.

Thus, by mathematical induction, the statement $P(n)$ holds for all $n\geq 1$. $\blacksquare$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great reply! Thanks, this all makes sense. $\endgroup$ – jm324354 Mar 14 '15 at 4:38
  • 1
    $\begingroup$ @jm324354 Glad it helped. :) $\endgroup$ – Daniel W. Farlow Mar 14 '15 at 4:41
  • $\begingroup$ Hmm in the summand, is "$2n$" supposed to be "$2i$"? $\endgroup$ – jm324354 Mar 16 '15 at 18:42
  • $\begingroup$ @jm324354 Yes! Very good catch. I just corrected it. Look all good to you now? $\endgroup$ – Daniel W. Farlow Mar 16 '15 at 19:06
  • 1
    $\begingroup$ @jm324354 You're welcome! Also, the whole "peeling" notion applies to problems where you have a product, $\Pi$. It's the same kind of thing, but most often you're confronted with summation problems using induction. Handy to know though. :) $\endgroup$ – Daniel W. Farlow Mar 16 '15 at 19:23
2
$\begingroup$

Suppose $P(k)$ is true for some $k \in \mathbb{N}$. That is, \begin{equation} 2+4+6+\cdots+2k=k^2+k. \end{equation} Now, we need to use this to show \begin{equation} 2+4+6+\cdots+2k+2(k+1)=(k+1)^2+(k+1). \end{equation} I hope this helps.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I believe this might help you.

Hint: $\sum2n=2\sum n$, but $\sum n=\frac{n^{2}+n}{2}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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