Question

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?

Answer 1

work it the same way as previous

Answer 2

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

Answer 3

\[\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}\]

Answer 4

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

Answer 5

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}\]

?

Answer 6

yes... just subtract 1 from every n in \(a_{n-1}\)

Answer 7

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

Answer 8

then we keep going few more levels to see the pattern

Answer 9

\[
\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 ^

Answer 10

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

Answer 11

\[
\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}
\]

Answer 12

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}
\]

Answer 13

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

Answer 14

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

Answer 15

\[1+2+\cdots + (n-1) = ?\]

Answer 16

yeah?

Answer 17

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

Answer 18

no

Answer 19

look up in google

Answer 20

ah ok then

Answer 21

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

Answer 22

sorry minus