Deriving Closed Form for a Recursion via Generating Functions

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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