Generating function of a sequence with a sum 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.
 A: 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.

A: 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)}}
$$
A: 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.
