# 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?

-

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

-
just great, thank you very much for being so patient and providing such a comprehendible solution! – muffel Jun 18 '11 at 21:04

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.

-
how do you mean that exactly? $\sum b_n t^n = \sum B b_{n-1} + CB^n + D$? Did you modify the index so it starts with 1 with intent? – muffel Jun 17 '11 at 20:49
Yes. You need the $t^n$ terms on the right-hand side but otherwise that is what I meant. Note that $b_{-1}$ is not defined and so you have to start at $n=1$ and manipulate a little to get the $n=0$ term, which involves adding and subtracting a constant on the left side.. – SteveH Jun 17 '11 at 20:57

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.

-
Israel What exactly should I substitute? If defining $g(t)$ for the sum, how can I apply this to the recurrence? – muffel Jun 17 '11 at 20:52
Substitute $B b_{n-1} + C B^n + D$ for $b_n$ (except in the case $n=0$). – Robert Israel Jun 17 '11 at 21:45

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.

-
Millikan Thank you, that helped me finding the answser $b_n = B^n(1+n\cdot C) + D(\sum_{i=0}^{n-1} B)$ (that is right, isn't it?) and the induction worked like a charm! – muffel Jun 18 '11 at 21:06
You need an exponent $i$ in the sum with $D$. Then you can represent the sum as $\frac{B^n-1}{B-1}$ as it is a geometric series. – Ross Millikan Jun 19 '11 at 1:44