## Reciprocal-Fibonacci Series

2018 Jan 30

Evaluate the following infinite series, where $$F_n$$ is the nth fibonacci number with $$F_1=F_2=1$$:
$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_k F_{k+5}}=\space\space\space ?$
$\sum_{k=1}^\infty \frac{1}{F_k F_{k+6}}=\space\space\space ?$
$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_{5k-1}F_{5k+4}}=\space\space\space ?$
$\sum_{k=1}^\infty \frac{1}{F_{10k}F_{10k+10}}=\space\space\space ?$

To evaluate these series, consider the functions $$\Phi_n(x)$$ defined as
$\Phi_n(x):=\sum_{k=1}^\infty \frac{x^{k+1}}{F_k F_{k+n}}$
where $$F_k$$ are the Fibonacci numbers, with $$F_1=F_2=1$$. In this post, I shall endeavour to evaluate a few particular value of $$\Phi_n(x)$$, establish a few of its functional equations to make computation easier, and use the functional equations to evaluate related sums.

First, recall the following well-known identities:
$F_{k+n}=F_k F_{n-1}+F_{k+1}F_n$
$F_k^2-F_{k+1}F_{k-1}=(-1)^{k+1}$
which I will use frequently throughout the post.

I shall begin by computing $$\Phi_1(-1)$$ and $$\Phi_2(1)$$, which are both straightforward telescoping sums:
\begin{align} \Phi_1(-1) &= \sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_k F_{k+1}}\\ &= 1+\sum_{k=2}^\infty \frac{F_k^2-F_{k+1}F_{k-1}}{F_k F_{k+1}}\\ &= 1-\sum_{k=2}^\infty \frac{F_{k-1}}{F_{k}}-\frac{F_k}{F_{k+1}}\\ &= 1-1+\lim_{k\to\infty} \frac{F_k}{F_{k+1}}\\ &= \phi^{-1}\\ \end{align}
Where $$\phi$$ is the golden ratio $$\frac{1+\sqrt 5}{2}$$. Next, we have
\begin{align} \Phi_2(1) &= \sum_{k=1}^\infty \frac{1}{F_k F_{k+2}}\\ &= \sum_{k=1}^\infty \frac{1}{F_k F_{k+1}}-\frac{1}{F_{k+1}F_{k+2}}\\ &= 1+\lim_{k\to\infty} \frac{1}{F_{k+1}F_{k+2}}\\ &= 1\\ \end{align}

Now I will establish a recurrence relation that allows one to compute additional values of $$\Phi_n(x)$$ using the two previously computed as initial conditions.

Theorem 1:
$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}-\frac{F_{n-1}}{F_n}\frac{\Phi_{n-1}(x)}{x}+\frac{F_{n-1}x}{F_n^2}$

Proof:

\begin{align} \Phi_n(x) &=\sum_{k=1}^\infty \frac{x^{k+1}}{F_k F_{k+n}}\\ &=\sum_{k=1}^\infty \frac{x^{k+1}}{F_k (F_k F_{n-1}+F_{k+1}F_n)}\\ &=\sum_{k=1}^\infty \frac{x^{k+1}}{F_{k+1}F_n}\bigg(\frac{1}{F_k}-\frac{F_{n-1}}{F_{k+n}}\bigg)\\ &=\frac{\Phi_1(x)}{F_n}-\frac{F_{n-1}}{F_n}\sum_{k=1}^\infty \frac{x^{k+1}}{F_{k+1}F_{k+n}}\\ &=\frac{\Phi_1(x)}{F_n}+\frac{F_{n-1}}{F_n}\bigg(\frac{x}{F_n}-\sum_{k=1}^\infty \frac{x^{k}}{F_{k}F_{k+n-1}}\bigg)\\ &=\frac{\Phi_1(x)}{F_n}+\frac{F_{n-1}}{F_n}\bigg(\frac{x}{F_n}-\frac{\Phi_{n-1}(x)}{x}\bigg)\\ &= \frac{\Phi_1(x)}{F_n}-\frac{F_{n-1}}{F_n}\frac{\Phi_{n-1}(x)}{x}+\frac{F_{n-1}x}{F_n^2}\space\space\space\space\space\space\blacksquare\\ \end{align}

Through this formula, one may recursively calculate many values of $$\Phi_n(1)$$ and $$\Phi_{n}(-1)$$. For example, using $$\Phi_1(-1)=\phi^{-1}$$ as previously calculated,
\begin{align} \Phi_2(-1) &=\frac{\Phi_1(-1)}{F_2}-\frac{F_1}{F_2}\frac{\Phi_1(-1)}{-1}+\frac{F_1 (-1)}{F_2^2}\\ &=2\Phi_1(-1)-1\\ &=2\phi^{-1}-1\\ \end{align}

and

\begin{align} \Phi_3(-1) &=\frac{\Phi_1(-1)}{F_3}-\frac{F_2}{F_3}\frac{\Phi_2(-1)}{-1}+\frac{F_2 (-1)}{F_3^2}\\ &=\frac{\phi^{-1}}{2}+\frac{2\phi^{-1}-1}{2}-\frac{1}{4}\\ &=\frac{3\phi^{-1}}{2}-\frac{3}{4}\\ \end{align}

In fact, one may solve the recurrence relation to obtain the following:

Theorem 2:
$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}\sum_{k=0}^{n-1} (-x)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-x)^{1-k}F_{n-k-1}}{F_{n-k}},\space\space\space n\ge 1$

Proof: The base case of this formula - with $$n=1$$ - holds trivially, so I will now begin the induction step.

Suppose that
$\Phi_m(x)=\frac{\Phi_1(x)}{F_m}\sum_{k=0}^{m-1} (-x)^{-k}-\frac{1}{F_m}\sum_{k=0}^{m-1}\frac{(-x)^{1-k}F_{m-k-1}}{F_{m-k}}$
is true for some $$m$$. Then it follows that
$-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)=-\frac{\Phi_1(x)}{F_{m+1}x}\sum_{k=0}^{m-1} (-x)^{-k}+\frac{1}{F_{m+1} x}\sum_{k=0}^{m-1}\frac{(-x)^{1-k}F_{m-k-1}}{F_{m-k}}$
$-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=1}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m-1}\frac{(-x)^{-k}F_{m-k-1}}{F_{m-k}}$
$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m-1}\frac{(-x)^{-k}F_{m-k-1}}{F_{m-k}}$
$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)+\frac{F_m x}{F_{m+1}^2}=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m-1}\frac{(-x)^{-k}F_{m-k-1}}{F_{m-k}}+\frac{F_m x}{F_{m+1}^2}$
$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)+\frac{F_m x}{F_{m+1}^2}=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=1}^{m}\frac{(-x)^{1-k}F_{m-k}}{F_{m-k+1}}+\frac{F_m x}{F_{m+1}^2}$
$\frac{\Phi_1(x)}{F_{m+1}}-\frac{F_{m}}{F_{m+1} x}\Phi_m(x)+\frac{F_m x}{F_{m+1}^2}=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m}\frac{(-x)^{1-k}F_{m-k}}{F_{m-k+1}}$
By Theorem 1, the LHS is equal to $$\Phi_{m+1}(x)$$, and so
$\Phi_{m+1}(x)=\frac{\Phi_1(x)}{F_{m+1}}\sum_{k=0}^{m} (-x)^{-k}-\frac{1}{F_{m+1}}\sum_{k=0}^{m}\frac{(-x)^{1-k}F_{m-k}}{F_{m-k+1}}$
Which shows that the formula holds for $$m+1$$ as well. Thus, by induction, it holds for all $$n\ge 1$$. $$\blacksquare$$

Corollary 1:
$\Phi_n(-1)=\frac{n\phi^{-1}}{F_n}-\frac{1}{F_n}\sum_{k=0}^{n-1} \frac{F_k}{F_{k+1}},\space\space\space n\ge 1$

Proof: This follows directly from Theorem 2, since
$\sum_{k=0}^{n-1} 1^{-k}=n$
and since $$\Phi_1(-1)=\phi^{-1}$$. $$\blacksquare$$

Corollary 2:
$\Phi_{2n}(1)=\frac{1}{F_{2n}}\sum_{k=0}^{2n-1}\frac{(-1)^{k}F_{2n-k-1}}{F_{2n-k}},\space\space\space n\ge 1$

Proof: This follows directly from Theorem 2, since
$\sum_{k=0}^{n-1} (-1)^{-k}=\begin{cases} 0 & \text{if n is even}\\ 1 & \text{if n is odd} \end{cases}$

$$\blacksquare$$

Corollary 3:
$\Phi_{2n+1}(1)=\frac{\Phi_1(1)}{F_{2n+1}}+\frac{1}{F_{2n+1}}\sum_{k=1}^{n}\frac{1}{F_{2k}F_{2k+1}}, \space\space\space n\in\mathbb N, \space n\ge 1$

Proof: This follows directly from Theorem 2, since
$\sum_{k=0}^{n-1} (-1)^{-k}=\begin{cases} 0 & \text{if n is even}\\ 1 & \text{if n is odd} \end{cases}$

$$\blacksquare$$

Having derived these formulas, the answers to the first two proposed problems come easily:
$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_k F_{k+5}}=\phi^{-1}-\frac{83}{150}$
$\sum_{k=1}^\infty \frac{1}{F_k F_{k+6}}=\frac{143}{960}$

I will now demonstrate how to use $$\Phi_n(x)$$ to evaluate a class of rather intimidating sums - sums in the form
$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}},\space\space\text{with}\space\space\space 0\le m\le n-1$
To evaluate these sums, I will make use of the properties of the complex roots of unity:
$\omega_n := \cos \frac{2\pi}{n}+i\sin \frac{2\pi}{n}$
I will now state two elementary properties (without proof) of the complex roots of unity that I will make use of later:
$\sum_{p=0}^{n-1} (\omega_n^p)^k= \begin{cases} n & \text{if} \space\space\space n|k\\ 0 & \text{else} \end{cases}\tag 1$
$\sum_{k=0}^{n-1} (\omega_n^p)^k= \begin{cases} n & \text{if} \space\space\space \omega_n^p=1\\ 0 & \text{else}\\ \end{cases}\tag 2$

As a result,

Theorem 3:
If
$G(x):=\sum_{k=1}^\infty x^k a_k$
Then
$\sum_{p=0}^{n-1}(\omega_n^p)^m G(\omega_n^p)=n\sum_{k=1}^\infty a_{nk-m}$

Proof: This theorem follows directly from properties (1) and (2) of the complex roots of unity. $$\blacksquare$$

Using the solution to the generalized recurrence and these identities, one may prove the following:

Theorem 4:
$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_n F_{n-m}}\bigg],\space\space\space n\ge 2, \space\space 0\le m\le n-1$

Proof: I shall divide this proof into two cases - one for even $$n$$, and one for odd $$n$$. We shall consider even $$n$$ first.

Suppose $$n$$ is even. I will begin with the following formula from Theorem 2:
$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}\sum_{k=0}^{n-1} (-x)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-x)^{1-k}F_{n-k-1}}{F_{n-k}}$
Letting $$x=\omega_n^p$$, we have
$\Phi_n(\omega_n^p)=\frac{\Phi_1(\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (-\omega_n^p)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{1-k}F_{n-k-1}}{F_{n-k}}$
$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{(-1)^{m-1}\Phi_1(\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (-\omega_n^p)^{m-k-1}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
By property (2) of the roots of unity, when $$\omega_n^p\ne -1$$, this is equal to
$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
and when $$\omega_n^p=-1$$, it is equal to
$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\Phi_1(-1)}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
$(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
This tells us that, since exactly one of the $$\omega_n^p$$ with $$p$$ between $$0$$ and $$n-1$$ is equal to $$-1$$,
$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\sum_{p=0}^{n-1}\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(-\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\sum_{p=0}^{n-1}(-\omega_n^p)^{m-k}\bigg)$
Now note that since the sum $$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-k}$$ cycles through the nth roots of unity, and since when $$n$$ is even, $$\omega_n^p$$ being a root of unity implies that $$-\omega_n^p$$ is also a root of unity, it is equal to the sum $$\sum_{p=0}^{n-1}(\omega_n^p)^{m-k}$$. Thus,
$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\sum_{p=0}^{n-1}(\omega_n^p)^{m-k}\bigg)$
and, by identity (1), this is
$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\cdot\begin{cases} n & \text{if} \space\space\space n|m-k\\ 0 & \text{else} \end{cases}\bigg)$
Now, if one assumes that $$0\le m\le n-1$$, the only value of $$k$$ between $$0$$ and $$n-1$$ satisfying $$n|m-k$$ would be $$k=m$$. Thus, all terms of the sum are multiplied by zero except for the $$k=m$$ term, and all that remains is
$\sum_{p=0}^{n-1}(\omega_n^p)^{m-1}\Phi_n(\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{n(-1)^{m-1}F_{n-m-1}}{F_nF_{n-m}}$
Using Theorem 3, one may replace the LHS:
$\sum_{k=1}^\infty \frac{n}{F_{nk-m}F_{nk+n-m}}=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{n(-1)^{m-1}F_{n-m-1}}{F_nF_{n-m}}$
$\sum_{k=1}^\infty \frac{1}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg]$
and, because $$n$$ is even, this is equivalent to
$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg]$
Which completes the proof for the case of even $$n$$.

Now suppose that $$n$$ is odd. Again, I will begin with the following formula from Theorem 2:
$\Phi_n(x)=\frac{\Phi_1(x)}{F_n}\sum_{k=0}^{n-1} (-x)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(-x)^{1-k}F_{n-k-1}}{F_{n-k}}$
but this time, I will let $$x=-\omega_n^p$$, so that
$\Phi_n(-\omega_n^p)=\frac{\Phi_1(-\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (\omega_n^p)^{-k}-\frac{1}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{1-k}F_{n-k-1}}{F_{n-k}}$
$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{(-1)^{m-1}\Phi_1(-\omega_n^p)}{F_n}\sum_{k=0}^{n-1} (\omega_n^p)^{m-k-1}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
By property (2) of the roots of unity, when $$\omega_n^p\ne 1$$, this is equal to
$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
and when $$\omega_n^p=1$$, it is equal to
$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\Phi_1(-1)}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
$(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
Because of this, one may say that
$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\sum_{p=0}^{n-1}\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\frac{(\omega_n^p)^{m-k}F_{n-k-1}}{F_{n-k}}$
$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\sum_{p=0}^{n-1}(\omega_n^p)^{m-k} \bigg)$
By property (1), this is
$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\sum_{k=0}^{n-1}\bigg(\frac{F_{n-k-1}}{F_{n-k}}\cdot \begin{cases} n & \text{if} \space\space\space n|m-k\\ 0 & \text{else} \end{cases} \bigg)$
If one assumes that $$0\le m\le n-1$$, the only term of the sum that does not vanish is the term for which $$k=m$$. Thus,
$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=\frac{n(-1)^{m-1}\phi^{-1}}{F_n}-\frac{(-1)^{m-1}}{F_n}\frac{nF_{n-m-1}}{F_{n-m}}$
$\sum_{p=0}^{n-1}(-\omega_n^p)^{m-1}\Phi_n(-\omega_n^p)=(-1)^{m-1}\bigg[\frac{n\phi^{-1}}{F_n}-\frac{nF_{n-m-1}}{F_nF_{n-m}}\bigg]$
By Theorem 3, the LHS can be replaced with an infinite series:
$n\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{n\phi^{-1}}{F_n}-\frac{nF_{n-m-1}}{F_nF_{n-m}}\bigg]$
and so, at last,
$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg]$
Which completes the proof for the case of odd $$n$$. Thus I have established that
$\sum_{k=1}^\infty \frac{(-1)^{nk}}{F_{nk-m}F_{nk+n-m}}=(-1)^{m-1}\bigg[\frac{\phi^{-1}}{F_n}-\frac{F_{n-m-1}}{F_nF_{n-m}}\bigg],\space\space\space n\ge 2, \space\space 0\le m\le n-1 \space\space\space\blacksquare$

With this formula, the third and fourth proposed problems may be solved readily:
$\sum_{k=1}^\infty \frac{(-1)^{k+1}}{F_{5k-1}F_{5k+4}}= \frac{2}{15}-\frac{\phi^{-1}}{5}$
$\sum_{k=1}^\infty \frac{1}{F_{10k}F_{10k+10}}=\frac{\phi^{-1}}{55}-\frac{34}{3025}$