Sum of nth powers of Fibonacci numbers Is a closed form for
$$\sum_{i=1}^n{F_i^k}$$
(where $F_i$ is the $i^{th}$ Fibonacci number and $k$ is constant) known?
 A: 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.
A: 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.
