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