Generating function: Solving a recursive equation

Question

I've got following recursive equation to solve:

$$a_n = \begin{cases} 5, & n = 0 \\ 3, & n = 1 \\ 5n^2 - 6n - 4 + a_{n-1}, & n \ge 2 \end{cases}$$

I also found the resulting generating function (I think that should be correct):

$$F(x) = z^2F(x) + \frac{5(x+1)}{(1-x)^3} - \frac{6}{(1-x)^2} + \frac{2}{1-x} +8x + 9$$

Edit: Which of course would give me: $$F(x) = \left(\frac{1}{1-x^2}\right)\times \left( \frac{5(x+1)}{(1-x)^3} - \frac{6}{(1-x)^2} + \frac{2}{1-x} +8x + 9\right)$$

How should I go forward?

Any help is greatly appreciated!

Answer 1

For $n\geq 1$, the solution of the linear recurrence of the first order $$a_n -a_{n-1}=5n^2 - 6n - 4\quad\mbox{for $n \ge 2$, with $a_1=3$}$$ should have the form $$a_n=An^3+Bn^2+Cn+D$$ where $A,B,C,D$ are constants to be determined. In fact, for $n\geq 1$, \begin{align*} a_n&=a_1+\sum_{k=2}^n(a_k -a_{k-1})=3+\sum_{k=2}^n (5k^2-6k-4)\\ &= 3+10\sum_{k=2}^n \binom{k}{2}-\sum_{k=2}^n k-4\sum_{k=2}^n1\\ &=3+10\binom{n+1}{3}-\binom{n+1}{2}+1-4(n-1)\\ &=\frac{5n^3}{3}-\frac{n^2}{2}-\frac{37n}{6}+8. \end{align*} The case $n=0$ should be considered separately: $$a_n = \frac{5n^3}{3}-\frac{n^2}{2}-\frac{37n}{6}+ \begin{cases} 5 & n = 0 \\ 8 & n \ge 1 \end{cases}$$

Answer 2

With $S_k(n)$ denoting the sum of the $k^{th}$ powers of the naturals (Faulhaber formula), the solution $$b_n=\sum_{k=0}^{n-1}(n^2-6n-4)=5S_2(n-1)-6S_1(n-1)-4S_0(n-1)$$

satisfies the recurrence and is such that $b_0=0,b_1=-4$.

Then by linearity, $a_n=-\dfrac12b_n+5$ satisfies all conditions.

Answer 3

Your problem contains two flaws. The first is in the text of the problem itself.

Indeed in a recurrence like yours $a_n= a_{n-1}+5n^2 - 6n - 4 \quad(*)$

the indeterminate is just one and not two. Giving both $a_0$ and $a_1$ makes the problem insolvable. So let's suppose that we know $a_0=5$.

Now suppose $F(x)=\sum _{n=1}^{\infty } a_n x^n$

multiply each term by $x^n$

$a_n x^n= a_{n-1} x^n +5n^2 x^n - 6n x^n- 4 x^n$

and add from $n=0$ to $\infty$

$\sum _{n=0}^{\infty } a_n x^n= \sum _{n=0}^{\infty } a_{n-1} x^n +5\sum _{n=0}^{\infty } n^2 x^n - 6 \sum _{n=0}^{\infty } n x^n- 4 \sum _{n=0}^{\infty } x^n$

the last series gives $-\dfrac{4}{x-1}$

$5\sum _{n=0}^{\infty } n x^n=\dfrac{5x}{(x-1)^2}$

$-6\sum _{n=0}^{\infty } n^2 x^n =\dfrac{6x (x+1)}{(x-1)^3}$

The sum is

$5\sum _{n=0}^{\infty } n^2 x^n - 6 \sum _{n=0}^{\infty } n x^n- 4 \sum _{n=0}^{\infty } x^n=\dfrac{-7 x^2-7 x+4}{(x-1)^3}$

Now comes the second flaw. Because

$\sum _{n=0}^{\infty } a_{n-1} x^n =\sum _{n=1}^{\infty } a_{n} x^{n+1}=x \sum _{n=1}^{\infty } a_{n} x^n=xF(x)$ while you wrote $x^2F(x)$

and

$\sum _{n=0}^{\infty } a_n x^n =a_0+\sum _{n=1}^{\infty } a_n x^n=5+F(x)$

therefore we have

$F(x)+5=x F(x)+\dfrac{-7 x^2-7 x+4}{(x-1)^3}$

$F(x)=\dfrac{5 x^3-8 x^2+22 x-9}{(x-1)^4}$

reduce with partial fractions

$$\frac{a}{x-1}+\frac{b}{(x-1)^2}+\frac{c}{(x-1)^3}+\frac{d}{(x-1)^4}=\dfrac{5 x^3-8 x^2+22 x-9}{(x-1)^4}$$

which gives

$$F(x)=\frac{9}{1-x}+\frac{7}{(x-1)^2}+\frac{21}{(x-1)^3}+\frac{10}{(x-1)^4}$$

and now the way back. The term of the recurrence are the MacLaurin series coefficients of $F(x)$

$\dfrac{9}{1-x}$ gives $9 \sum _{n=0}^{\infty } x^n$ so we have $9$

$\dfrac{7}{(x-1)^2}$ gives $7 (1 + n)$

$\dfrac{21}{(x-1)^3}$ gives $-\dfrac{21}{2}(n+1) (n+2)$

and $\dfrac{10}{(x-1)^4}$ gives $\dfrac{5}{3} (n+1) (n+2) (n+3)$

The sum is $a_n=\dfrac{1}{6} \left(10 n^3-3 n^2-37 n+30\right)$

First values are $5,\; 0,\; 4,\; 27,\; 79,\; 170,\; 310,\; 509,\; 777,\; 1124,\; 1560,\;\ldots$

and we can see that $a_1\ne 3$

I have tried with $a_1=3$ but I couldn't get $a_0=5$

Hope this helps