# Solve recurrence equations-homework extras

Extras from my homework. The first one should be easier, but still hard enough.

1) $a_{n+3}-(3/2)a_{n+2}-a_{n+1}-(1/4)a_n=0$

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

-
looks like very good homework. It is slightly hard, but certainly worth the effort. (a spoiler: scale the negative numbers so you get 1 as sum, solve, scale back to original) – tp1 Dec 13 '11 at 21:32
I've edited in some parentheses since $3/2a_{n+2}$ could otherwise be interpreted as $3/(2a_{n+2})$. Of course, if $3/(2a_{n+2})$ was what you actually meant, you'll have to re-edit. – Gerry Myerson Dec 13 '11 at 22:20
I think the way this is going to work best is, you show us what you know, how far you get, where you get stuck, and we try to help you over the rough spots. – Gerry Myerson Dec 13 '11 at 22:21
Well, they are extras for students who love math. I hate math :D I think in first one are some complex roots, second one is to hard. Frenkly, I posted this question because of bonus points and I am not sure if I want to be able solve equations like this on my own. So feel free to solve it for me, if you want, or let it go ;) – Ondrej Janacek Dec 14 '11 at 8:36

These are linear difference equations. There is a general theory about them.

For the homogeneous equation 1) make the "Ansatz" $a_n:=C\ \lambda^n$ $\ (n\geq 0)$. There will be at most three admissible $\lambda$'s, called eigenvalues of 1). Assuming you found three different such $\lambda_i$ the general form of the solution of 1) is

$$a_n\ =\ C_1\lambda_1^n +C_2\lambda_2^n+C_3\lambda_3^n\qquad(n\geq 0)$$

with arbitrary constants $C_i$.

As for the inhomogeneous equation 2), a basic principle says that the general solution of 2) can be written as the sum of the general solution of 1) (which we already have) and a single solution of 2) found by inspired guessing. Looking at the right side of 2) an inspired guess is the "Ansatz"

$$a_n\ :=\ A+Bn+Cn^2 + D\ 2^n$$

with coefficients $A$, $B$, $C$, $D$ to be determined. Plugging this "Ansatz" into 2) you will get a simple system of linear equations for these coefficients. When you have solved this system the general solution of 2) is given by

$$a_n\ =\ C_1\lambda_1^n +C_2\lambda_2^n+C_3\lambda_3^n+A+Bn+Cn^2 + D\ 2^n\qquad(n\geq 0)$$

-
Given OP's attitude, I'm surprised anyone is eager to put in any amount of work for him. – Gerry Myerson Dec 15 '11 at 12:18
@Gerry Myerson: I was unhappy with the first answer, but had overlooked the OP's own comment concerning his question. – Christian Blatter Dec 15 '11 at 13:35

First problem

Hint:

For the first one, you can use the same trick of the fibonacci numbers.

The characteristic polynomial for this question is:

$$q^3-\frac{3q^2}{2}-q-\frac{1}{4}=0\;.$$

The second Mathematica says:

Solution:

\begin{align*} a(n)&= c_1 \left(2-\sqrt{3}\right)^n+c_2 \left(2+\sqrt{3}\right)^n+c_3 (-1)^n\\\\ &+\frac{-24 \sqrt{3} \zeta \left(-2,\frac{n}{2}\right)+48 \zeta \left(-2,\frac{n}{2}\right)+24 \sqrt{3} \zeta \left(-2,\frac{n+1}{2}\right)-48 \zeta \left(-2,\frac{n+1}{2}\right)}{9 \left(\sqrt{3}-1\right)^3 \left(1+\sqrt{3}\right)}\\\\ &+\frac{12 \sqrt{3} n^2-24 n^2-30 \sqrt{3} n+60 n-2^{n+3}+\sqrt{3} 2^{n+2}+27 \sqrt{3}-54}{9 \left(\sqrt{3}-1\right)^3 \left(1+\sqrt{3}\right)} \end{align*}

-

Use Wilf's "generatingfunctionology" techniques. Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply the recurrence by $z^n$ and sum over $n \ge 0$ to get for (1): $$\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} - \frac{3}{2} \frac{A(z) - a_0 - a_1 z}{z^2} - \frac{A(z) - a_0}{z} - \frac{1}{4} A(z) = 0$$ Solve for $A(z)$, split into partial fractions. The expansions: $$(1 - u)^{-m} = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} u^n$$ will be all that is needed. It works with complex roots too.

For (2) you'll need: $$\sum_{n \ge 0} n^2 z^n = z \frac{d}{dz} ( z \frac{d}{dz} \sum_{n \ge 0} z^2 ) = z \frac{d}{dz} ( z \frac{d}{dz} \frac{1}{1 - z} ) = \frac{z + z^2}{(1 - z)^3}$$ and also: $$\sum_{n \ge 0} 2^n z^n = \sum_{n \ge 0} (2 z)^n = \frac{1}{1 - 2 z}$$

-