Let's consider a recurrence: $A_{0}=0$, $A_{1}=1$, $ A_{n}=A_{n-1}+A_{n-2}+F_{n}$, where $F_{n}$ is the $n$th Fibonacci number. How to express $A_{n}$ in a closed form?
Despite the fact that it sounds easy, i got stuck after a number of attempts( i've tried to evaluate the generating function of $A_{n}$)
Any hints that may help?
Let $F(x)$ be the generating function of the Fibonacci sequence, and $A(x)$ be the generating function of your sequence.
We have $$F(x)= \frac{x}{1-x-x^2},$$ so $(1-x-x^2)A(x) = x + F(x)$. By multiplying both sides by $F(x) $, we get $$A(x) = F(x) + F(x)^2.$$
Now, all you have to do is to compare the coefficient of $x^n$ on both sides.