1
$\begingroup$

Prove that $$\sum_{i=n}^{2n}i=\frac{3}{2}n(n+1)$$ usind induction.


Base step: for $n=1$ we have $\sum_{i=1}^{2\cdot1}i=1+2=3$, and $\frac{3}{2}1(1+1)=\frac322=3$, so it is true for $n=1$.

My problem starts when trying to prove the inductive step: $$\sum_{i=h}^{2h}i=\frac{3}{2}h(h+1)\implies\sum_{i=h+1}^{2(h+1)}i=\frac{3}{2}(h+1)(h+2).$$ I have read that it has to be: \begin{align}\sum_{i=h+1}^{2(h+1)}i&=\sum_{i=h+1}^{2h+2}i\\ &=\underbrace{\sum_{i=h}^{2h}(i)}_{\text{Hypothesis}}+\underbrace{\sum_{i=1}^{2}}_{(*)}\\ &=\frac{3}{2}h(h+1)+\underbrace{\sum_{i=1}^{2}}_{(*)}\\ &=\frac{3}{2}h(h+1)+\bigl((h+1)+2(h+1)\bigr)\\ &=\cdots\\ &=\frac32h^2+\frac92h+3\\ &=\frac32(h+1)(h+2)\end{align}

but I think $(*)$ has no sense.

But I am not able to write it in a nice way because I think it has to be: $$(*)=\sum_{i=h+1}^{2}(2i+2)=\bigl(2(h+1)+2\bigr)+\bigl(2(2(h+1)+2)\bigr),$$ which is not right.

So my questions are:

  1. Is $(*)$ correct? What has to be inside the summation i.e. $\sum_{i=1}^2\square$? Why the initial value is $i=1$ but not $i=h+1$?
  2. Where is my mistake?

Thanks!!

$\endgroup$
2
$\begingroup$

\begin{align*} \sum_{i=h+1}^{2h+2}i & = \sum_{i=h+1}^{2h}i+\underbrace{(2h+1)+(2h+2)}_{\text{ the } 2h+1 \, \& \, 2h+2 \, \text{terms}} \\ & = \color{red}{h}+\sum_{i=h+1}^{2h}i+(2h+1)+(2h+2)\color{blue}{-h}\\ & = \underbrace{\sum_{i=\color{red}{h}}^{2h}i}_{\text{hypothesis expression}}+(2h+1)+(2h+2)\color{blue}{-h}\\ &=\frac{3}{2}h(h+1)+3h+3. \end{align*} Now you can finish off.

$\endgroup$
2
$\begingroup$

Hint: $$ \sum_{k = n + 1}^{2n + 2} k = \left(\sum_{k = n}^{2n + 2} k\right) - n = \left(\sum_{k = n}^{2n} k\right) + \left(2n + 1 + 2n + 2\right) - n = \left(\sum_{k = n}^{2n} k\right) + 3n + 3. $$ Explanation: In the very first expression my first summand is the $n + 1$-th term. After the equality sign I begin at the $n$-th term, which is not in the first expression, so I have to subtract it again.

For the next equality, it's the same procedure, only the other way around. In the second term, I add until the $2n + 2$-th term. I only want to add until $2n$, so I have to subtract the $2n + 2$-th and $2n + 1$-th term. Note that the $j$-th term of the series is always $j$.

$\endgroup$
2
$\begingroup$

$$\sum_{i=h+1}^{2(h+1)}i=\sum_{i=h+1}^{2h+2}i=\underbrace{\sum_{i=h}^{2h}(i)}_{\text{Hypothesis}}+\underbrace{\sum_{i=1}^{2}}_{(*)}$$

It looks you misunderstand the summation notation. Here are some more details (in expanded forms): $$\sum_{i=h+1}^{2(h+1)}i=\sum_{i=\color{blue}{h+1}}^{\color{red}{2h+2}}i=(\color{blue}{h+1})+(h+2)+\cdots +(2h)+(2h+1)+(\color{red}{2h+2})=\\ \color{green}{h}+(h+1)+(h+2)+\cdots +(2h)+(2h+1)+(2h+2)-\color{green}h=\\ \color{blue}{h}+(h+1)+(h+2)+\cdots +(\color{red}{2h})+(2h+1)+(2h+2)-h=\\ \sum_{i=\color{blue}h}^{\color{red}{2h}}i+(3h+3)=\frac32h(h+1)+3(h+1)=\frac32(h+1)(h+2).$$ Note:

1) In the summations above, the sum is taken from $\color{blue}{blue}$ to $\color{red}{red}$.

2) In line 2, the number $\color{green}h$ is added and subtracted to complete the sum from $\color{blue}h$ to $\color{red}{2h}$, which is needed for the hypothesis.

$\endgroup$
1
$\begingroup$

You should have said $$\sum_{i=h+1}^{2h+2}i=\left(\sum_{i=h}^{2h}i\right)-h+(2h+1)+(2h+2)$$

$\endgroup$
  • $\begingroup$ Thanks! I have never descompose a summation wrt the initial values i.e. $i=h+1$. So my questions are: 1) How do you go from $i=h+1$ to $i=h$? 2) Why there is a $-h+(2h+1)+(2h+2)$? $\endgroup$ – manooooh Jul 8 at 20:47
  • $\begingroup$ In general with integers $a<b<c<d,$ $$\sum_{i=a}^d f(i)=\sum_{i=a}^b f(i) + \sum_{i=b+1}^c f(i) + \sum_{i=c+1}^d f(i);$$ try writing out with some small values of $h$ to see $\endgroup$ – J. W. Tanner Jul 8 at 20:50
1
$\begingroup$

Hint:

Denoting the sums $S_n$ and $S_{n+1}$, just look at how they begin and end: \begin{alignat}{3} S_n &= {} &n&+{}&(n+1)+(n+2)+\dots &+2n \\ S_{n+1} &={} &&\phantom{+{}}&(n+1)+(n+2)+\dots &+2n +(2n+1)+(2n+2), \end{alignat} so that we have the relation $$S_{n+1}=S_n -n+(2n+1)+(2n+2)=S_n+3(n+1).$$ Can you end the computation?

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