Sum of nth powers of Fibonacci numbers

According to Wikipedia, we have the following: $$\sum_{i=1}^n F_i=F_{n+2}-1$$ $$\sum_{i=1}^n F_i^2=F_nF_{n+1}$$

For sum of higher powers of Fibonacci numbers, look at this helpful blog post.

---

One possible inuition behind these formulas is Binet's formula: $$F_n=\frac{1}{\sqrt 5}\left(\phi^n-\left(-\frac{1}{\phi}\right)^n\right)$$ Then, for any given constant $k$, we can use binomial expansion to get a bunch of terms that have the form $a\cdot b^n$ and we can find the sum of $\sum_{i=1}^n a\cdot b^i$ using the sum of geometric series formula. I'll apply this to the $k=1$ case: $$\sum_{i=1}^n \frac{1}{\sqrt 5}\left(\phi^i-\left(-\frac{1}{\phi}\right)^i\right)$$ Bring the $\frac{1}{\sqrt 5}$ out of the sumation: $$\frac{1}{\sqrt 5}\sum_{i=1}^n \left(\phi^i-\left(-\frac{1}{\phi}\right)^i\right)$$ Distribute the summation over the terms: $$\frac{1}{\sqrt 5}\left(\sum_{i=1}^n\phi^i-\sum_{i=1}^n\left(-\frac{1}{\phi}\right)^i\right)$$ Use geometric series formula: $$\frac{1}{\sqrt 5}\left(\phi\frac{\phi^n-1}{\phi-1}-\frac{1}{\phi}\frac{\left(-\frac{1}{\phi}\right)^n-1}{\frac{1}{\phi}+1}\right)$$ Use identities about $\phi$: $$\frac{1}{\sqrt 5}\left(\phi\frac{\phi^n-1}{\frac{1}{\phi}}-\frac{1}{\phi}\frac{\left(-\frac{1}{\phi}\right)^n-1}{\phi}\right)$$ Simplify: $$\frac{1}{\sqrt 5}\left(\phi^{n+2}-\phi^2-\left(-\frac{1}{\phi}\right)^{n+2}+\left(-\frac{1}{\phi}\right)^2\right)$$ Note that $\left(-\frac{1}{\phi}\right)^2-\phi^2=-\sqrt 5$: $$\frac{1}{\sqrt 5}\left(\phi^{n+2}-\left(-\frac{1}{\phi}\right)^{n+2}-\sqrt 5\right)$$ Partially distribute the $\frac{1}{\sqrt 5}$: $$\frac{1}{\sqrt 5}\left(\phi^{n+2}-\left(-\frac{1}{\phi}\right)^{n+2}\right)-\frac{1}{\sqrt 5}\cdot \sqrt 5$$ Use Binet's Formula and simplify: $$F_{n+2}-1$$ As you can see, this method is very cumbersome, so it's probably impractical for very high powers.

Consider a generalized Fibonacci sequence $\{U_n\}$ with $U_n=U_n(p,q)$ defined as $U_0=0$, $U_1=1$, and $U_{n+2}=-qU_n+pU_{n+1}$ for all $n\geq0$. It is prove that

$$\sum_{i=1}^nU_i^m=\frac{1}{\sum_{i=1}^m{m\atopwithdelims\{\}i}}\left(\sum_{i=1}^nU_{im-\binom{m+1}{2}}+\sum_{i=1}^m{m\atopwithdelims\{\}i}\sum_{j=1}^i(U_{n-i+j}^m-U_{j-i}^m)\right),$$ in which $${m\atopwithdelims\{\}i}=\left(\prod_{\underset{j=1}{j\neq i}}^mU_{j-i}\right)^{-1}.$$ Also, note that in the above formula $$\sum_{x=1}^nU_{ax+b}=\frac{q^aU_{na+b}-U_{(n+1)a+b}-q^aU_{b-a}+U_b}{1+q^a-V_a}-U_b$$ for all integers $a,b$. See here.