6
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @vadim123 Oh...Did not realize exponent. Sorry! I've added a link to sum of powers of Fibonacci numbers above. $\endgroup$ – Noble Mushtak Jun 30 '16 at 3:28
  • $\begingroup$ 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 . $\endgroup$ – DanielWainfleet Jun 30 '16 at 3:34
  • $\begingroup$ @user254665 Yes, that is in my answer. $\endgroup$ – Noble Mushtak Jun 30 '16 at 3:35
  • 1
    $\begingroup$ @user230452 Thank you so much! $\endgroup$ – Noble Mushtak Jun 30 '16 at 14:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Elliot Gorokhovsky Jun 30 '16 at 17:30
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.