*2018 Jan 30*

Evaluate the following infinite series, where $F_n$ is the

nthfibonacci number with $F_1=F_2=1$:

To evaluate these series, consider the functions $\Phi_n(x)$ defined as 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: 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: Where $\phi$ is the golden ratio $\frac{1+\sqrt 5}{2}$. Next, we have

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:

**Proof:**

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,

and

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

Theorem 2:

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

Suppose that is true for some $m$. Then it follows that By Theorem 1, the LHS is equal to $\Phi_{m+1}(x)$, and so Which shows that the formula holds for $m+1$ as well. Thus, by induction, it holds for all $n\ge 1$. $\blacksquare$

Corollary 1:

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

Corollary 2:

**Proof:** This follows directly from Theorem 2, since

$\blacksquare$

Corollary 3:

**Proof:** This follows directly from Theorem 2, since

$\blacksquare$

Having derived these formulas, the answers to the first two proposed problems come easily:

I will now demonstrate how to use $\Phi_n(x)$ to evaluate a class of rather intimidating sums - sums in the form To evaluate these sums, I will make use of the properties of the complex roots of unity: I will now state two elementary properties (without proof) of the complex roots of unity that I will make use of later:

As a result,

Theorem 3:If Then

**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:

**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: Letting $x=\omega_n^p$, we have By property (2) of the roots of unity, when $\omega_n^p\ne -1$, this is equal to and when $\omega_n^p=-1$, it is equal to This tells us that, since exactly one of the $\omega_n^p$ with $p$ between $0$ and $n-1$ is equal to $-1$, 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, and, by identity (1), this is 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 Using Theorem 3, one may replace the LHS: and, because $n$ is even, this is equivalent to 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: but this time, I will let $x=-\omega_n^p$, so that By property (2) of the roots of unity, when $\omega_n^p\ne 1$, this is equal to and when $\omega_n^p=1$, it is equal to Because of this, one may say that By property (1), this is 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, By Theorem 3, the LHS can be replaced with an infinite series: and so, at last, Which completes the proof for the case of odd $n$. Thus I have established that

With this formula, the third and fourth proposed problems may be solved readily:

back to home page