Does sketching the Pascal Triangle help?

Great problem, Christoper! +1

I'll rewrite this summation as below

$\displaystyle \sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \dbinom{n-i}{i}$

I will prove that this expression is equivalent to $f_{n+1}$ , where $f_x$ is the $x$ th term of the Fibonacci sequence.

Consider the number of ways to walk up $n$ stairs taking 1 or 2 steps at a time. Here, you can take $i$ double steps and $n-2i$ single steps, so by the Supermarket Principle, there are $\dbinom {n-2i+i}{i}=\dbinom{n-i}{i}$ number of ways of going up $n$ stairs using $i$ double steps. Summing this for all $i$ , there are

$\displaystyle \sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \dbinom{n-i}{i}$

number of ways of doing so. However, we can also recursively define this. Let $A_n$ denote the number of ways of climbing $n$ stairs using single or double steps. We have that $A_n=A_{n-1}+A_{n-2}$ since it only requires a single or double step to get to the $n$ th stair, respectively. We also have $A_1$ as 1 and $A_2$ as 2. Notice that $f_2 = 1$ , $f_3=2$ , and both this stair-counting and Fibonacci sequences are similarly defined (i.e. $A_1=f_2$ , $A_2=f_3$ , etc). Thus, we must have $A_n=f_{n+1}$ . Therefore,

$\displaystyle \sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor} \dbinom{n-i}{i} = f_{n+1}$

We will now prove $\text{gcd}(f_m, f_n) = f_{\text{gcd}(m,n)}$ .

Let's break this down into manageable chunks we can prove more easily.

Part 1: $\text{gcd}(f_n, f_{n-1}) = 1$ for all positive integers $n$ .

We have $\text{gcd}(f_n, f_{n_1}) = \text{gcd}(f_{n-1}+f_{n-2}, f_{n_1}) = \text{gcd}(f_{n-1}, f_{n_2})$ , by the division algorithm. Thus, if we apply this repeatedly, we have

$\text{gcd}(f_n, f_{n-1}) = \text{gcd}(f_{n-1}, f_{n-2}) = \text{gcd}(f_{n-2}, f_{n-3}) = \ldots = \text{gcd}(f_{2}, f_{1}) = 1$

Thus, our first lemma is true.

Part 2: $f_{m+n} = f_{m+1} f_n + f_{m} f_{n-1}$ for all positive integers $m$ and $n$ greater than 1.

The above statement directly follows if we can induct the below expression on $k$ :

$f_N = f_{k+1} f_{N-k} + f_k f_{N-k-1}$

for all positive integers $N>1$ and all $k=1,2,...,N-2$ .This statement is easily seen to be true for $k=1$ and the induction will be complete once we have verified that $f_{k+1} f_{N-k}+f_k f_{N-k-1} = f_{k+2} f_{N-k-1} + f_{k+1} f_{N-k-2}$ . However, this is equivalent to $f_{k+1} (f_{N-k} - f_{N-k-2}) = f_{N-k-1} (f_{k+2} - f_k)$ , which on turn is equivalent to $f_{k+1} f_{N-k-1} = f_{N-k-1} f_{k+1}$ . This expression is obviously true, so we are done. Therefore, our second lemma is true.

Part 3: If $m \mid n$ , then $f_m \mid f_n$ .

We will prove by induction on $k$ that $f_m \mid f_{km}$ for every positive integer $k$ . The statement is easily seen to be true when $k=1$ . Furthermore, $f_m \mid f_{km}$ implies $f_m \mid f_{km+1} f_m + f_{km} f_{m-1} = f_{(m+1)k}$ from our second lemma. Thus, this is easily shown by induction to be true.

Part 4: If $n=qm+r$ , then $\text{gcd}(f_{m}, f_{n}) = \text{gcd}(f_{m}, f_{r})$ .

We simply write $f_n=f_{qm+r}=f_{qm+1}f_r+f_{qm}f_{r-1}$ , which implies that

$\begin{aligned} \text{gcd}(f_{m}, f_{n}) &= \text{gcd}(f_{m}, f_{qm+1}f_r + f_{qm} f_{r-1})\\ &= \text{gcd}(f_{m}, f_{qm+1}f_r)\\ &= \text{gcd}(f_{m}, f_{r}) \end{aligned}$

where we used the division algorithm from the first line to the second line, and used the first lemma to pass from the second line to the third line.

If we write $n=qm+r$ , then the statement $\text{gcd}(f_{m}, f_{n}) = \text{gcd}(f_{m}, f_{r})$ is quite similar to the statement $\text{gcd}(m, n)=\text{gcd}(m, r)$ , which is the the basis of Euclid's algorithm. In fact, the only difference is that the letter $f$ has been added into the picture. Therefore, applying Euclid's algorithm to two Fibonacci numbers gives the result $\text{gcd}(f_{m}, f_{n})=f_{\text{gcd}(m, n)}$ .

Finally, we have $F(101)=f_{102}$ and $F(118)=f_{119}$ , and $\text{gcd}(102, 119)=17$ , so our answer is $f_{17}=1597$ . QED