# Use generating functions to solve $a_n = 6a_{n-1} - 8a_{n-2} + 3$ and… [closed]

Use generating functions to solve:

$$a_n = 6 a_{n - 1} - 8 a_{n - 2} + 3$$

With initial condition: $a_0 = 1$ and $a_1 = 0$

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

With initial conditions: $a_0 = 1$

Have done recurrence relation problems before but am struggling with these two problems, any help is appreciated.

## closed as off-topic by user147263, Macavity, user223391, 6005, Harish Chandra RajpootOct 22 '15 at 5:01

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Community, 6005, Harish Chandra Rajpoot
If this question can be reworded to fit the rules in the help center, please edit the question.

• Thank you,what would you suggest? – D.Peterson Oct 14 '15 at 20:27
• Have you tried $a_n=\lambda ^n$? – user249332 Oct 14 '15 at 20:29
• @D.Peterson: What you have is quite adequate. It’s preferred, though, that you ask one question at a time. Is that supposed to be $8a_{n-2}$ in the first problem? (And could you take a moment to answer my question here?) – Brian M. Scott Oct 14 '15 at 20:30
• @Sameer: I’m going to roll back that edit, The $a_{n-2}$ in the first problem is probably correct, but we don’t know that for a fact, and the $a_{n-1}$ in the second is almost certainly incorrect. – Brian M. Scott Oct 14 '15 at 20:57
• Isn't first recurrence missing an initial condition for $a_0$? Anyway, you could use substitution $b_n = a_n - 1$ to get rid of constant $3$ and then use power series and find generating function. – Ennar Oct 14 '15 at 21:11

writing $∑_1 := \sum_{n=1}^∞$, \begin{align} A(x) &= \sum_{n=1}^∞ a_n x^n \\&= a_1x + a_2x^2 + \sum_{n=1}^∞ a_{n+2}x^{n+2} \\&= 0 + a_2x^2 + x^2∑_1\left(6a_{n+1}-8a_n+3\right)x^n \\&= a_2x^2 + x^2\left[ 6∑_1 a_{n+1}x^n - 8A(x) + 3∑_1x^n \right] \\&= a_2x^2 + x^2\Big[ 6\frac{A(x)-\color{red}{\overbrace{\color{black}{a_1x}}^{=0}}}{x} - 8A(x) + \frac{3x}{1-x}\Big] \\&= a_2x^2 + 6xA(x) - 8x^2A(x) + \frac{3x^3}{1-x} \end{align} So that

$$A(x) = \frac{a_2x^2 + \frac{3x^3}{1-x}}{8x^2-6x+1} = \frac{a_2x^2-a_2x^3 + 3x^3}{(8x^2-6x+1)(1-x)}$$

Expanding the right hand side as a Taylor series will give the answer. Alternatively, finish using the partial fraction decomposition (if you aren't a masochist, try W|A.)

Shift indices of the first one to get:

\begin{align} a_{n + 2} = 6 a_{n + 1} - 8 a_n + 3 \end{align}

Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get:

\begin{align} \sum_{n \ge 0} a_{n + 2} z^n &= 6 \sum_{n \ge 0} a_{n + 1} z^n - 8 \sum_{n \ge 0} a_n z^n + 3 \sum_{n \ge 0} z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 6 \frac{A(z) - a_0}{z} - 8 A(z) + 3 \frac{1}{1 - z} \end{align}

Solving for $A(z)$, as partial fractions:

\begin{align} A(z) &= \frac{1 - 7 z + 9 z^2}{1 - 7 z + 14 z^2 - 8 z^3} \\ &= \frac{1}{1 - z} + \frac{1}{2} \frac{1}{1 - 2 z} - \frac{1}{2} \frac{1}{1 - 4 z} \end{align}

This is just a bunch of geometric series:

\begin{align} a_n = 1 + \frac{1}{2} \cdot 2^n - \frac{1}{2} \cdot 4^n \end{align}