Sequence formulas and proving one of them is a rational function Let $B,C,D \geq 1$ be positive integers and $(b_n)_{n\geq 0}$ be a sequence with $b_0 = 1, b_n = B b_{n-1} + C B^n + D$ for $n \geq 1$.
Prove that 
(a) $\sum_{n\geq 0}^\infty b_n t^n$ ist a rational function
(b) identify a formula for $b_n$

Hi!
(a)
As I know I need to show that $\sum_{n\geq 0}^\infty b_n t^n$ can be rewritten as a fraction of two polynomials $\frac{P(x)}{Q(x)}$ while $Q(x)$ is not the zero polynomial, right?
There is no fraction in the recurrence formula given above, how do I show that? Can't I just take $Q(x) = 1$?
(b)
I do already have the formula $b_n = B b_{n-1} + C B^n + D$, so I might need one without any $b_n$ on the right side. But how do I eleminate it? If I would divide by $b_n$ I still don't know how to calculate $\frac{b_{n-1}}{b_n}$ (if this would actually help). 
Any ideas how this might be done?
Thanks in advance!
 A: Use the recursion $b_n=B b_{n-1}+CB^n+D$ in $\sum_{n=1}^{\infty} b_n t^n$ and equate the two sides. You will have the sum showing up on both sides after a little manipulation. Hope this helps.  
A: Hint: If $g(t) = \sum_{n=0}^\infty b_n t^n$, substitute in the recurrence for $b_n$ 
and express the result in terms of $g(t)$, $t$ and some geometric series.
A: I do not know how much help you need.  Both Robert Israel and Steve have given an almost complete solution of the problem, and one of theirs should be chosen as the solution to "accept."
You want to find a simple expression for $F(t)$, where
$$F(t)=\sum_0^\infty b_nt^n$$
Substituting in the recurrence for $b_n$, we find that we want
$$\sum_0^\infty (Bb_{n-1}+CB^n+D)t^n$$
Well, not quite!  Note that when $n=0$, we have $n-1=-1$, and we do not have an expression for $b_{n-1}$. The following is a way around the problem. (There is a cleverer way: find it!)
Note that 
$$F(t)=1+\sum_1^\infty b_nt^n$$
Now the substitution goes fine.
$$F(t)=1 + \sum_1^\infty (Bb_{n-1}+CB^n+D)t^n$$
Multiply through by $t^n$. We want
$$\sum_1^\infty Bb_{n-1}t^n+\sum_1^\infty CB^nt^n +\sum_1^\infty Dt^n$$
Let's deal with these various sums, say in backwards order.
So we want to calculate $\sum_1^\infty Dt^n$.  There is a common factor of $Dt$, so we want $Dt\sum_0^\infty t^k$.  I imagine you recognize that this is $Dt/(1-t)$.
Now let us calculate $\sum_1^\infty CB^nt^n=C\sum_1^\infty (Bt)^n$. Again, we have an infinite geometric series, and the sum is $CBt/(1-Bt)$.
Finally, let's deal with $\sum_1^\infty b_{n-1}t^n$.  This is
$b_0t+b_1t^2 + b_2t^3+\cdots$.  If we take out the common factor $t$, we get simply $t(b_0+b_1t+b_2t^2 +\cdots$, which is $tF(t)$.
Put all the stuff together. We get
$$F(t)= 1+ tF(t) + \frac{CBt}{1-Bt} + \frac{t}{1-t}$$
Rearrange a bit.
$$(1-t)F(t)= 1+ \frac{CBt}{1-Bt} + \frac{t}{1-t}$$
Now divide both sides by $1-t$ to obtain
$$F(t)= \frac{1}{1-t}+ \frac{CBt}{(1-Bt)(1-t)} + \frac{t}{(1-t)^2}$$
It remains to deal with part (b), but I already have typed too long. We want a formula for $b_n$, for $n \ge 1$.  There are various ways to do this, and I don't know what the preferred way is in your course.  Your function is a sum of $3$ terms. You know the coefficient of $t^n$ in the expansion of the first, and probably can handle the third, by exploiting the connection with the derivative of $1/(1-t)$.  The second term I would handle by first calculating its "partial fraction" decomposition.  
Added comment: The suggestion in the answer by Ross Millikan leads to a solution of (b) that is nicer and faster than extracting the coefficients from the generating function $F(t)$ using the ideas of the preceding paragraph.  But in your course you may be expected to know how to compute the coefficients of relatively simple generating functions like $F(t)$. 
A: For part b), you can just find the first few terms by hand:
$b_0=1$
$b_1=B+CB+D=B(C+1)+D$
$b_2=B^2+CB^2+dB+CB^2+D=B^2(2C+1)+D(B+1)$
$b_3=B^3(3C+1)+D(B^2+B+1)$
Maybe you can see a pattern and prove it by induction.
