confusion about recurrence relation

Question

let us suppose that we have following recurrence relation

$a_n-a_{n-1}=2*n$ where $a_0=0$

as i know solution is following

$a_n=a_0+\sum\limits_{i=1}^n 2n $

which is the same as $a_n=2*\sum\limits_{i=1}^n n $

but this term
$ \sum\limits_{i=1}^n n=n^2$

therefore $a_n=2*n^2$

but youtube says that

and also wolfram alpha says that solution is $a_n=n*(n+1)$ how?

Your notation is confusing, and you have got the sum of integers formula wrong. $1+2=3=\frac {2\times 3}2$ and not $2^2=4$. — Mark Bennet, Oct 08 '18 at 09:08
On the Internet you also find pages claiming and actually proving that the Earth is flat. The image you show is an example of something you shouldn't trust to. — egreg, Oct 08 '18 at 11:15

score 1 · Accepted Answer · answered Oct 08 '18 at 09:05

1

The following two summations are correct, \begin{align} \sum_{i=1}^n i &= \frac{n(n+1)}{2} \\ \sum_{i=1}^n n &= n \sum_{i=1}^n 1 = n(n) = n^2 \end{align} For your recurrence relation, we have that at each iteration you extract a term of the form $2i$ as such \begin{equation} \begin{split} a_n &= a_{n-1} + 2n\\ &= a_{n-2} + 2(n-1) + 2n\\ &= \vdots \\ &= a_{i} + 2(i+1) + \ldots + 2n \end{split} \end{equation} For $i = 0$, we get $$a_n = a_0 + \sum_{i=1}^n 2i = 0 + 2 \sum_{i=1}^n i = 2 \frac{n(n+1)}{2}=n(n+1)$$

answered Oct 08 '18 at 09:05

Ahmad Bazzi

12,076

now it is clear, but i think he also use wrong notation because direct insertion gives us exactly $a_n=2*n^2 $ – dato datuashvili Oct 08 '18 at 09:12
1

you are right. The reference you posted has a mistake in the second line, should be $2\sum_{i=1}^n i$ instead of $2\sum_{i=1}^n n$ – Ahmad Bazzi Oct 08 '18 at 09:13

confusion about recurrence relation

1 Answers1