Given the sequence {39, 174, 441, 876, 1515, ....}, find the generating function

Question

It seems that there is a lot of differentiation and right shifting in this equation but I do not know which comes first. Here's what I've done:

Initial function (Known function): {1,1,1,1,1,...} = 1x⁰ + 1x¹ + 1x²+ 1x³ + 1x⁴ + ... = 1/(1-x)

(differentiating)

func. 1: {1,2,3,4,5,...} = 0 + 1 + 2x+ 3x² + 4x³ + 5x⁴ +... = 1/(1-x)²

.... fourth round of differentiating:

func. 4: {6,24,60,120,210,...} = 6 + + 24x+ 60x² + 120x³ + 210x⁴ +... = 3/(1-x)⁴

I tried Right Shifting afterwards which produced:

{0,6,24,60,120,210,...} = 0 + 6x + 24x² + 60x³ + 120x⁴ + 210x⁵ +... = 3x/(1-x)⁴

Need to find: {39,174,441,876,1515,...} = ?(function) = ?(Generating Function}

Wolframalpha suggests that the generating function is 3(7x² - 6x - 13)/(x-1)⁴

Can anyone advise me in the right direction? Thanks.

Answer 1

We are given that $f_0=\{1,1,1,1,1,...\}=\frac 1{1-x}$

Differentiating gives $f_1=\{1,2,3,4,5,...\}=\frac 1{(1-x)^2}$. This is a linear sequence.

Not given, but differentiating again gives $f_2=\{2,6,12,20,30...\}=\frac 2{(1-x)^3}$. Note that this is a quadratic sequence with second difference 2.

Differentiating again gives $f_3=\{6,24,60,120,210...\}=\frac 6{(1-x)^4}$. Note that this is a cubic sequence with third difference 6. Note also that I disagree with you slightly... $\frac d{dx}\left (\frac 2{(1-x)^3}\right)=\frac 6{(1-x)^4}$, not $\frac 3{(1-x)^4}$

We are given $g=\{39, 174, 441, 876, 1515, ...\}$.

The terms form a cubic sequence with third difference 36. They can therefore be written as a linear combination of $f_0$, $f_1$, $f_2$ and $f_3$.

Start by subtracting $\frac {36}6 f_3$

$g-6f_3=\{39, 174, 441, 876, 1515, ...\}-\{36,144,360,720,1260,...\}$

which gives $g_1=\{3,30,81,156,255,...\}$

The terms form a quadratic sequence with common difference $24$ so subtract $\frac {24}2 f_2$

$g_1-12f_2=\{3, 30, 81, 156, 255, ...\}-\{24,72,144,240,360,...\}$

which gives $g_2=\{-21,-42,-63,-84,-105,...\}$

We can see that $g_2=-21f_1$

Since we have $g-6f_3-12f_2=-21f_1$,

we can say $g=6f_3+12f_2-21f_1$

Thus $g=\frac {6 \times 6}{(1-x)^4}+\frac{12 \times 2}{(1-x)^3}-\frac{21 \times 1}{(1-x)^2}$

$g=\frac {36}{(1-x)^4}+\frac{24(1-x)}{(1-x)^4}-\frac{21(1-x)^2}{(1-x)^4}$

$g=\frac {36+24-24x-21+42x-21x^2}{(1-x)^4}$

$g=\frac {39+18x-21x^2}{(1-x)^4}$

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