Recurrence relation with quadratic equation

Question

Situation: working on a homework problem for my discrete math class that I think is solved, but I am now wondering if my solution is right. This a is a recurrence relations problem with a quadratic equation to find the roots and then an extra term to deal with.

The question: Solve homogenous problem: $A_n = A_{n-1} + A_{n-2} + 2^n$ for $n \ge 2$.

My solution is: Roots $= \dfrac{1 \pm \sqrt{5}}{2}$

So I have $A_n = C_1\left( \dfrac{1 + \sqrt{5}}{2}\right)^n + C_2\left( \dfrac{1 - \sqrt{5}}{2}\right)^n $ where $C_1$ and $C_2$ are constants.

For the $2^n$, I have set the following: $A(2^n) - A(2^{n-1}) - A(2^{n-2}) = 2^n$, $A(1 -1/2 - 1/4) = 1$ then $A((4-2-1)/4) = 1$ or $A=4$.

For a particular solution, $A_n = 4(2)^n$.

Putting this all together, I have: $A_n = C_1\left( \dfrac{1 + \sqrt{5}}{2}\right)^n + C_2\left( \dfrac{1 - \sqrt{5}}{2}\right)^n + 4(2)^n$.

Am I on the right track? Any hints would be appreciated.

Answer 1

Yeah! Seems quite good. Btw here's another nice way to eliminate the extra term and work out the recurrence:

Multiplying the giving recurrence by a factor of 2, seems like a hint to to me.

$$2A_n = 2A_{n-1} + 2A_{n-2} + 2^{n+1}$$

And also observe that

$$A_{n+1} = A_{n} + A_{n-1} + 2^{n+1}$$

From where we can easily eliminate the extra term and get $A_{n+1} - 3A_n + A_{n-1} + 2A_{n-2} = 0$ whose characteristic polynomial is $x^3-3x^2+x+2 = 0$ which in turn factorizes as $(x-2)(x-\varphi)(x+\varphi^{-1}) = 0$ where $\varphi = \frac{1+\sqrt{5}}{2}$ which is exactly what you got.

Answer 2

Here's an alternative approach using generating functions. We have the recurrence:

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

We convert the recurrence to a power series:

$$ \sum_{n = 2}^{\infty} a_n x^n = \sum_{n = 1}^{\infty} a_n x^{n + 1} + \sum_{n = 0}^{\infty} a_n x^{n + 2} + \sum_{n = 2}^{\infty}2^n x^n $$

We define $A(x)$:

$$ A(x) = \sum_{n = 0}^{\infty} a_n x^n $$

Substituting into the equation for the series and using properties of convergence of series we get:

$$ A(x) - a_0 - a_1 x = x(A(x) - a_0) + x^2 A(x) + \frac{1}{1 - 2x} - 1 - 2x $$

Rearranging and simplifying we get:

$$ (1 - x - x^2) A(x) = a_0 + (a_1 - a_0) x + \frac{4x^2}{1 - 2x} $$ $$ = a + b x + \frac{4x^2}{1 - 2x} $$

Or:

$$ A(x) = \frac{a + bx}{1 - x - x^2} + \frac{4x^2}{(1 - x - x^2)(1 - 2x)} $$

The roots of $1 - x - x^2$ are:

$$ c = -\frac{1}{2} + \frac{1}{2} \sqrt{5} $$ $$ d = -\frac{1}{2} - \frac{1}{2} \sqrt{5} $$

Applying partial fraction decomposition to $A(x)$ we get:

$$ A(x) = \frac{A}{c - x} + \frac{B}{d - x} + \frac{C}{c - x} + \frac{D}{d - x} - \frac{E}{1 - 2x} $$

$$ A = \frac{a + bc}{\sqrt{5}} $$ $$ B = -\frac{a + bd}{\sqrt{5}} $$ $$ C = \frac{6 - 2 \sqrt{5}}{2\sqrt{5} - 5} $$ $$ D = -\frac{6 + 2 \sqrt{5}}{2\sqrt{5} + 5} $$ $$ E = -4 $$

Converting back to series we get:

$$ A(x) = \frac{A}{c} \sum_{n = 0}^{\infty} \left( \frac{x}{c} \right)^n + \frac{B}{d} \sum_{n = 0}^{\infty} \left( \frac{x}{d} \right)^n + \frac{C}{c} \sum_{n = 0}^{\infty} \left( \frac{x}{c} \right)^n + \frac{D}{d} \sum_{n = 0}^{\infty} \left( \frac{x}{d} \right)^n - E \sum_{n = 0}^{\infty} (2x)^n $$

And so we conclude:

$$ a_n = \frac{A + C}{c} \frac{1}{c^n} + \frac{B + D}{d} \frac{1}{d^n} + 4 \cdot 2^n $$

Or more simply:

$$ a_n = \alpha c^{-n} + \beta d^{-n} + 4 \cdot 2^n $$ $$ a_n = \alpha \left( \frac{-1 + \sqrt{5}}{2} \right)^{-n} + \beta \left( \frac{-1 - \sqrt{5}}{2} \right)^{-n} + 4 \cdot 2^n $$

And so we have deduced the explicit form of the recurrence. We verify the validity of the result using induction:

$$ a_n = a_{n - 1} + a_{n - 2} + 2^n $$ $$ = \alpha c^{-(n - 1)} + \beta d^{-(n - 1)} + 4 \cdot 2^{n - 1} + a_{n - 3} + 2^{n - 1} + \alpha c^{-(n - 2)} + \beta d^{-(n - 2)} + 4 \cdot 2^{n - 2} + a_{n - 4} + 2^{n - 2} + 2^n $$ $$ = \alpha c^{-n}(c + c^2) + \beta d^{-n}(d + d^2) + 2 \cdot 2^n + 2^n + 2^n $$ $$ = \alpha c^{-n} + \beta d^{-n} + 4 \cdot 2^n $$

And so the deduced explicit form is valid.