2

I'm attempting to understand in how to get from step1 to step2 :

Step 1. $1+2+\cdots+n = n(n+1)/2 $

Step 2. Need to show $1+2+\cdots+(n+1)= (n+1)(n+2) / 2$

How is $(n+1)(n+2) / 2$ derived from replacing $n$ in step 1 with $(n+1)$ ?

Daniel W. Farlow
  • 22,531
blue-sky
  • 2,100

2 Answers2

2

$$ {\huge(} 1+2+3+\cdots+n {\huge)} + (n+1) = \text{something}+(n+1). $$ The "something" comes from the induction hypothesis, i.e. from the case involving $n$ rather than $n+1$.

Michael Hardy
  • 1
2

The $(n+1)(n+2)/2$, or the right-hand side, is derived by using the induction hypothesis.

You assume $$ 1+2+\cdots+n=\frac{n(n+1)}{2} $$ is true for some $k\geq 1$. You need to use this assumption, called the induction hypothesis, in your derivation.

For example, you have the following \begin{align} 1+2+\cdots+k+(k+1) &= \underbrace{\frac{k(k+1)}{2}}_{1+2+\cdots+k=\frac{k(k+1)}{2}\;\text{(induction hypothesis)}}+(k+1)\\[1em] &= \frac{k(k+1)+2(k+1)}{2}\qquad\text{(common denominator)}\\[1em] &= \frac{(k+1)(k+2)}{2}\qquad\text{(desired expression)} \end{align} Do you see how this worked?

Daniel W. Farlow
  • 22,531
  • thank you, can you elaborate on how you derived the desired expression from the common denominator ? – blue-sky Feb 24 '15 at 21:45
  • 1
    @blue-sky I'm not entirely sure what your question is--if you meant how I got from the expression where there is a common denominator to the desired expression, then this is not too hard to figure out if you reason as follows: $\color{blue}{k}(\color{red}{k+1})+\color{blue}{2}(\color{red}{k+1})=(\color{blue}{k+2})(\color{red}{k+1})$. Does that answer your question? – Daniel W. Farlow Feb 24 '15 at 22:09
  • yes that makes sense now, is there a name or formula for factoring "k(k+1)+2(k+1)=(k+2)(k+1)" as it does appear familiar ? – blue-sky Feb 24 '15 at 23:30
  • 1
    @blue-sky It's simply combining like terms. For example, if you had $k(k+1)+2(k+1)+r(k+1)$, then you can now see why this would be equivalent to $(k+2+r)(k+1)$. – Daniel W. Farlow Feb 24 '15 at 23:32