# Proving an equality of two sums using induction for $n \in \mathbb N$

I stumbled across an exercise about induction that I can't come around to find a solution for.

I have to prove for all natural numbers that

$$\sum_{k=n}^{2n}{k} = 3\sum_{l=0}^{n}{l}$$

I started the proof as usual by proving that the equality is at least true for $$n_0$$. So for $$n=1$$ I got $$\sum_{k=1}^{2}{k} = 3\sum_{l=0}^{1}{l} \Rightarrow$$ $$1+2=3(0+1) \Rightarrow 3=3$$ and therefore the statement is true for $$n_0=1$$ Now with the requirement that the equality is true for $$n \in \mathbb N$$, I assume that the equality is also true for $$n+1$$ which means: $$\color{red}{\sum_{k=n}^{2n+1}{k}} = 3\sum_{l=0}^{n+1}{l} \space$$ With this assumption I have to execute the inductive step which is where I encounter my problem. I have to prove that if the statement holds for $$n$$ then it also holds for $$n+1$$. What I get is: $$\sum_{k=n}^{2(n+1)}{k} = 3\sum_{l=0}^{n+1}{l} \Rightarrow$$ $$\sum_{k=n}^{2n}{k}+2(n+1) = 3\sum_{l=0}^{n}{l}+3(n+1) \Rightarrow$$ $$\sum_{k=n}^{2n}{k} = 3\sum_{l=0}^{n}{l}+(n+1)$$ According to my understanding the proof should end with: $$\sum_{k=n}^{2n}{k} = 3\sum_{l=0}^{n}{l}$$ which of course is the starting equality.Unfortunately I don't end up with it, and I can't understand why. Any insight on the particular problem, or a way to approach induction problems with an equality between sums would be appreciated.

• I have colored the mistake. – Aqua Jun 6 at 13:38

Note that when you increase $$n$$ by $$1$$ on the LHS, you add the terms $$2n+1$$ and $$2n+2$$, and subtract the term $$n$$, leading to a total increase of $$3n+3$$. Note that increasing $$n$$ by $$1$$ on the RHS adds the term $$3n+3$$. The induction is straightforward from here.
The mistake you made is that $$\sum \limits_{k=n}^{2n+1}$$ should be $$\sum \limits_{k=n+1}^{2n+2}$$; your proof would have worked if you did this.
• Could you please elaborate how exactly the proof concludes, because when I use the index shift formula $\sum_{n=s}^{t}{f(n)} = \sum_{n=s+p}^{t+p}{f(n-p) }$ for $p=-1$ I get $\sum_{k=n+1}^{2(n+1)}{k} = \sum_{k=n}^{2n+1}{k+1}$ which equals $\sum_{k=n}^{2n}{k} +2n+2$ Instead of $\sum_{k=n}^{2n}{k} +3n+3$ that I think I need. – Konstantinos Zafeiris Jun 6 at 14:42
• @KonstantinosZafeiris When you got to $\sum_{k=n}^{2n+1} (k+1)$, you should have taken out $2n+2$ as the greatest term, as well as $n+1$ to turn $k+1$ into $k$. – auscrypt Jun 6 at 14:49
This $$\sum_{k=n}^{2n+1}{k}$$ should be $$\sum_{k=n+1}^{2n+2}{k}$$