2
$\begingroup$

Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$.

Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain

$$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = \sum2a_{n+1}x^{n+2} - \sum a_nx^{n+2} + \sum 4n3^nx^{n+2}\\ &\implies [A(x) - a_0 - a_1x] = 2x[A(x)-a_0] - x^2A(x) + \sum_n 4n3^nx^{n+2}\end{align*}$$

Is this correct so far? Is there always a best way to go about rearranging the obtained generating function, or does it vary from problem to problem? Further, is it simpler to use this method here or to instead obtain a particular solution through undetermined coefficients? Any help is much appreciated.

Is it possible to decompose $4n3^nx^{n+2}$ into $x^2$$\sum 4n \times 1/(1-3x)$ and does this help?

$\endgroup$
14
  • $\begingroup$ Should that be $\sum_n 4n3^nx^{n+2}$? $\endgroup$ Apr 21 '13 at 12:40
  • $\begingroup$ Yes it should, apologies. Is the rest correct so far? I not sure about my manipulations on the last line in particular. $\endgroup$
    – user73041
    Apr 21 '13 at 12:42
  • $\begingroup$ No, $\sum_{n=0}^\infty a_{n+2}x^{n+2} = A(x)-a_0-a_1x$ there should be no $x^2$ there $\endgroup$ Apr 21 '13 at 12:44
  • $\begingroup$ That's very good to know. So what is really happening when we remove these terms? I understood it to mean that we are shifting the index of $a_{n+2}$ by 2 and we then obtain $a_nx^{n+2}$ and must account for the x's. How do $a_0$ and $a_1x$ account for them instead? $\endgroup$
    – user73041
    Apr 21 '13 at 12:50
  • $\begingroup$ Are you asking what's the shortest way to solve the problem? $\endgroup$ Apr 21 '13 at 13:01
3
$\begingroup$

Everything is OK except $\sum_n 4n3^n x^{n+2}$. Let $B(x)=\sum_{n=1}^\infty 4n3^n x^{n+2}$. Then $$ \frac{1}{12x^3}B(x)=\sum_{n=1}^\infty n (3x)^{n-1}. $$ Using the fact that $\sum_{n=1}^\infty nx^{n-1}=\frac{1}{(1-x)^2}$ for $|x|<1$, we have $$\frac{1}{12x^3}B(x)=\frac{1}{(1-3x)^2}$$ or $$B(x)=\frac{12x^3}{(1-3x)^2}.$$

$\endgroup$
5
  • $\begingroup$ Thanks! And you mean everything except that and the error Thomas pointed out? I should change that in the original question. $\endgroup$
    – user73041
    Apr 21 '13 at 15:54
  • $\begingroup$ so then with B(x) inserted into the series I can solve for A(x) and then proceed by partial fraction expansion to get the coefficients for the fractions and transform back to power series to get the coefficients that will be the roots of the series? $\endgroup$
    – user73041
    Apr 21 '13 at 15:57
  • 1
    $\begingroup$ one final comment: did you mean that $d/dx(\sum x^n) = d/dx(1/(1-x)$? I think that's what was meant but just making sure. $\endgroup$
    – user73041
    Apr 21 '13 at 16:26
  • $\begingroup$ Yes, I think so. $\endgroup$
    – xpaul
    Apr 21 '13 at 21:18
  • $\begingroup$ to be sure, what coefficients does $B(x)$ result in? I know $1/(1-x)^2$ will just have coefficient $ n+1 \choose 1$ but what happens in this more complex case? $\endgroup$
    – user73041
    Apr 23 '13 at 19:42
3
$\begingroup$

In this case an easy way to derive a closed form solution is to rewrite the sequence as

$$a_{n+2}-a_{n+1} = a_{n+1} - a_n + 4n3^n$$

Then you can define $b_n = a_{n+1}-a_n$ and you'll get

$$b_{n+1} = b_n + 4n3^n$$

for which it is easy to give a closed-form solution. You can then obtain $a_n$ by summing over $b_n$:

$$a_n = \sum_{k=0}^{n-1}b_k + a_0$$

$\endgroup$
3
  • $\begingroup$ +1 but I suspect the point of the problem was to use generating functions. $\endgroup$ Apr 21 '13 at 12:35
  • $\begingroup$ Maybe you're right. Just thought it's nice to have a simpler alternative. $\endgroup$
    – Matt L.
    Apr 21 '13 at 12:36
  • $\begingroup$ This is still good to know, but Thomas is correct. With respect to these methods though, if I wanted to, for example, take $x(x - 1)$ as the solution using characteristic equation how would I: a) change this solution back in terms of $a_n$ - the same substitution you described? b) guess a particular solution. $\endgroup$
    – user73041
    Apr 21 '13 at 12:40
2
$\begingroup$

I would avoid the use of $\sum$ notation until you get an intuitive feel for how this method works. Instead, write out each term: $$\begin{aligned}a_2x^2&=2a_1x^2-a_0x^2\\ a_3x^3&=2a_2x^3-a_1x^3+12x^3\\ a_4x^4&=2a_3x^4-a_2x^4+72x^4\\ a_5x^5&=2a_4x^5-a_3x^5+324x^5\\ \vdots\phantom{x^n} &=\phantom{2a_2x^3-a_1}\vdots\end{aligned}$$ These are obtained by specializing the original recurrence (times $x^{n+2}$) to $n=0,1,2,3,\ldots$

Now sum up these equations and match the resulting sums to your definition of $A(x)$.

$\endgroup$
2
  • $\begingroup$ So the idea then is that these will result in a sum of the form $a_2x^2 + a_3x^3 + a_4x^4$ and so on = $2a_1x^2 + 2a_2x^3 + 2a_3x^4...$ - a0x^2 + a1x^3 + a2x^4...? I think my issue with this method stems from a lack of experience using generating functions. I understand that their coefficients correspond to combinatorial solutions but don't see how that relationship developed. $\endgroup$
    – user73041
    Apr 21 '13 at 13:45
  • $\begingroup$ That's right. The counting is the primary thing. Generating functions are just a convenient package for the coefficients. Writing the sequence of coefficients as a power series is very suggestive, and basic algebraic manipulations on the series often have combinatorial meaning, which is why the method is powerful. In some cases the formal power series even defines a function, and analytical techniques can be brought to bear. $\endgroup$ Apr 21 '13 at 16:12
1
$\begingroup$

This is how I would approach this. Of all the terms $4n3^n$does not depend on the $a_i$, so I'll keep that one apart. The first thing is to view an expression obtained from the remaining terms as a multiple of $A(x)$. So first separate $$ a_{n+2}-2a_{n-1}+a_n = 4n3^n. $$ We can recognise the left hand side as the coefficient of $x^{n+2}$ in $(1-2x+x^2)A(x)$. So if we multiply each displayed recursion relation by $x^{n+2}$ and add up, then we get an equation for $(1-2x+x^2)A(x)$, except for the terms of degree${}\leq1$, which are $1-x$ because $a_0=a_1=1$ and $(1-2x)(1+x)\equiv1-x\pmod{x^2}$. So we get $$ (1-2x+x^2)A(x) = 1-x+4x^2\sum_{n\geq0}n(3x)^n, $$ where the term $x^2$ before the summation comes from the fact that $4n3^n$ was multiplied by $x^{n+2}$ rather than by $x^n$.

Now doing the final summation can be done recognising that we can write $n+1=\binom{n+1}n=(-1)^n\binom{-2}n$ and $1=\binom nn=(-1)^n\binom{-1}n$ for all $n\geq0$, so that $$ \sum_{n\geq0}n(3x)^n =\sum_{n\geq0}\left(\tbinom{-2}n-\tbinom{-1}n\right)(-3x)^n =(1-3x)^{-2}-(1-3x)^{-1} =\frac{3x}{(1-3x)^2}. $$ Putting everything together gives $$ A(x)=\frac{1-7x+15x^2+3x^3}{(1-x)^2(1-3x)^2}, $$ where the numerator was obtained as $(1-3x)^2(1-x)+4x^2\times 3x$. Working out a concrete expression for the coefficients of $A(x)$ is now standard by partial fraction decomposition.

$\endgroup$
0
$\begingroup$

Use Wilf's techniques (see "generatingfunctionology"). Your recurrence is: $$ a_{n + 2} = 2 a{n + 1} - a_n + 4 n 3^n \qquad a_0 = a_1 = 1 $$ Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply by $z^n$ and sum over $n \ge 0$, recognizing the resulting sums gives: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 2 \frac{A(z) - a_0}{z} - A(z) + 4 z \frac{d}{d z} \frac{1}{1 - 3 z} $$ This gives: $$ A(z) = \frac{1 - 7 z + 15 z^2 + 3 z^3}{1 - 8 z + 22 z^2 - 24 z^3 + 9 z^4} = \frac{1}{(1 - 3 z)^2} - 4 \cdot \frac{1}{1 - 3 z} + \frac{1}{1 - z} + 3 \cdot \frac{1}{(1 - z)^2} $$ As we have: $$ (1 - u)^{-m} = \sum_{n \ge 0} \binom{-m}{n} (-u)^n = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} u^n $$ the expression for $A(z)$ gives directly: $$ a_n = \binom{n + 1}{1} 3^n - 4 \cdot 3^n + 1 + 3 \binom{n + 1}{1} = (n - 3) \cdot 3^n + 3 n + 4 $$

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