OpenStudy (anonymous):

Solve the recurrence relation $$a_n = a_{n-1} + n$$ where $$a_0 = 0$$ how to do this? First few values are (1,1), (2,3), (3,6), (4,10)... Is there any kind of formula for solving this?

2 years ago
ganeshie8 (ganeshie8):

work it the same way as previous

2 years ago
ganeshie8 (ganeshie8):

or you may eyeball the pattern you're adding sum of first n natural numbers

2 years ago
ganeshie8 (ganeshie8):

\begin{align} a_n &= a_{n-1}+n\\~\\ &= (a_{n-2}+ (n-1)) + n = a_{n-2} + 2n - 1 \\~\\ & = (a_{n-3} +(n-2)) + 2n-1 = a_{n-3} + 3n -(1+2)\\~\\ &=\cdots \\~\\ &=a_0 + n\cdot n - (1+2+\cdots + (n-1)) \\~\\&= a_0 + n^2 - \frac{n(n-1)}{2} \\~\\&= a_0 + \dfrac{n(n+1)}{2} \end{align}

2 years ago
OpenStudy (anonymous):

I don't get how you're doing that substitution.

2 years ago
ganeshie8 (ganeshie8):

did you follow the second line : \begin{align} a_n &= a_{n-1}+n\\~\\ &= (a_{n-2}+ (n-1)) + n = a_{n-2} + 2n - 1 \\~\\ \end{align} ?

2 years ago
OpenStudy (anonymous):

yes... just subtract 1 from every n in $$a_{n-1}$$

2 years ago
ganeshie8 (ganeshie8):

yes we just replace $$a_{n-1}$$ by $$a_{n-2} + (n-1)$$

2 years ago
ganeshie8 (ganeshie8):

then we keep going few more levels to see the pattern

2 years ago
ganeshie8 (ganeshie8):

\begin{align} a_n &= a_{n-1}+n\\~\\ &= (a_{n-2}+ (n-1)) + n = a_{n-2} + 2n - 1 \\~\\ & = (a_{n-3} +(n-2)) + 2n-1 = a_{n-3} + 3n -(1+2)\\~\\ \end{align} see if 3rd line also makes sense ^

2 years ago
OpenStudy (anonymous):

sure just keep subtracting one in place of the a_ part but then the last lines i don't get

2 years ago
ganeshie8 (ganeshie8):

\begin{align} a_n &= a_{n-1}+n\\~\\ &= (a_{n-2}+ (n-1)) + n = a_{n-2} + 2n - 1 \\~\\ & = (a_{n-3} +(n-2)) + 2n-1 = a_{n-\color{Red}{3}} + \color{red}{3}n -(1+\color{red}{2})\\~\\ \end{align}

2 years ago
ganeshie8 (ganeshie8):

Notice as you keep backtracking the levels, you will get $$a_0$$ when : \begin{align} &a_{n-\color{Red}{n}} + \color{red}{n}\cdot n -(1+2+\cdots + \color{red}{n-1})\\~\\ \end{align}

2 years ago
OpenStudy (anonymous):

like how is $$a_0 + n^2 - (1+2+...+(n-1)) = n^2 - \frac{n(n-1)}{2}$$

2 years ago
ganeshie8 (ganeshie8):

whats the formula for sum of first n-1 natural numbers ?

2 years ago
ganeshie8 (ganeshie8):

$1+2+\cdots + (n-1) = ?$

2 years ago
OpenStudy (anonymous):

yeah?

2 years ago
ganeshie8 (ganeshie8):

thats supposed to be a question to you :) do you remember the formula for finding sum of first n natural numbers ?

2 years ago
OpenStudy (anonymous):

no

2 years ago
ganeshie8 (ganeshie8):

2 years ago
OpenStudy (anonymous):

ah ok then

2 years ago
OpenStudy (anonymous):

and $$\frac{2n^2}{2} + \frac{n^2-n}{2} = \frac{n(n+1)}{2}$$ how..?

2 years ago
OpenStudy (anonymous):

sorry minus

2 years ago
Similar Questions: