Consider the following sum:
$$\sum_{k=0}^{n}F_k^2=F_nF_{n+1}$$
Where $F_n$ is the nth Fibonacci number.
Using a little of algebra it's easy to show that the sum telescopes to $F_nF_{n+1}$.
Now define
$$G(F,r):=\sum_{k=0}^{n}F_k^r$$ Where $r$ is a natural number.
Still using binomial theorem it's possible to find a formula for $G(F,r)$, although the process of calculating would be cumbersome, the first sum can be viewed as a counting problem which has been done here.
Let's compute $G(F,3)$ by hand:
The first 11 Fibonacci terms are : $0,1,1,2,3,5,8,13,21,34,55$
$$0^3=0$$ $$0^3+1^3=1$$ $$0^3+1^3+1^3=2$$ $$0^3+1^3+1^3+2^3=10$$ $$0^3+1^3+1^3+2^3+3^3=37$$ $$0^3+1^3+1^3+2^3+3^3+5^3=162$$ $$0^3+1^3+1^3+2^3+3^3+5^3+8^3=674$$
I cannot see any pattern or at least the pattern is not obvious.
If we denote $f_n$ to be the number of ways to tile a board of length $n$ with squares of size $1×1$ and dominoes of size $1×2$ then it's known that $f_n=F_{n+1}$.
Since I don't know what is the RHS of $G(F,3)$ and since I cannot see any pattern , so I'm not able to using tiles to derive a formula.
My questions are :
- Is there any closed formula for $G(F,r)$?
- What would be the combinatorial interpretation for $G(F,3)$