What is the generating function for $(a_n)_{0\leq n}$, where $a_n$ is defined as $a_0 = 0$ and $a_{n+1} = a_n + (n+1)^3$ for all $n\geq0$?

Question

I have an idea of how to approach this problem, but I am rather confused by generating functions so I do not know if some of the steps I take are correct/allowed. I started this by noting that the function we are looking for is $f(x) = \sum_{n\geq0}a_nx^n$.
Since the sequence can be defined recursively by $a_0 = 0$ and $a_{n+1} = a_n + (n+1)^3$ for all $n\geq0$, I multiplied each of the parts by $x^n$ and summed to get $$\sum_{n\geq0}a_{n+1}x^n = \sum_{n\geq0}a_nx^n + \sum_{n\geq0}(n+1)^3x^n$$ Which I rewrote as $$\frac{1}{x}\sum_{n\geq0}a_{n+1}x^{n+1} = f(x) + \sum_{n\geq0}(n+1)^3x^n$$ And, since $a_0 = 0$, $$\frac{1}{x}f(x) = f(x) + \sum_{n\geq0}(n+1)^3x^n$$ I then subtracted $f(x)$ from both sides to obtain $$\frac{1-x}{x}f(x) = \sum_{n\geq0}(n+1)^3x^n$$ This is where I got stuck. I think the next step would be to say, since $0^3 = 0$, we can rewrite it as $$\frac{1-x}{x}f(x) = \sum_{n\geq0}n^3x^n$$ I am not sure if this works/is true? In a previous problem, we derived the generating function for $(n^3)$, so I subsituted it in here $$\frac{1-x}{x}f(x) = \frac{x^3+4x^2+x}{(1-x)^4}$$ And lastly multiplied both sides by $\frac{x}{1-x}$ to obtain $$f(x) = \frac{x^4+4x^3+x^2}{(1-x)^5}$$ So, does this look right? Is the maths correct? I am still new to generating functions so I am still confused by a lot of the rules and what you can and cannot do.

Answer 1

(A lot of people wrote long answers with alternate solutions and ideas -- I am suspicious some may not have actually read your post. Probably it will be more helpful to you to get direct feedback on what you did, so I will do that.)

It's almost a fully correct solution. The only error is when you replaced $\sum_{n \ge 0} (n+1)^3 x^n$ with $\sum_{n \ge 0} n^3 x^n$.

I am not sure if this works/is true?

It doesn't quite. Let's do it more carefully, by changing the index $n$ to $n' = n+1$ (so conversely, $n = n' - 1$):

\begin{align*} \sum_{n \ge 0} (n+1)^3 x^n &= \sum_{\color{red}{n' \ge 1}} (\color{red}{n'})^3 x^{\color{red}{n' - 1}} \\ &= \frac{1}{x} \sum_{n' \ge 1} (n')^3 x^{n'} \\ &= \frac{1}{x} \sum_{n' \ge 0} (n')^3 x^{n'} \quad (\text{since } 0^3 = 0)\\ &= \frac{1}{x} \sum_{n \ge 0} n^3 x^n \quad \text{(rename the variable)} \end{align*}

OK, so you'll end up with the same thing as before, but with an additional $\frac{1}{x}$ factor.

Answer 2

I'll post an incomplete solution and leave it to you to finish it:

$$\begin{align*} \color{blue}{\sum_{n>0}a_nx^n}&=x\sum_{n\ge0}a_{n+1}x^n\\ &=x\sum_{n\ge0}(a_n+(n+1)^3)x^n\\ &=x\left(\color{blue}{\sum_{n>0}a_n x^n}+\sum_{n\ge0}(n+1)^3x^n\right)\\ \end{align*}$$

Take particular note of the indexing changes I did, which exploit the initial condition $a_0=0$.

You should be able to evaluate one of the sums explicitly, and then solve for the unknown sum.

Answer 3

The best approach to write down the generating function from the recurrence is as recommended in the renowned "Concrete Mathematics", that is

a) make clear that (as usually is ) the variable is defined to be null for negative values of the index $$a_n=0\quad|\; n<0$$.

b) rewrite the recurrence putting the higher index at $n$, and you have better to arrange with RHS $=0$. $$ a_{\,n} - a_{\,n - 1} - n^{\,3} = 0 $$

c) by resorting to Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$ introduce suitable terms, such as to make the equation valid for all $0 \le n$.
In your case, for $n=0$, the equation becomes $a_0=0$ and we do not need any additional term. Otherwise in the LHS we should have added $-a_0\left[ 0=n \right]$: let's do it, so to make the case more general.

d) multiply by $x^n$ and sum for $0 \le n$ $$ \eqalign{ & 0 = \sum\limits_{0\, \le \,n} {a_{\,n} \,x^{\,n} } - \sum\limits_{0\, \le \,n} {a_{\,n - 1} \,x^{\,n} } - \sum\limits_{0\, \le \,n} {n^{\,3} \,x^{\,n} } - \sum\limits_{0\, \le \,n} {a_{\,0} \left[ {0 = n} \right]\,x^{\,n} } = \cr & = \sum\limits_{0\, \le \,n} {a_{\,n} \,x^{\,n} } - x\,\sum\limits_{0\, \le \,n} {a_{\,n - 1} \,x^{\,n - 1} } - \sum\limits_{0\, \le \,n} {n^{\,3} \,x^{\,n} } - a_{\,0} = \cr & = \sum\limits_{0\, \le \,n} {a_{\,n} \,x^{\,n} } - x\,\left( {a_{\, - 1} x^{\, - 1} + \sum\limits_{0\, \le \,n} {a_{\,n} \,x^{\,n} } } \right) - \sum\limits_{0\, \le \,n} {n^{\,3} \,x^{\,n} } - a_{\,0} = \cr & = F(x) - x\,F(x) - \sum\limits_{0\, \le \,n} {n^{\,3} \,x^{\,n} } - a_{\,0} = \cr & = F(x) - x\,F(x) - \sum\limits_{0\, \le \,n} {n\,x^{\,n} } - 3\sum\limits_{0\, \le \,n} {n\left( {n - 1} \right)\,x^{\,n} } - \sum\limits_{0\, \le \,n} {n\left( {n - 1} \right)\left( {n - 2} \right)\,x^{\,n} } - a_{\,0} = \cr & = F(x) - x\,F(x) - x\sum\limits_{0\, \le \,n} {n\,x^{\,n - 1} } - 3x^{\,2} \sum\limits_{0\, \le \,n} {n\left( {n - 1} \right)\,x^{\,n - 1} } - x^{\,3} \sum\limits_{0\, \le \,n} {n\left( {n - 1} \right)\left( {n - 2} \right)\,x^{\,n - 3} } - a_{\,0} \cr} $$

e) to conclude that $$ \eqalign{ & \left( {1 - x} \right)F(x) = x\sum\limits_{0\, \le \,n} {n\,x^{\,n - 1} } + 3x^{\,2} \sum\limits_{0\, \le \,n} {n\left( {n - 1} \right)\,x^{\,n - 1} } + x^{\,3} \sum\limits_{0\, \le \,n} {n\left( {n - 1} \right)\left( {n - 2} \right)\,x^{\,n - 3} } + a_{\,0} = \cr & = a_{\,0} + x{d \over {dx}}\left( {1 - x} \right)^{\, - 1} + 3x^{\,2} {{d^{\,2} } \over {dx^{\,2} }}\left( {1 - x} \right)^{\, - 1} + x^{\,3} {{d^{\,3} } \over {dx^{\,3} }}\left( {1 - x} \right)^{\, - 1} = \cr & = a_{\,0} + {x \over {\left( {1 - x} \right)^{\,2} }} + {{6x^{\,2} } \over {\left( {1 - x} \right)^{\,3} }} + {{6x^{\,3} } \over {\left( {1 - x} \right)^{\,4} }} = \cr & = {{a_{\,0} \left( {1 - x} \right)^{\,4} + x\left( {1 - x} \right)^{\,2} + 6x^{\,2} \left( {1 - x} \right) + 6x^{\,3} } \over {\left( {1 - x} \right)^{\,4} }} \cr} $$ i.e. $$ \eqalign{ & F(x) = {{a_{\,0} \left( {1 - x} \right)^{\,4} + x\left( {1 + 4x + x^{\,2} } \right)} \over {\left( {1 - x} \right)^{\,5} }} = \cr & = {{a_{\,0} } \over {1 - x}} - {1 \over {\left( {1 - x} \right)^{\,2} }} + {7 \over {\left( {1 - x} \right)^{\,3} }} - {{12} \over {\left( {1 - x} \right)^{\,4} }} + {6 \over {\left( {1 - x} \right)^{\,5} }} \cr} $$

So, your solution contains an extra $x$ factor . If you want to avoid (as much as possible) uncertainties in developing more complicated ogfs, I do suggest to you to get acquainted with the procedure above.

check

For $a_0=0$ the Taylor series of $F(x)$ gives the following coefficients $$ 0,1,9,36,100,225,441,\cdots $$ which corresponds to $$ a_{\,n} - a_{\,n - 1} = 0,1,8,27,64,125,216, \cdots = n^{\,3} $$

Or more rigorously $$ \eqalign{ & F(x) = {{a_{\,0} } \over {1 - x}} - {1 \over {\left( {1 - x} \right)^{\,2} }} + {7 \over {\left( {1 - x} \right)^{\,3} }} - {{12} \over {\left( {1 - x} \right)^{\,4} }} + {6 \over {\left( {1 - x} \right)^{\,5} }} = \cr & = a_{\,0} \sum\limits_{0\, \le \,n} {x^{\,n} } - \sum\limits_{0\, \le \,n} {\left( \matrix{ 1 + n \cr n \cr} \right)x^{\,n} } + 7\sum\limits_{0\, \le \,n} {\left( \matrix{ 2 + n \cr n \cr} \right)x^{\,n} } - 12\sum\limits_{0\, \le \,n} {\left( \matrix{ 3 + n \cr n \cr} \right)x^{\,n} } + 6\sum\limits_{0\, \le \,n} {\left( \matrix{ 4 + n \cr n \cr} \right)x^{\,n} } \Rightarrow \cr & \Rightarrow a_{\,n} = a_{\,0} - \left( \matrix{ 1 + n \cr 1 \cr} \right) + 7\left( \matrix{ 2 + n \cr 2 \cr} \right) - 12\left( \matrix{ 3 + n \cr 3 \cr} \right) + 6\left( \matrix{ 4 + n \cr 4 \cr} \right) = \cr & = a_{\,0} - \left( {n + 1} \right) + 7{{\left( {n + 2} \right)\left( {n + 1} \right)} \over 2} - 2\left( {n + 3} \right)\left( {n + 2} \right)\left( {n + 1} \right) + {{\left( {n + 4} \right)\left( {n + 3} \right)\left( {n + 2} \right)\left( {n + 1} \right)} \over 4} = \cr & = a_{\,0} + \left( {{{n\left( {n + 1} \right)} \over 2}} \right)^{\,2} \cr} $$ and in conclusion $$ \bbox[lightyellow] { F(x) = {{a_{\,0} \left( {1 - x} \right)^{\,4} + x\left( {1 + 4x + x^{\,2} } \right)} \over {\left( {1 - x} \right)^{\,5} }}\quad \Leftrightarrow \quad a_{\,n} = a_{\,0} + \left( {{{n\left( {n + 1} \right)} \over 2}} \right)^{\,2} \quad \Leftrightarrow \quad \left\{ {\matrix{ {a_{\,0} = a_{\,0} } \cr {a_{\,n} - a_{\,n - 1} = n^{\,3} } \cr {a_{\,n + 1} - a_{\,n} = \left( {n + 1} \right)^{\,3} } \cr } } \right. }$$

Answer 4

The definition of generating functions is very clear $f(x)=\sum\limits_{n=0}^{\infty}a_nx^n$. I prefer not ignoring $a_0$ to avoid messing with the indexes and, typically, you calculate it from the initial conditions, which you mentioned only in the title. So, I will treat it as unknown parameter for the purpose of the calculations below.

Thus $$f(x)=\sum\limits_{n=0}^{\infty}a_nx^n= a_0+\sum\limits_{n=1}^{\infty}a_nx^n= a_0+\sum\limits_{n=1}^{\infty}(a_{n-1}+n^3)x^n=\\ a_0+\sum\limits_{n=1}^{\infty}a_{n-1}x^n+\sum\limits_{n=1}^{\infty}n^3x^n= a_0+x\sum\limits_{n=1}^{\infty}a_{n-1}x^{n-1}+\sum\limits_{n=1}^{\infty}n^3x^n=\\ a_0+x\sum\limits_{n=0}^{\infty}a_{n}x^{n}+\sum\limits_{n=1}^{\infty}n^3x^n=a_0+xf(x)+x\sum\limits_{n=1}^{\infty}n^3x^{n-1}=\\ a_0+xf(x)+x\left(\sum\limits_{n=1}^{\infty}n^2x^{n}\right)'= a_0+xf(x)+x\left(x\sum\limits_{n=1}^{\infty}n^2x^{n-1}\right)'=\\ a_0+xf(x)+x\left(x\left(\sum\limits_{n=1}^{\infty}nx^{n}\right)'\right)'= a_0+xf(x)+x\left(x\left(x\sum\limits_{n=0}^{\infty}(n+1)x^{n}\right)'\right)'=\\ a_0+xf(x)+x\left(x\left(\frac{x}{(1-x)^2} \right)'\right)'= a_0+xf(x)+\frac{x^3+4x^2+x}{(1-x)^4}$$ and $$f(x)=\frac{a_0}{1-x}+\frac{x^3+4x^2+x}{(1-x)^5}$$