2
$\begingroup$

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$

  • 0
    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 ;)2011-12-14

3 Answers 3

1

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

  • 0
    @Gerry Myerson: I was unhappy with the first answer, but had overlooked the OP's own comment concerning his question.2011-12-15
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*}$

0

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