# 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?

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.

• @vadim123 Oh...Did not realize exponent. Sorry! I've added a link to sum of powers of Fibonacci numbers above. – Noble Mushtak Jun 30 '16 at 3:28
• Since $F_n=(a^n-b^n)/\sqrt 5 ,$ where $a=(1+\sqrt 5)/2$ and $b=(1-\sqrt 5)/2=-1/a,$ individual cases with small $k$ (like $k=1$ or $2$) can be evaluated with the binomial theorem and the summing of geometric series. But I haven't looked into it . – DanielWainfleet Jun 30 '16 at 3:34
• @user254665 Yes, that is in my answer. – Noble Mushtak Jun 30 '16 at 3:35
• @user230452 Thank you so much! – Noble Mushtak Jun 30 '16 at 14:47
• Hey, I'm in high school too :) USACO is pretty cool. Also, you can always use Tor or a VPN... I mean I use scihub all the time, I wouldn't be able to do anything if I couldn't. It might not be legal but I think we can agree it's ethical, especially for people our age. – Elliot Gorokhovsky Jun 30 '16 at 17:30

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.