Find the generating function for $a_n=\sum_{k=0}^{n} 3^{k}(n-k), n\geq0$.

Question

For every integer $n\geq 0$ we define

$a_n=\sum_{k=0}^{n} 3^{k}(n-k)$.

Find the generating function of the sequence $(a_n)_{n=0}^\infty$ and write down the answer without series.

Attempt: $G(x)=\sum_{n=0}^{\infty} (\sum_{k=0}^{n} 3^{k}(n-k))x^n=\sum_{n=0}^{\infty} (n\sum_{k=0}^{n} 3^{k}-\sum_{k=0}^{n}k3^k)x^n=\sum_{n=0}^{\infty}(\frac{1}{2}n(3^{n+1}-1)-\sum_{k=0}^{n}k3^{k})=...?$

where I took into account that $1+3+...+3^n=\frac{1}{2}(3^{n+1}-1)$. How to continue?

WolframAlpha returns: $\sum_{n=0}^{\infty} (\sum_{k=0}^{n} 3^{k}(n-k))x^n$=$-\frac{x}{(x-1)^2 (3x-1)}$. How do I get to this?

Answer 1

We can directly see that $a_n$ is the convolution of the sequences $b_n = 3^n$ and $c_n = n$. Therefore, the generating function for $a_n$ is the product of the generating functions for $b_n$ and $c_n$, which are $\frac{1}{1-3x}$ and $\frac{x}{(1-x)^2}$, respectively.

Answer 2

An alternative method to the discussion in the comments:
We can reindex the sum as follows: $$\begin{align}\sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} 3^{k}(n-k)\right)x^n &= \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} 3^{n-k}k\right)x^n \\ &= \sum_{n=0}^{\infty} 3^n\left(\sum_{k=0}^{n} (1/3)^kk\right)x^n \\ &= \sum_{n=0}^{\infty} 3^n\left(\frac{3^{n+1} - 2n-3}{4\cdot 3^n}\right)x^n \\ &= \sum_{n=0}^{\infty} \frac{3^{n+1} - 2n-3}{4}x^n \end{align}$$ To avoid long calculations (I'm too lazy for this), I leave the rest to the OP. When you split it into three sums, two should be standard GP, the remaining one can be salvaged by using derivatives.

Answer 3

The convolution approach by @DanielSchepler is the simplest way, but here is an explicit derivation that does not rely on recognizing that. \begin{align} \sum_{n=0}^\infty \sum_{k=0}^n 3^k(n-k) x^n &= \sum_{k=0}^\infty \sum_{n=k}^\infty 3^k(n-k) x^n \\ &= \sum_{k=0}^\infty (3x)^k \sum_{n=k}^\infty (n-k) x^{n-k} \\ &= \sum_{k=0}^\infty (3x)^k \sum_{n=0}^\infty n x^n \\ &= \sum_{k=0}^\infty (3x)^k \frac{x}{(1-x)^2} \\ &= \frac{x}{(1-x)^2} \sum_{k=0}^\infty (3x)^k \\ &= \frac{x}{(1-x)^2} \cdot \frac{1}{1-3x} \\ &= \frac{x}{(1-x)^2 (1-3x)} \end{align}

Essentially the same steps yield the general convolution result: \begin{align} \sum_{n=0}^\infty a_n x^n &= \sum_{n=0}^\infty \sum_{k=0}^n b_k c_{n-k} x^n \\ &= \sum_{k=0}^\infty \sum_{n=k}^\infty b_k c_{n-k} x^n \\ &= \sum_{k=0}^\infty b_k x^k \sum_{n=k}^\infty c_{n-k} x^{n-k} \\ &= \sum_{k=0}^\infty b_k x^k \sum_{n=0}^\infty c_n x^n \\ &= \sum_{k=0}^\infty b_k x^k C(x) \\ &= C(x) \sum_{k=0}^\infty b_k x^k \\ &= C(x) B(x) \end{align}