# Recurrence relations problem help

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.

-
For the last bit, see math.stackexchange.com/questions/38194/…. It's a FAQ... – lhf Apr 3 '12 at 1:04
Consider reading this, and especially this section. – ThisIsNotAnId Apr 3 '12 at 3:43
You say you are supposed to find a recurrence relation for (1), but that can't be what you mean - (1) is already a recurrence relation. Maybe you mean you are supposed to find a generating function for the sequence $a_n$. Or maybe you mean you are supposed to find a solution of the recurrence relation (1). I'm not just quibbling here - half the trouble students have with math is getting all muddled up because they don't use the vocabulary precisely. Figure out what question you really mean to ask, and then edit the question accordingly - it's worth it. – Gerry Myerson Apr 3 '12 at 4:20
@GerryMyerson You make a completely valid and important point; though, I don't think the consequences are all that serious with the misuse of terminology in this post. And, +1 for providing the correct phraseology. – ThisIsNotAnId Apr 3 '12 at 4:59

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$.

-
 Wonderful! Very nice! – Salech Alhasov Apr 3 '12 at 1:28

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.

-

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}}$$

-