1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have colored the mistake. $\endgroup$ – Aqua Jun 6 at 13:38
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Konstantinos Zafeiris Jun 6 at 14:42
  • $\begingroup$ @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$. $\endgroup$ – auscrypt Jun 6 at 14:49
1
$\begingroup$

This $$\sum_{k=n}^{2n+1}{k} $$ should be $$\sum_{k=n+1}^{2n+2}{k} $$

$\endgroup$
  • 1
    $\begingroup$ I am obviously a much less experienced member than you are, but shouldn't this be a comment rather than an answer? $\endgroup$ – tia Jun 6 at 13:42
  • $\begingroup$ @Aqua So I should also change the index of summation. I understand my mistake now, I just thought that because it's an index it wouldn't be affected. By it makes sense now since that '+1' is the (n+1) I am missing $\endgroup$ – Konstantinos Zafeiris Jun 6 at 13:43
  • $\begingroup$ Glad I could help $\endgroup$ – Aqua Jun 6 at 13:44

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.