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):

look up in google

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