0
$\begingroup$

I am having problems understanding how to 'prove' a summation formula.

I have the equation:

$ {\sum}^n _{i=1}i = \frac {n(n+1)}{2} $

Basis Step

when: $ n=1 $

$ {\sum}^1 _{i=1}i = \frac {1(1+1)}{2} $

which simplifies to: $ 1=1 $

Inductive Step; assume $ P(k) $ is true:

$ {\sum}^k _{i=1}i = \frac {k(k+1)}{2} $

Under this assumption, $P(k+1) $ is also true

$ {\sum}^{k+1} _{i=1}i = \frac {(k+1)((k+1)+1)}{2} $

Simplify

$ {\sum}^{k+1} _{i=1}i = \frac {(k+1)(k+2)}{2} $

Right Hand Side

$ RHS =\frac {(k+1)(k+2)}{2} $

Left Hand Side

$ {\sum}^{k+1} _{i=1}i ={\sum}^{k} _{i=1}i + \frac {(k+1)(k+2)}{2} $

Which simplifies to

$ {\sum}^{k+1} _{i=1}i = \frac {k(k+1)}{2} + \frac {(k+1)(k+2)}{2} $

The step above is the last step that I was able to complete, as I am confused on how to 'prove' the equivalency between the right hand side and the left hand side, or even if i am just providing incorrect steps.

Please any help would be very much appreciated as I have been working on the question for quite some time.

$\endgroup$
  • $\begingroup$ possible duplicate of Proof for formula for sum of sequence $1+2+3+\ldots+n$? $\endgroup$ – Daniel W. Farlow Jul 24 '15 at 1:04
  • $\begingroup$ @DanielW.Farlow I would not really say this is a duplicate because in that question they just wanted any proof, but in this they want strictly induction. $\endgroup$ – Nikhil Jul 24 '15 at 1:05
  • $\begingroup$ @Nkris Most proofs of this sum formula are by induction--it's almost universally the first induction problem people encounter. That link has a plethora of answers OP should read. Or search MSE for numerous other duplicate questions--the one I linked to is simply from this list of generalized questions on meta. I'd encourage you to take a look at it. $\endgroup$ – Daniel W. Farlow Jul 24 '15 at 1:08
  • $\begingroup$ @DanielW.Farlow You maybe right! $\endgroup$ – Nikhil Jul 24 '15 at 1:10
  • $\begingroup$ @Nkris I retracted my close vote and posted an answer I wrote a while back that does everything strictly by induction. There are too many duplicate links to count for this exact question. My answer is (I think) very thorough and should address anything the OP may be a bit hazy on. Hopefully anyway. $\endgroup$ – Daniel W. Farlow Jul 24 '15 at 1:15
1
$\begingroup$

Note: Originally posted as an answer for this question. Provided here to address a proof of the summation identity strictly by induction (as opposed to most of the answers offered in the linked to question).


Since this is your first time, I'll try to explain it with an emphasis on clarity. If something isn't clear, just comment and I'll try to explain what's happening.

Claim: You are trying to prove the statement $P(n)$ where $$ P(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$ Your goal is to try to prove this using induction. Proofs by induction usually involve two things: (1) showing that $P(n)$ is true for some fixed value of $n$; this value is oftentimes $n=1$, as it is in your case since you are trying to prove $P(n)$ for all $n\geq 1$. Make sense so far? (2) After you have shown (1) to be true, you then need to assume $P(k)$ to be true for some fixed $k\geq 1$ and then show that $P(k)$ implies $P(k+1)$; that is, you need to show that "if $P(k)$ is true, then $P(k+1)$ is true."

  • (1) is called the base case.
  • (2) is called the inductive step.

I'll outline the proof below. Let me know if a step doesn't make sense.

Proof. Let $P(n)$ denote the statement $$ P(n) : 1+2+3+\cdots+n = \frac{n(n+1)}{2}. $$ Base case ($n=1$): Try to see what happens for $P(1)$. We get that $1 = \frac{1(1+1)}{2}$, and this is true. Thus, the base case holds for $n=1$.

Inductive step ($P(k)\to P(k+1)$): Assume $P(k)$ is true for some fixed $k\geq 1$ (this is called the inductive hypothesis). That is, assume $$ P(k) : \color{red}{1+2+3+\cdots+k} = \color{green}{\frac{k(k+1)}{2}}\tag{inductive hypothesis} $$ is true. We must show that $P(k+1)$ follows where $$ P(k+1) : \underbrace{\color{red}{1+2+3+\cdots+k}+\color{blue}{(k+1)}}_{\text{LHS or "left-hand side"}} = \underbrace{\color{purple}{\frac{(k+1)((k+1)+1)}{2}}}_{\text{RHS or "right-hand side"}}. $$


Side note: Make sure you understand what just happened with $P(k+1)$. For $P(k)$, we just had $1+2+3+\cdots+k$ on the left-hand side. How come we have $1+2+3+\cdots+k+(k+1)$ now for the left-hand side of $P(k+1)$? This is because we are adding another term to the sum, namely $k+1$ (I highlighted this term with blue). On the right-hand side, where $P(k)$ just had $k$ in its expression, we just replace all of those $k$'s with $k+1$ because we are considering $P(k+1)$. Make sense?


Okay. Starting with the left-hand side of $P(k+1)$, we need to show that the right-hand side of $P(k+1)$ follows. Here's how it works: \begin{align} \text{LHS} &= \color{red}{1+2+3+\cdots+k}+\color{blue}{(k+1)}\tag{by definition}\\[1em] &= \color{green}{\frac{k(k+1)}{2}}+\color{blue}{(k+1)}\tag{by inductive hypothesis}\\[1em] &= \frac{\color{green}{k(k+1)}+\color{green}{2}\color{blue}{(k+1)}}{\color{green}{2}}\tag{common denominator}\\[1em] &= \frac{(k+1)\color{green}{(k+2)}}{\color{green}{2}}\tag{group like terms}\\[1em] &= \color{purple}{\frac{(k+1)((k+1)+1)}{2}}\tag{rearrange}\\[1em] &= \text{RHS} \end{align} Thus, we have shown that the right-hand side of $P(k+1)$ follows from the left-hand side of $P(k+1)$. This completes the inductive step.

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

Does it all make sense now?

$\endgroup$
  • $\begingroup$ Thank you!, this is possibly the most thoughal answer I've ever gotten on Stack Exchange $\endgroup$ – removed account Jul 24 '15 at 1:21
  • $\begingroup$ @asdfasdfasdf I'm glad I was able pull through the cobwebs and find that answer from a while back, and I am happy you found it helpful! Cheers. $\endgroup$ – Daniel W. Farlow Jul 24 '15 at 1:23
0
$\begingroup$

$P(k+1)$ has to be proven to be true, that means you have to prove: $\displaystyle \sum_{i=1}^{k+1} i = \dfrac{(k+1)(k+2)}{2}$. Start from $LHS = \displaystyle \sum_{i=1}^k i + (k+1)=\dfrac{k(k+1)}{2}+k+1$, and this expression equals to the $RHS$, hence completing the induction process, thereby proving the formuala.

$\endgroup$
0
$\begingroup$

Base Step: $n = 1$: $$\sum_{i = 1}^1 i = \frac{(1)(2)}{2} = 1$$ So the base case checks out. Now we must see if it works for $n = k+1$ assuming it works for $k$. $$\sum_{i = 1}^{k+1} i = 1+2+3+\cdots k+k+1 = \frac {k(k+1)}{2}+k+1$$ Simplifying we get: \begin{align*} \frac {k(k+1)}{2}+k+1 &= \frac {k(k+1)}{2} + \frac{2k+2}{2} \\ &= \frac{k^2+k+2k+2}{2} \\ & = \frac{k^2+3k+2}{2} \\ & = \frac{(k+1)(k+2)}{2} \\ \end{align*} Which is equal to the RHS in your question.

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