1
$\begingroup$

I need to find the generating function of this recurrence when $a_0 = 4$, $a_1$ = 8

$f(x) = \sum_{i=0}^\infty a_ix^i = 4 + 8x + (4a_1 - a_0)x^2 + (4a_2 - a_1)x^3 + \dots$

$f(x) = 4 + 8x + 4a_1x^2 - a_0x^2 + 4a_2x^3 - a_1x^3 + \dots$

$f(x) = 4 + 8x + 4x(a_1x + a_2x^2 + \dots) - x^2(a_0 + a_1x + \dots)$

$f(x) = 4 + 8x + 4x(f(x) - 4) - x^2f(x)$

$f(x) = \dfrac{4 - 8x}{x^2 - 4x + 1}$

I dont know if this is the correct generating function, but either way I dont know how to interpret the answer, like for instance $f(1)$ is the sum of all terms of the recurrence? then it seems strange I get $f(1) = 2$. Did I do a mistake?

$\endgroup$
2
  • 2
    $\begingroup$ Looks good. $f(1)$ would be the sum of all the terms in the recursion IF the radius of convergence were $>1$. In this case, though, the radius is just $2-\sqrt 3$. $\endgroup$ – lulu Nov 27 '19 at 13:58
  • $\begingroup$ $a_1$ is the coefficient on $x$ in the series for $f$ $\endgroup$ – J. W. Tanner Nov 27 '19 at 13:58
1
$\begingroup$

To rewrite your work more clearly:

\begin{align}f(x)&=\sum_{n=0}^\infty a_nx^n\\&=4+8x+\sum_{n=0}^\infty a_{n+2}x^{n+2}\\&=4+8x+\sum_{n=0}^\infty(4a_{n+1}-a_n)x^{n+2}\\&=4+8x+4x(f(x)-4)-x^2f(x)\\&=4-8x-(x^2-4x)f(x)\end{align}

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

As noted in the comments, this representation is valid provided that it converges, which is only for $|x|<2-\sqrt3$.

From this form, we can then derive the coefficients by expanding it out as follows:

\begin{align}f(x)&=\frac{4-8x}{x^2-4x+1}\\&=\frac{4-8x}{(x-2)^2-3}\\&=\frac{4-8x}{(x-2-\sqrt3)(x-2+\sqrt3)}\\&=\frac{-4-2\sqrt3}{x-2-\sqrt3}+\frac{-4+2\sqrt3}{x-2+\sqrt3}\\&=\frac2{1-\frac x{2+\sqrt3}}+\frac2{1-\frac x{2-\sqrt3}}\\&=2\sum_{n=0}^\infty\underbrace{\left[\frac1{(2+\sqrt3)^n}+\frac1{(2-\sqrt3)^n}\right]}_{a_n/2}x^n\end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.