<s>[INST] Recurrence relation with quadratic equation 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.
 [/INST] 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.
</s>