<s>[INST] Recurrence relation $a_{n} = a_{n-1}+a_{n-2}+n$ How to solve this recurrence relation?
$a_{n} = a_{n-1}+a_{n-2}+n,a_{1}=a_{0}=1$
What I have tried:
$r^2 = r + 1  \rightarrow r = \frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}$
non-homogeneous part:
$$
\begin{split}
a_{n} &= cn+b \implies c(n)+b = c(n-1) + b + c(n-2) + b + n\\
0     &= -3c+b+n(c+1) \implies c+1 = 0 \iff c=-1 \implies b = -4 \\
a_{n} &= c_{0} \left(\frac{1+\sqrt{5}}{2}\right)^n
       + c_{1} \left(\frac{1-\sqrt{5}}{2}\right)^n -n-4
\end{split}
$$
putting $a_{0}$ and $a_{1}$ in recurrence relation gives $c_{0} = (\frac{1}{2})(5+\frac{7}{\sqrt{5}})$ and $c_{1} = (\frac{1}{2})(5-\frac{7}{\sqrt{5}})$.
I am sure my answer is wrong because for n greater than 1 it doesn't work. help me correct my mistake, please.
 [/INST] the last equation
$$
0 = n(c+1) + (b-3c),
$$
which implies $c+1 = 0 \iff c=-1$ and $b = 3c = -3 \ne -4$.
</s>