stuck trying to solve nonhomogeneous recurrence relation

Question

hello and happy new year!

I'm trying to solve this question: We are required to find the solution (direct formula) of the following recurrence relation: $b(n)=b(n-1)+n-1$, $b(0)=0$.

What I did:

I was taught that if $\lambda^n p(n)$ is the nonhomogenous term (where $p(n)$ is some polynomial of $n$) and $\lambda$ is a root of the characteristic polynomial (with multiplicity of $r$ )of the homogeneous relation, then i need to add $\lambda^n n^r q(n)$ to the solution of the homogeneous system (where $q(n)$ is some polynomial of $n$ with the same degree as $p(n)$, and $r$ is the multiplicity of $\lambda$ as a root

It's a bit complex, I'll write down what I did.

First, I rewrote the question, $b(n)=b(n-1)+1^n(n-1)$, then I wrote the characteristic polynomial of the homogeneous relation $f(x)=x-1$. and wrote the solution for the homogenous system: $b(n)=1^na$ where $a$ is some coefficient.

now according to what i was taught, we know that the solution to the nonhomogeneous relation is: $b(n)=1^na+1^nn^1q(n) = a+nq(n)$

we know that $b(0)=0$ so we can get that $a=0$ and so $b(n)=nq(n)$ but now I'm stuck. How can I find $q(n)$?

Answer 1

Managed to solve it.

say $q(n) = an+b$ (we know that deg(q) = 1) and so:

$b(1)=1*(a*1+b) = 0$

$b(2) = 2*(a*2+b)=1$

you can conclude that $a=0.5$ and $b=-0.5$ and so $q(n)=0.5n-0.5$, and overall:

$b(n) = n(0.5n-0.5)$

Answer 2

Or you could conclude that

$$b(n)=b(0)+\sum_{k=0}^{n-1}k=\frac{(n-1)n}2.$$

Answer 3

This problem is way easier than you thought: \begin{align*} b(n)&=b(n-1)+(n-1)\\ &=b(n-2)+(n-2)+(n-1)\\ &=b(n-3)+(n-3)+(n-2)+(n-1)\\ &\cdots\\ &=b(0)+0+1+\cdots+(n-1)\\ &=1+\cdots+(n-1)\\ &=\frac{n(n-1)}{2} \end{align*}