Generating function of a sequence with a sum

Question

I am new to generating functions and I know some of the basics how to create them. But now I am not sure how to create a generating function of this sequence:

$$a_0 = 0$$

$$ a_n = n + c (\sum_{k=0}^{n-1} a_k)$$ for n >=1

where c is a real non-zero constant.

I guess I need to add $ \frac {1}{(1-x)^2}$ (which is generating function of the n (sequence 1, 2, 3, 4, ...)) to the rest. But how do I evaluate the rest?

Thank you for any tips.

Answer 1

We denote the generating function of $a_n$ with $A(x)=\sum_{n=0}^\infty a_n x^n$.

Part 1: Generating function of $\sum_{k=0}^{n-1}a_k$:

A generating function of the sum of the first $n+1$ elements $\sum_{k=0}^n a_k$ can be derived as Cauchy product of $A(x)$ with $\frac{1}{1-x}$.

We obtain \begin{align*} A(x)\color{blue}{\cdot\frac{1}{1-x}}=\left(\sum_{k=0}^\infty a_kx^k\right)\left(\sum_{l=0}^\infty x^l\right) =\sum_{n=0}^\infty\left(\sum_{{k+l=0}\atop{k,l\geq 0}}a_k\right)x^n =\sum_{n=0}^\infty\color{blue}{\left(\sum_{k=0}^na_k\right)} x^n \end{align*}

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series. This way we can write e.g. \begin{align*} \color{blue}{[x^n]A(x)}=[x^n]\sum_{k=0}^\infty a_kx^k\color{blue}{=a_n} \end{align*}

We get for $n\geq 1$ \begin{align*} \sum_{k=0}^{n-1}a_k=[x^{n-1}]\frac{A(x)}{1-x}=[x^n]\frac{xA(x)}{1-x}\tag{1} \end{align*}

Part 2: Generating function of $n$: Using the binomial series expansion we obtain for $n\geq 0$ \begin{align*} \frac{1}{(1-x)^2}&=\sum_{n=0}^\infty\binom{-2}{n}(-x)^n=\sum_{n=0}^\infty\binom{n+1}{n}x^n\\ &=\sum_{n=0}^\infty (n+1)x^n=\sum_{n=0}^\infty nx^n+\frac{1}{1-x} \end{align*} Here we use the binomial identities $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ and $\binom{p}{p-1}=\binom{p}{1}=p$. It follows \begin{align*} \sum_{n=0}^\infty nx^n=\frac{1}{(1-x)^2}-\frac{1}{1-x}=\frac{x}{(1-x)^2}\\ \end{align*} or equivalently \begin{align*} n=[x^n]\frac{x}{(1-x)^2}\qquad\qquad n\geq 0\tag{2} \end{align*}

Putting all together: We consider \begin{align*} a_n&=n+c\sum_{k=0}^{n-1}a_k\\ a_0&=0 \end{align*} and obtain from (1) and (2) \begin{align*} a_n&=[x^n]A(x)=[x^n]\frac{x}{(1-x)^2}+c[x^n]\frac{xA(x)}{1-x}\qquad\qquad n\geq 0\\ \end{align*} respectively \begin{align*} A(x)&=\frac{x}{(1-x)^2}+c\cdot\frac{xA(x)}{1-x}\\ \end{align*} from which \begin{align*} \color{blue}{A(x)=\frac{x}{(1-(c+1)x)(1-x)}} \end{align*} follows.

Answer 2

We have $$ a_{\,n} = n + c\sum\limits_{0\, \le \,k\, \le \,n - 1} {a_{\,k} } $$ and the condition $a_0=0$ is implicit in that.

So we can proceed with $$ \eqalign{ & F(z) = \sum\limits_{0\, \le \,n} {a_{\,n} \,z^{\,n} } = \sum\limits_{0\, \le \,n} {n\,z^{\,n} } + c\sum\limits_{0\, \le \,n} {\sum\limits_{0\, \le \,k\, \le \,n - 1} {a_{\,k} \,z^{\,n} } } = \cr & = z\sum\limits_{0\, \le \,n} {n\,z^{\,n - 1} } + c\sum\limits_{0\, \le \,n} {\sum\limits_{0\, \le \,k\, \le \,n - 1} {a_{\,k} \,z^{\,k} z^{\,n - k} } = } \cr & = z{d \over {dz}}\sum\limits_{0\, \le \,n} {\,z^{\,n} } + c\sum\limits_{0\, \le \,k} {a_{\,k} \,z^{\,k} \sum\limits_{k\, \le \,n - 1\,} {z^{\,n - k} } = } \cr & = z{d \over {dz}}\sum\limits_{0\, \le \,n} {\,z^{\,n} } + cz\sum\limits_{0\, \le \,k} {a_{\,k} \,z^{\,k} \sum\limits_{0\, \le \,n - 1 - k\,} {z^{\,n - 1 - k} } = } \cr & = z{d \over {dz}}{1 \over {1 - z}} + {{cz} \over {1 - z}}F(z) \cr} $$

and get $$ F(z) = {1 \over {1 - {{cz} \over {1 - z}}}}{z \over {\left( {1 - z} \right)^2 }} = {z \over {\left( {1 - \left( {c + 1} \right)z} \right)\left( {1 - z} \right)}} $$

Answer 3

Note that if $$ A(x)=\sum_{n=0}^\infty a_n x^n;\quad B(x)=\sum_{n=0}^\infty b_n x^n $$ are two formal power series then (by definition) $$ A(x)B(x)=\sum_{n=0}^\infty \left( \sum_{k=0}^na_kb_{n-k} \right) x^n.\tag{1} $$ In particular taking $B(x)=(1-x)^{-1}$, we have that $$ \frac{A(x)}{1-x}=\sum_{n=0}^\infty \left( \sum_{k=0}^na_k \right) x^n.\tag{2} $$ by (1) Further taking $A(x)=B(x)=(1-x)^{-1}$. we see that $$ (1-x)^{-2}=\sum_{n=0}^\infty(n+1)x^n\tag{3} $$ by (1). Finally observe that $$ \sum_{n=0}^\infty a_{n+1}x^n=\frac{A(x)-a_0}{x}\tag{4} $$ Now we have enough tools to tackle the problem. First rewrite the recurrence as $$ a_{n+1} = n+1 + c \left(\sum_{k=0}^{n} a_k\right);\quad (n\geq0)\tag{5} $$ where $a_0=0$. Let $A(x)$ be the generating function corresponding to the sequence $a_n$. Multiply both sides of (5) by $x^n$ and sum on $n\geq 0$ to obtain that $$ \frac{A(x)}{x}=\frac{1}{(1-x)^2}+c\frac{A(x)}{1-x} $$ where we have used (2), (3) and (4). We now proceed to solve for $A(x)$. Indeed, $$ A(x)(1-x)^2=x+cA(x)x(1-x)\implies A(x)=\frac{x}{(1-x)(1-(c+1)x)} $$ as desired.