Recurrence relations problem (1st order, linear, constant coeff, inhomogeneous) okay im supposed to find a recurrence relation for
$$
a_{n+1}= b \cdot a_n + c \cdot n  \ \ \ \ \ \ \ \  \ \ \ \ \mathbf{(1)}
$$
where $b$ and $c$ are constants. the method we learned in class was to multiply each term by $x^n$ and then take the sum of of the equation which has always worked fine but the "$c \cdot n$" term is giving me trouble in this problem. after some manipulation i get $c \sum n \cdot x^n$ which obviously does not converge. i know $x^n$ converges to $1 \over{1-x}$ but i dont know what to do about the "$n$" term. any help would be appreciated.
 A: You have the recurrence $a_{n+1}=ba_n+cn$, presumably with some initial value $a_0$. Multiply both sides by $x^n$ and sum over $n\ge 0$: $$\sum_{n\ge 0}a_{n+1}x^n=b\sum_{n\ge 0}a_nx^n+c\sum_{n\ge 0}nx^n\;.\tag{1}$$ For convenience let $$A(x)=\sum_{n\ge 0}a_nx^n\;.$$ Then for starters we can rewrite $(1)$ as $$\sum_{n\ge 0}a_{n+1}x^n=bA(x)+c\sum_{n\ge 0}nx^n\;.$$ Now look more closely at the sum on the lefthand side of $(1)$: it’s $$a_1+a_2x+a_3x^2+\dots\;,\tag{2}$$ compared with $$A(x)=a_0+a_1x+a_2x^2+\dots\;.$$ If you multiply $(2)$ by $x$ and add $a_0$, you get exactly $A(x)$, so we can further rewrite $(2)$ as $$\frac{A(x)-a_0}x=bA(x)+c\sum_{n\ge 0}nx^n\;,$$ or $$A(x)-a_0=bxA(x)+c\sum_{n\ge 0}nx^{n+1}\;,\tag{3}$$ which can be solved for $A(x)$ as soon as we evaluate the summation in the last term. From what you’ve written, I suspect that you may already be okay up to here. Now
$$\begin{align*}
\sum_{n\ge 0}nx^{n+1}&=x^2+2x^3+3x^4+\dots\\
&=x^2(1+2x+3x^2+\dots)\\\\
&=x^2\sum_{n\ge 0}(n+1)x^n\;,
\end{align*}$$
and $$\begin{align*}\sum_{n\ge 0}(n+1)x^n&=\frac{d}{dx}\left(\sum_{n\ge 0}x^{n+1}\right)\\
&=\frac{d}{dx}\left(\sum_{n\ge 0}x^n\right)\tag{4}\\
&=\frac{d}{dx}\left(\frac1{1-x}\right)\\
&=\frac1{(1-x)^2}\;.
\end{align*}$$
The step at $(4)$ is justified because $\sum_{n\ge 0}x^{n+1}$ and $\sum_{n\ge 0}x^n$ differ only by the constant $1$, so they have the same derivative. $(3)$ now becomes $$A(x)-a_0=bxA(x)+\frac{c}{(1-x)^2}\;,$$ so $$\begin{align*}A(x)&=\frac1{1-bx}\left(a_0+\frac{c}{(1-x)^2}\right)\\
&=\frac{a_0}{1-bx}+\frac{c}{(1-bx)(1-x)^2}\;.
\end{align*}$$
This is the desired generating function, and if you really want a closed form solution to the recurrence, you can decompose this into partial fractions, convert them to power series, and read off the coefficient of $x^n$.
A: You need to find a closed form to $a_{n+1}=ba_n+cn$.
For convenience manners, I will wrote the the above as following:
$$a_n=ba_{n-1}+c(n-1)$$
Let $f(x)$, be generating function of $a_n$:
$$f(x)=a_0+a_1x+a_2x^2+...$$
We write:
$$f(x)=a_0+a_1x+\sum_{i=2}^{\infty}a_ix^i=a_0+a_1x+\sum_{i=2}^{\infty}(ba_{i-1}+c(i-1))x^i=a_0+a_1x+\sum_{i=2}^{\infty}ba_{i-1}x^i+\sum_{i=2}^{\infty}c(i-1)x^i$$
$$=a_0+a_1x+b\sum_{i=2}^{\infty}a_{i-1}x^i+c\sum_{i=2}^{\infty}(i-1)x^i=$$
$$=a_0+a_1x+bx\sum_{i=2}^{\infty}a_{i-1}x^{i-1}+cx^2\sum_{i=2}^{\infty}(i-1)x^{i-2}=$$
$$=a_0+a_1x+bx(f(x)-a_0)+cx^2\sum_{i=2}^{\infty}(i-1)x^{i-2}=$$
$$=a_0+a_1x+bx(f(x)-a_0)+cx^2(\frac{1}{(1-x)^2})$$
So,
$$f(x)=a_0+a_1x+bx(f(x)-a_0)+\frac{cx^2}{(1-x)^2}$$
$$f(x)=\frac{a_0+a_1x+a_0bx+\frac{cx^2}{(1-x)^2}}{1-bx}$$
Now, you left to find the coefficient of $x^n$ in the expansion of $f(x)$ above.   
A: Hint $\ $ Let $\rm\:a(n) =\: b^n f(n).\:$ Then $\rm\:c\:\!n\: =\: a(n\!+\!1)-b\:a(n) =\: b^{n+1} (f(n\!+\!1)-f(n)).\:$ Hence
$$\rm f(n\!+\!1)-f(n)\ =\: \frac{c\!\:n}{b^{n+1}}\ \: \Rightarrow\ \: f(n)\: =\ f(0) + \sum_{k\:=\:0}^{n-1}(f(k\!+\!1)-f(k))\: =\ a(0) + \frac{c}b\:\sum_{k\:=\:0}^{n-1}\: \frac{k}{b^{k}}$$
