How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?
$f(n)$ is the well-known Fibonacci sequence.

Let $\alpha=\frac{1+\sqrt5}2$ be the golden ratio and $\phi=\frac{1-\sqrt5}2$. It is shown here that
$$f(n)=(\alpha^n-\phi^{n})/\sqrt5$$



Gnasher729 conjectured that $F(n) \approx 0.72 * n * f(n)$. Following that clue, we can find the following identity holds for all cases we tested by trial and error.
$$F(n)= nf(n) - (n-2)f(n-2) + (n-4)f(n-4) - (n-6)f(n-6) + \cdots$$
where the sequence of summands goes on as long as the summand makes sense.



How to prove that long formula? We can observe it implies for $n\ge2$,
$$ F(n) = nf(n) - F(n-2).$$

Let us prove that simple recurrence relation of $F(n)$ by induction on $n$.

The base cases when $n=2$ and when $n=3$ is easy since f(2)=1, f(3)=2, F(2)=1+0+1=2 and F(3)=2+1+2=5.

Suppose it is true for $n\le k$, where $k\ge3$.
$$\begin{aligned}
F(k+1) =&amp; F(k) + F(k-1) + f(k+1)\\
=&amp; (kf(k) - F(k-2)) + ((k-1)f(k-1) - F(k-3)) + f(k+1)\\
=&amp; k(f(k)+f(k-1))-f(k-1) - (F(k-2)+F(k-3)) + f(k+1)\\
=&amp; kf(k+1)-f(k-1) - (F(k-1)-f(k-1)) + f(k+1)\\
=&amp; (k+1)f(k+1)- F(k-1)\\
\end{aligned}$$

Now that we have proved that simple recurrence relation of $F(n)$, it is immediate to prove that long formula, which can also be stated succinctly as

$$F(n)=\sum_{0\le i\lt n, i\text{ even}}(-1)^{i/2}f(n-i)$$



Interested readers may enjoy the following exercises, roughly in the order of increasing difficulty.

Exercise 1. Given the above formulas for $f(n)$ and $F(n)$, show that $F(n)=\Theta(n\alpha^n)$.

Exercise 2. Given the above formulas for $f(n)$ and $F(n)$, show that $$\lim_{n\to\infty}\frac{F(n)}{n\alpha^n}= \frac1{1+\alpha^{-2}}\approx 0.7236$$

Exercise 3. Find a close formula for $F(n)$.