3
$\begingroup$

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.

  • 0
    @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.2012-04-03

3 Answers 3

3

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

  • 0
    Wonderful! Very nice!2012-04-03
0

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.

0

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