Prove generating function of $a_n = (b+1)^n - b^n$

Question

The problem is prove that $$\frac{x}{(1-bx)(1-bx-x)}$$ is the generating function for the sequence $$a_n = (b+1)^n - b^n$$ I tried separating the fraction as $$x\frac{1}{1-bx}\frac{1}{1-x(b+1)}$$ which yields the generating functions $$x\sum_{n=0}^\infty (bx)^n\sum_{n=0}^\infty ((b+1)x)^n$$ Did I make a mistake? If not, how does this lead to the generating function with terms $a_n$?

Answer 1

HINT $$ \begin{split} \sum_{n=0}^\infty a_nx^n = \sum_{n=0}^\infty (b+1)^nx^n - \sum_{n=0}^\infty b^n x^n = \frac{1}{1-x(b+1)} - \frac{1}{1-xb} \end{split} $$

Answer 2

There is no mistake with your approach. The calculation is just, let's say slightly more cumbersome.

We obtain \begin{align*} \color{blue}{x\sum_{k=0}^\infty}&\color{blue}{ (bx)^k\sum_{l=0}^\infty ((b+1)x)^l}\\ &=x\sum_{n=0}^\infty\left(\sum_{{k+l=n}\atop{k,l\geq 0}}b^k(b+1)^l\right)x^n\tag{1}\\ &=x\sum_{n=0}^\infty\left(\sum_{k=0}^n b^k(b+1)^{n-k}\right)x^n\\ &=x\sum_{n=0}^\infty\left(\sum_{k=0}^n\left(\frac{b}{b+1}\right)^k\right)(b+1)^nx^n\tag{2}\\ &=x\sum_{n=0}^\infty\left(\frac{1-\left(\frac{b}{b+1}\right)^{n+1}}{1-\frac{b}{b+1}}\right)(b+1)^nx^n\tag{3}\\ &=\sum_{n=0}^\infty\left(1-\left(\frac{b}{b+1}\right)^{n+1}\right)(b+1)^{n+1}x^{n+1}\\ &=\sum_{n=0}^\infty\left((b+1)^{n+1}-b^{n+1}\right)x^{n+1}\\ &\,\,\color{blue}{=\sum_{n=1}^\infty\left((b+1)^{n}-b^{n}\right)x^{n}} \end{align*} and the claim follows.

Comment:

• In (1) we use the Cauchy product of two series.

• In (2) we do some rearrangements as preparation for the next step.

• In (3) we apply the geometric series formula.