# Summation over k to n of Product of kth with n-kth Fibonacci Numbers

## Theorem

$\ds \sum_{k \mathop = 0}^n F_k F_{n - k} = \dfrac {\paren {n - 1} F_n + 2n F_{n - 1} } 5$

where $F_n$ denotes the $n$th Fibonacci number.

## Proof

$\map G z = \dfrac z {1 - z - z^2}$

Then:

 $\ds \map G z$ $=$ $\ds \dfrac z {1 - z - z^2}$ $\ds$ $=$ $\ds \dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \phi z} - \dfrac 1 {1 - \hat \phi z} }$ Partial Fraction Expansion

where:

$\phi = \dfrac {1 + \sqrt 5} 2$
$\hat \phi = \dfrac {1 - \sqrt 5} 2$

Hence:

 $\ds \paren {\map G z}^2$ $=$ $\ds \paren {\dfrac 1 {\sqrt 5} \paren {\dfrac 1 {1 - \phi z} - \dfrac 1 {1 - \hat \phi z} } }^2$ $\ds$ $=$ $\ds \dfrac 1 5 \paren {\paren {\dfrac 1 {1 - \phi z} }^2 + \paren {\dfrac 1 {1 - \hat \phi z} }^2 - 2 \dfrac 1 {1 - \phi z} \dfrac 1 {1 - \hat \phi z} }$ $\ds$ $=$ $\ds \dfrac 1 5 \paren {\dfrac 1 {\paren {1 - \phi z}^2} + \dfrac 1 {\paren {1 - \hat \phi z}^2} - 2 \dfrac {1 - \hat \phi z + 1 - \phi z} {\paren {1 - \phi z} \paren {1 - \hat \phi z} } }$ $\ds$ $=$ $\ds \dfrac 1 5 \paren {\dfrac 1 {\paren {1 - \phi z}^2} + \dfrac 1 {\paren {1 - \hat \phi z}^2} - \dfrac 2 {\paren {1 - \phi z} \paren {1 - \paren {1 - \phi} z} } }$ Definition of $\hat \phi$ $\ds$ $=$ $\ds \dfrac 1 5 \paren {\dfrac 1 {\paren {1 - \phi z}^2} + \dfrac 1 {\paren {1 - \hat \phi z}^2} - \dfrac 2 {1 - z - z^2} }$ after algebra $\ds$ $=$ $\ds \dfrac 1 5 \paren {\sum_{n \mathop = 0}^\infty \paren {n + 1} \paren {\phi z}^n + \sum_{n \mathop = 0}^\infty \paren {n + 1} \paren {\hat \phi z}^n - \dfrac 2 z \map G z}$ Power Series Expansion for Square of Reciprocal of 1-z $\ds$ $=$ $\ds \dfrac 1 5 \paren {\sum_{n \mathop = 0}^\infty \paren {n + 1} \paren {\phi^n + \hat \phi^n} z^n - \dfrac 2 z \sum_{n \mathop = 0}^\infty F_n z^n}$ Generating Function for Fibonacci Numbers $\ds$ $=$ $\ds \dfrac 1 5 \paren {\sum_{n \mathop = 0}^\infty \paren {n + 1} \paren {\phi^n + \hat \phi^n} z^n - 2 \sum_{n \mathop = 0}^\infty F_n z^{n - 1} }$ $\ds$ $=$ $\ds \dfrac 1 5 \paren {\sum_{n \mathop = 0}^\infty \paren {n + 1} \paren {\phi^n + \hat \phi^n} z^n - 2 \sum_{n \mathop = 1}^\infty F_{n + 1} z^n}$ Translation of Index Variable of Summation $\ds$ $=$ $\ds \dfrac 1 5 \sum_{n \mathop = 0}^\infty \paren {\paren {n + 1} \paren {\phi^n + \hat \phi^n} - 2 F_{n + 1} } z^n$

Since the coefficient of $z^n$ in $\paren {\map G z}^2$ is $\ds \sum_{k \mathop = 0}^n F_k F_{n - k}$, by comparing coefficients:

 $\ds \sum_{k \mathop = 0}^n F_k F_{n - k}$ $=$ $\ds \dfrac 1 5 \paren {\paren {n + 1} \paren {\phi^n + \hat \phi^n} - 2 F_{n + 1} }$ $\ds$ $=$ $\ds \dfrac 1 5 \paren {\paren {n + 1} \paren {\dfrac {\phi^{2 n} - \hat \phi^{2 n} } {\sqrt 5} \times \dfrac {\sqrt 5} {\phi^n - \hat \phi^n} } - 2 F_{n + 1} }$ Difference of Two Squares $\ds$ $=$ $\ds \dfrac 1 5 \paren {\paren {n + 1} \dfrac {F_{2 n} } {F_n} - 2 F_{n + 1} }$ Euler-Binet Formula $\ds$ $=$ $\ds \dfrac 1 5 \paren {\paren {n + 1} \dfrac {F_{n - 1} F_n + F_n F_{n + 1} } {F_n} - 2 F_{n + 1} }$ Honsberger's Identity $\ds$ $=$ $\ds \dfrac 1 5 \paren {\paren {n + 1} \paren {F_{n - 1} + F_{n + 1} } - 2 F_{n + 1} }$ $\ds$ $=$ $\ds \dfrac 1 5 \paren {\paren {n + 1} \paren {F_n + 2 F_{n - 1} } - 2 \paren {F_n + F_{n - 1} } }$ Definition of Fibonacci Numbers $\ds$ $=$ $\ds \dfrac {\paren {n - 1} F_n + 2n F_{n - 1} } 5$

$\blacksquare$