stuck trying to solve nonhomogeneous recurrence relation 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)$?
 A: Or you could conclude that 
$$b(n)=b(0)+\sum_{k=0}^{n-1}k=\frac{(n-1)n}2.$$
A: Use generating functions. Define $B(z) = \sum_{n \ge 0} b(n) z^n$, write the recurrence as:
$$
b(n + 1) = b(n) + n
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize:
$$
\sum_{n \ge 0} b(n + 1) z^n = \frac{B(z) - b(0)}{z}
$$
and also:
\begin{align}
\sum_{n \ge 0} z^n   &= \frac{1}{1 - z} \\
\sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\
                     &= \frac{z}{(1 - z)^2}
\end{align}
This gives:
$$
\frac{B(z)}{z} = B(z) + \frac{z}{(1 - z)^2}
$$
Or:
$$
B(z) = \frac{1}{1 - z} - \frac{2}{(1 - z)^2} + \frac{1}{(1 -z)^3}
$$
So you have:
\begin{align}
b(n) &= 1 - 2 \cdot (-1)^n \binom{-2}{n} + (-1)^n \binom{-3}{n} \\
     &= 1 - 2 \binom{n + 2 - 1}{2 - 1} + \binom{n + 3 - 1}{3 - 1} \\
     &= 1 - 2 (n + 1) + \frac{(n + 2) (n + 1)}{2} \\
     &= \frac{n (n - 1)}{2}
\end{align}
A: 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)$
A: 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*}
A: The sequence $A_n = n$ satisfies $A_{n+1} = 2A_n - A_{n-1}$
$B_{n+2} = B_{n+1} + A_{n+1}$
$B_{n+1} = B_{n} + A_{n}$
$B_{n} = B_{n-1} + A_{n-1}$
Now starting with the first equation, subtracting twice the second, and then adding the third we get:
$B_{n+2} - 2B_{n+1} + B{n} = B_{n+1} - 2B_{n} + B_{n-1}$
$B_{n+2} = 3B_{n+1} - 3B_{n} +B_{n-1}$
So now we have usual linear recurrence which you may be more comfortable with.
