I have to prove the following identity, where $F_n$ are Fibonacci numbers and $F_{0}=F_{1}=1$
$$\sum_{k=0}^{n}F_{k}F_{n-k}=\sum_{k=0}^{n}(k+1)F_{k+1}(-2)^{n-k}.$$
I am trying to do it by induction, but i am stuck at the induction step.
I have $$\sum_{k=0}^{n+1}F_{k}F_{n+1-k}=\sum_{k=0}^{n}F_{k}F_{n+1-k}+F_{n+1}=\sum_{k=0}^{n}F_{k}(F_{n-k}+F_{n-k-1})+F_{n+1}\\=\sum_{k=0}^{n}F_{k}F_{n-k}+\sum_{k=0}^{n}F_{k}F_{n-k-1}+F_{n+1}.$$
Okay, in the last part I can use for the part $\sum_{k=0}^{n}F_{k}F_{n-k}$ the assumption that it works for $n$, but what do I do with the rest? I guess I have to come at $-2\sum_{k=0}^{n}(k+1)F_{k+1}(-2)^{n-k}$.
Thanks in advance for the help
EDIT: I would need to do it using induction if that would be possible, so i edited the question
