0
$\begingroup$

Use generating functions to solve $a_n = 3a_{n-1} - 2a_{n-2} + 2^n + (n+1)3^n$.

What I have so far, not sure if I forgot to do something or am missing out on something obvious: Define $$G(x) = \sum_{n=0}^{\infty} a_nx^n$$

Then, $G(x) = a_0 + a_1x + a_2x^2 + \sum_{n=3}^{\infty} a_nx^n$

= $a_0 + a_1x + a_2x^2 + \sum_{n=3}^{\infty} (3a_{n-1} - 2a_{n-2} + 2^n + (n+1)3^n)x^n$

= $a_0 + a_1x + a_2x^2 + \sum_{n=3}^{\infty} 3a_{n-1}x^n - \sum_{n=3}^{\infty} 2a_{n-2}x^n + \sum_{n=3}^{\infty} 2^nx^n + \sum_{n=3}^{\infty} (n+1)3^nx^n$

= $a_0 + a_1x + a_2x^2 + 3\sum_{n=3}^{\infty} a_{n-1}x^n - 2\sum_{n=3}^{\infty} a_{n-2}x^n + \sum_{n=3}^{\infty} (2x)^n + \sum_{n=3}^{\infty} (n+1)(3x)^n$

=$a_0 + a_1x + a_2x^2 + 3x\sum_{n=3}^{\infty} a_{n-1}x^{n-1} - 2x^2\sum_{n=3}^{\infty} a_{n-2}x^{n-2} + \sum_{n=3}^{\infty} (2x)^n + \sum_{n=3}^{\infty} (n+1)(3x)^n$

= $a_0 + a_1x + a_2x^2 + 3x\sum_{n=2}^{\infty} a_nx^n - 2x^2\sum_{n=1}^{\infty} a_nx^n + \sum_{n=3}^{\infty} (2x)^n + \sum_{n=3}^{\infty} (n+1)(3x)^n$

$\endgroup$
1
$\begingroup$

After making these replacements, you will have $G(x)$ on both sides, and a couple of other summations you can (hopefully?) find closed forms for. Then you can solve for $G(x)$. $$ \sum_{n=1}^\infty a_nx^n=G(x)-a_0\hspace{1.3cm} $$ $$ \sum_{n=2}^\infty a_nx^n=G(x)-a_0-a_1x $$

$\endgroup$
0
$\begingroup$

Hint: if $G(x)$ is the generating function for $a_n$, what are $x G(x)$ and $x^2 G(x)$ the generating functions for?

$\endgroup$
  • $\begingroup$ I know that $3xG(x) = \sum_{n=0}^{\infty} a_nx^n$, but my issue is how to make the bottom index of the sum to be n=0. Do I have to introduce some of the other previous terms into the summation? $\endgroup$ – Norman Contreras Apr 10 at 20:16
  • $\begingroup$ No, $x G(x) = \sum_{n=0}^\infty a_n x^{n+1} = \sum_{n=1}^\infty a_{n-1} x^n$. $\endgroup$ – Robert Israel Apr 11 at 0:50
0
$\begingroup$

Given that $G(x) = \sum_{n=0}^{\infty} a_nx^n$, you can write $a_n$ as $[x^n]G(x)$. Then the recurrence becomes $$[x^n]G(x) = 3[x^{n-1}]G(x) - 2[x^{n-2}]G(x) + 2^n + (n+1)3^n$$

If we introduce functions $P(x) = \sum_{n=0}^\infty 2^n x^n$ and $Q(x) = \sum_{n=0}^\infty (n+1)3^n x^n$ then, by the linearity of coefficient extraction, $$[x^n]G(x) = 3[x^n]xG(x) - 2[x^n]x^2G(x) + [x^n]P(x) + [x^n]Q(x)$$ and if this holds for every $n$ then $$G(x) = 3xG(x) - 2x^2G(x) + P(x) + Q(x)$$ which rearranges to $$G(x) = \frac{P(x) + Q(x)}{2x^2 - 3x + 1}$$

Finding closed forms for $P$ and $Q$ is left as an exercise...

$\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.