Generating Function for $(4,9,16,25,36,.....)$

Question

I have a sequence $(4,9,16,25,36,...)$ it is being generated by $a_n=(n+1)^2)$

I have found the generating function for $n^2$ here: Proving the generating function of $n^2$.

I know I can shift a sequence: $(1,4,9,16,25,....)$ to the right $(0,1,4,9,25,...)$ via $x^1*A(x)$ with $ A(x)$ a generating function. Does this also work with a left shift? Is there a definition? $n$ was a natural numbers. Maybe something else?

Answer 1

Let $f(t)=t^2+t^3+t^4+\dots=\dfrac{t^2}{1-t}$, for $|t|<1$.

Then $f'(t)=2t+3t^2+4t^3+\dots=\dfrac{2t-t^2}{(1-t)^2}$

And

$$\dfrac{\mathrm d\left(tf'(t)\right)}{\mathrm dt}=4t+9t^2+16t^3\dots=\frac{t^3-3t^2+4t}{(1-t)^3}$$

Finally

$$4+9t+16t^2+\dots=\frac{t^2-3t+4}{(1-t)^3}$$

Answer 2

We consider a power series $A(x)$ with constant term $a_0=0$. \begin{align*} A(x)=\sum_{j=j_0}^\infty a_jx^j \end{align*} A power series $B(x)=\sum_{j=j_0}^\infty a_{j+1}x^j$ can be derived via \begin{align*} A(x)&=\sum_{j=j_0}^\infty a_j x^j=\sum_{j=j_0-1}^\infty a_{j+1} x^{j+1}\\ &=x\sum_{j=j_0}^\infty a_{j+1}x^j+a_{j_0}x^{j_0}\\ &=xB(x)+a_{j_0}x^{j_0} \end{align*}

We conclude the left-shifted power series $B(x)$ has the representation \begin{align*} \color{blue}{B(x)=\frac{1}{x}A(x)-a_{j_0}x^{j_0-1}} \end{align*}

In the current situation we have \begin{align*} A(x)&=\frac{x(1+x)}{(1-x)^3}\\ &=x+4x^2+9x^3+16x^4+\cdots\\\\ \color{blue}{B(x)}&=\frac{1}{x}A(x)-1\\ &=\frac{1+x}{(1-x)^3}-1\\ &=\frac{x(x^2-3x+4)}{(1-x)^3}\\ &\,\,\color{blue}{=4x+9x^2+16x^3+\cdots} \end{align*}

Answer 3

An alternative way to think about it is to consider the forward differences of the sequence, $1,4,9,16,25,\ldots$ which is $3,5,7,9,\ldots$, and then forward differencing again we get constants. We translate this into generating function language:

Knowing that $$f(x) = 4 + 9x + 16x^2 + 25x^3 + \cdots$$

We calculate that $$\tag{1} f(x) - xf(x) - 4 = 5x + 7x^2 + 9x^3 + \cdots \equiv g(x)$$

and then $$\tag{2} g(x) - xg(x) - 5x = 2x^2 + 2x^3 + 2x^4 + \cdots = \frac{2x^2}{1-x}$$

From $(2)$ we solve for $g(x)$ as $$g(x) = \frac{-3x^2 + 5x}{(1-x)^2}$$

and then substitute back into $(1)$ to find

$f(x) = \frac{g(x) + 4}{1-x} = \frac{x^2 - 3x + 4}{(1-x)^3}$

This gives a good brute force approach for computing the generating function of any sequence whose terms are given by evaluating a polynomial at evenly spaced points.