1. [10] What is the answer to Leonardo Fibonacci’s original problem: How many pairs of rabbits are present after a year?

The original problem assumes we start with a single pair of rabbits and a monthly period. Let $k$ represent the number of months that have passed and our sequence by $S_k$, so that that initially we start with

$$S_0=1=F_2=F_{0+2}\text{ pair.}$$

After a year, we have

$$S_{12}=F_{12+2}=F_{14}=377\text{ pairs,}$$

and in general, after $k$ months, we have

$$S_k=F_{k+2}\text{ pairs.}$$

$▸$ 2. [20] In view of Eq. (15), what is the approximate value of $F_{1000}$? (Use logarithms found in Appendix A.)

Given Eq. (15)

$$F_n={\varphi }^n∕\sqrt{5}\text{ rounded to the nearest integer,}$$

we may use the logarithms found in Appendix A to find that

$$\begin{array}{llll}\hfill F_{1000}& \approx e^{\ln <!--FUNCTION\; APPLICATION-->({\varphi }^{1000}∕\sqrt{5})}& \hfill & \\ \hfill & =e^{1000\ln <!--FUNCTION\; APPLICATION-->\varphi -\frac{1}{2}\ln <!--FUNCTION\; APPLICATION-->5}& \hfill & \\ \hfill & =e^{1000\ln <!--FUNCTION\; APPLICATION-->\varphi -\frac{1}{2}\ln <!--FUNCTION\; APPLICATION-->5}& \hfill & \\ \hfill & =e^{1000\ln <!--FUNCTION\; APPLICATION-->\varphi -\frac{1}{2}(\ln <!--FUNCTION\; APPLICATION-->10-\ln <!--FUNCTION\; APPLICATION-->2)}& \hfill & \\ \hfill & \approx e^{408.40711}& \hfill & \\ \hfill & \approx 10^{408.40711∕\ln <!--FUNCTION\; APPLICATION-->10}& \hfill & \\ \hfill & \approx 10^{208.63816}& \hfill & \\ \hfill & \approx 4.34666\times 10^{208}\text{.}\text{.}& \hfill & \end{array}$$

That is, $F_{1000}$ is a 209-digit number whose leading digit is $4$.

3. [25] Write a computer program that calculates and prints $F_1$ through $F_{1000}$ in decimal notation. (The previous exercise determines the size of numbers that must be handled.)

The following Java code calculates and prints $F_1$ through $F_{1000}$, by assuming nonnegative integers no larger than 209 digits.

class FibonacciNumber { 
 
   public FibonacciNumber(int initialValue) { 
      decimalDigits = new int[209]; 
      for (decimalDigitCount = 0; initialValue != 0; ++decimalDigitCount) { 
         decimalDigits[decimalDigitCount] = initialValue % 10; 
         initialValue /= 10; 
      } 
   } 
 
   public FibonacciNumber plus(FibonacciNumber fibonacciNumber) { 
      FibonacciNumber sum = new FibonacciNumber(0); 
      int carry = 0; 
      for ( 
         int k = 0; 
         k < Math.max(decimalDigitCount, fibonacciNumber.decimalDigitCount); 
         ++k 
      ) { 
         int thisDigit = (k < decimalDigitCount) ? 
            decimalDigits[k] : 0; 
         int thatDigit = (k < fibonacciNumber.decimalDigitCount) ? 
            fibonacciNumber.decimalDigits[k] : 0; 
         int digitSum = thisDigit + thatDigit + carry; 
         sum.decimalDigits[sum.decimalDigitCount++] = digitSum % 10; 
         carry = digitSum / 10; 
      } 
      if (carry > 0) { 
         sum.decimalDigits[sum.decimalDigitCount++] = carry; 
      } 
      return (sum); 
   } 
 
   public String toString() { 
      StringBuilder stringBuilder = new StringBuilder(); 
      for (int k = decimalDigitCount - 1; k >= 0; --k) { 
         stringBuilder.append(decimalDigits[k]); 
      } 
      if (stringBuilder.length() == 0) { 
         stringBuilder.append(0); 
      } 
      return (stringBuilder.toString()); 
   } 
 
   private int[] decimalDigits; 
   private int decimalDigitCount; 
 
} 
 
FibonacciNumber[] fibonacci = new FibonacciNumber[1000]; 
int k = 0; 
System.out.println(fibonacci[k] = new FibonacciNumber(1)); 
++k; 
System.out.println(fibonacci[k] = fibonacci[k - 1]); 
for (++k; k < fibonacci.length; ++k) { 
   System.out.println(fibonacci[k] = fibonacci[k - 1].plus(fibonacci[k - 2])); 
}

The first thirty numbers generated are listed below,

$n$	$F_n$
1	1
2	1
3	2
4	3
5	5
6	8
7	13
8	21
9	34
10	55
11	89
12	144
13	233
14	377
15	610
16	987
17	1597
18	2584
19	4181
20	6765
21	10946
22	17711
23	28657
24	46368
25	75025
26	121393
27	196418
28	317811
29	514229
30	832040

and $F_{1000}$ is printed as anticipated, a 209-digit number whose leading digit is $4$:

43466	55768	69374	56435	68852	76750	40625	80256	46605	17371
78040	24817	29089	53655	54179	49051	89040	38798	40079	25516
92959	22593	08032	26347	75209	68962	32398	73322	47116	16429
96440	90653	31879	38298	96964	99285	16003	70447	61377	95166
84922	8875.

$▸$ 4. [14] Find all $n$ for which $F_n=n$.

Manually inspecting $F_n$ until $F_{n-1}>n$

$n$	$F_n$
0	0
1	1
2	1
3	2
4	3
5	5
6	8
7	13

reveals $F_n=n$ for $n=0$, $1$, and $5$. For $n>5$, $F_n$ increases faster than $n$, letting us conclude that these are the only $n$, as may be seen by the inductive argument that follows.

In the case that $n=6$, clearly $F_n=F_6=8>6=n$. Similarly, in the case that $n=7$, $F_n=F_7=13>7=n$. Then, assuming $F_n>n$ for $n>5$, we must show that $F_{n+1}>n+1$. But

$$\begin{array}{llll}\hfill F_{n+1}& =F_n+F_{n-1}& \hfill & \\ \hfill & >n+n-1& \hfill & \\ \hfill & >n+1& \hfill & \\ \hfill & & \hfill \end{array}$$

since $n>5$ by hypothesis, and hence the conclusion.

5. [20] Find all $n$ for which $F_n=n^2$.

Manually inspecting $F_n$ until $F_{n-1}>n^2$

$n$	$n^2$	$F_n$
0	0	0
1	1	1
2	4	1
3	9	2
4	16	3
5	25	5
6	36	8
7	49	13
8	64	21
9	81	34
10	100	55
11	121	89
12	144	144
13	169	233
14	196	377

reveals $F_n=n^2$ for $n=0$, $1$, and $12$. For $n>12$, $F_n$ increases faster than $n$, letting us conclude that these are the only $n$, as may be seen by the inductive argument that follows.

In the case that $n=13$, clearly $F_n=F_{13}=233>169=13^2=n^2$. Similarly, in the case that $n=14$, $F_n=F_{14}=377>196=14^2=n^2$. Then, assuming $F_n>n^2$ for $n>12$, we must show that $F_{n+1}>{(n+1)}^2$. But

$$\begin{array}{llll}\hfill F_{n+1}& =F_n+F_{n-1}& \hfill & \\ \hfill & >n^2+{(n-1)}^2& \hfill & \\ \hfill & =n^2+n^2-2n+1& \hfill & \\ \hfill & >n^2+2n+1& \hfill & \\ \hfill & ={(n+1)}^2& \hfill & \\ \hfill & & \hfill \end{array}$$

since $n>12$ by hypothesis, and hence the conclusion.

6. [HM10] Prove Eq. (5).

Proposition. $\left(\begin{array}{cc}\hfill F_{n+1}\hfill & \hfill F_n\hfill \\ \hfill F_n\hfill & \hfill F_{n-1}\hfill \\ \hfill \hfill \end{array}\right)={\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^n$.

Proof. Let $n$ be an arbitrary positive integer. We must show that

$$\left(\begin{array}{cc}\hfill F_{n+1}\hfill & \hfill F_n\hfill \\ \hfill F_n\hfill & \hfill F_{n-1}\hfill \\ \hfill \hfill \end{array}\right)={\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^n\text{.}$$

In the case that $n=1$,

$$\begin{array}{llll}\hfill \left(\begin{array}{cc}\hfill F_{1+1}\hfill & \hfill F_1\hfill \\ \hfill F_1\hfill & \hfill F_{1-1}\hfill \\ \hfill \hfill \end{array}\right)& =\left(\begin{array}{cc}\hfill F_2\hfill & \hfill F_1\hfill \\ \hfill F_1\hfill & \hfill F_0\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & ={\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^1\text{;}& \hfill & \\ \hfill & & \hfill \end{array}$$

and in the case that $n=2$,

$$\begin{array}{llll}\hfill \left(\begin{array}{cc}\hfill F_{2+1}\hfill & \hfill F_2\hfill \\ \hfill F_2\hfill & \hfill F_{2-1}\hfill \\ \hfill \hfill \end{array}\right)& =\left(\begin{array}{cc}\hfill F_3\hfill & \hfill F_2\hfill \\ \hfill F_2\hfill & \hfill F_1\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill 2\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 1\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill 1+1\hfill & \hfill 1+0\hfill \\ \hfill 1+0\hfill & \hfill 1+0\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill 1\cdot 1+1\cdot 1\hfill & \hfill 1\cdot 1+1\cdot 0\hfill \\ \hfill 1\cdot 1+0\cdot 1\hfill & \hfill 1\cdot 1+0\cdot 0\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & ={\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^2\text{.}& \hfill & \\ \hfill & & \hfill \end{array}$$

Then, assuming

$$\left(\begin{array}{cc}\hfill F_{n+1}\hfill & \hfill F_n\hfill \\ \hfill F_n\hfill & \hfill F_{n-1}\hfill \\ \hfill \hfill \end{array}\right)={\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^n\text{,}$$

we must show that

$$\left(\begin{array}{cc}\hfill F_{n+2}\hfill & \hfill F_{n+1}\hfill \\ \hfill F_{n+1}\hfill & \hfill F_n\hfill \\ \hfill \hfill \end{array}\right)={\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^{n+1}\text{.}$$

But

$$\begin{array}{llll}\hfill \left(\begin{array}{cc}\hfill F_{n+2}\hfill & \hfill F_{n+1}\hfill \\ \hfill F_{n+1}\hfill & \hfill F_n\hfill \\ \hfill \hfill \end{array}\right)& =\left(\begin{array}{cc}\hfill F_{n+1}+F_n\hfill & \hfill F_n+F_{n-1}\hfill \\ \hfill F_{n+1}\hfill & \hfill F_n\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill 1\cdot F_{n+1}+1\cdot F_n\hfill & \hfill 1\cdot F_n+1\cdot F_{n-1}\hfill \\ \hfill 1\cdot F_{n+1}+0\cdot F_n\hfill & \hfill 1\cdot F_n+0\cdot F_{n-1}\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)\left(\begin{array}{cc}\hfill F_{n+1}\hfill & \hfill F_n\hfill \\ \hfill F_n\hfill & \hfill F_{n-1}\hfill \\ \hfill \hfill \end{array}\right)& \hfill & \\ \hfill & =\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right){\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^n& \hfill & \\ \hfill & ={\left(\begin{array}{cc}\hfill 1\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill \\ \hfill \hfill \end{array}\right)}^{n+1}\text{.}& \hfill & \end{array}$$

as we needed to show. □

$▸$ 7. [15] If $n$ is not a prime number, $F_n$ is not a prime number (with one exception). Prove this and find the exception.

Proposition. If $n$ is not a prime number, $F_n$ is not a prime number, with the one exception being $n=4$ where $F_4=3$.

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that if $n$ is not a prime number, $F_n$ is not a prime number, with the one exception being $n=4$ where $F_4=3$.

In the case that $n=0$ not prime, $F_0=0$ not prime; similarly for $n=1$, $F_1=1$. Otherwise, let us assume $n>2$ not prime, such that $d$ is a proper divisor of $n$ ($d|n$, $1<d<n$) such that $n=dm$ for some positive integer $m$. Deduced from Eq. (6) we know that $F_d$ divides $F_n$. Since $d>1$, $F_d\ge 1$; and since $n>2$, $F_d<F_n$. That is, $1\le F_d<F_n$.

Hence, $F_n$ is not prime in all cases except where $F_d=1$, or equivalently since $d>1$, where $d=2$. The only composite number $n$ that has no proper factor greater than $2$ is $n=4$, being the one exception, where $F_4=3$, as we needed to show. □

8. [15] In many cases it is convenient to define $F_n$ for negative $n$, by assuming that $F_{n+2}=F_{n+1}+F_n$ for all integers $n$. Explore this possibility: What is $F_{-1}$? What is $F_{-2}$? Can $F_{-n}$ be expressed in a simple way in terms of $F_n$?

Allowing $n$ to range over all integers, we require

$$F_1=F_0+F_{-1}\text{,}$$

or equivalently,

$$\begin{array}{llll}\hfill F_{-1}& =F_1-F_0& \hfill & \\ \hfill & =1-0& \hfill & \\ \hfill & =1\text{.}& \hfill & \end{array}$$

Similarly,

$$\begin{array}{llll}\hfill F_{-2}& =F_0-F_{-1}& \hfill & \\ \hfill & =0-1& \hfill & \\ \hfill & =-1\text{,}& \hfill & \end{array}$$

and in general for nonegative $n$,

$$F_{-n}={(-1)}^{n+1}{F}_n\text{,}$$

as is shown below.

Proposition. $F_{-n}=F_{-n+2}-F_{-n+1}={(-1)}^{n+1}{F}_n$.

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that

$$F_{-n}=F_{-n+2}-F_{-n+1}={(-1)}^{n+1}{F}_n\text{.}$$

In the case that $n=0$,

$$\begin{array}{llll}\hfill F_0& =F_2-F_1& \hfill & \\ \hfill & =1-1& \hfill & \\ \hfill & =0& \hfill & \\ \hfill & ={(-1)}^{0+1}{F}_0\text{;}& \hfill & \end{array}$$

and in the case that $n=1$,

$$\begin{array}{llll}\hfill F_{-1}& =F_1-F_0& \hfill & \\ \hfill & =1-0& \hfill & \\ \hfill & =1& \hfill & \\ \hfill & ={(-1)}^{1+1}{F}_1\text{.}& \hfill & \\ \hfill & & \hfill \end{array}$$

Then, assuming

$$F_{-n}=F_{-n+2}-F_{-n+1}={(-1)}^{n+1}{F}_n\text{,}$$

we must show that

$$F_{-(n+1)}=F_{-(n+1)+2}-F_{-(n+1)+1}={(-1)}^{(n+1)+1}{F}_{n+1}\text{.}$$

But

$$\begin{array}{llll}\hfill F_{-(n+1)}& =F_{-(n+1)+2}-F_{-(n+1)+1}& \hfill & \\ \hfill & =F_{-n+1}-F_{-n}& \hfill & \\ \hfill & ={(-1)}^{(n-1)+1}{F}_{n-1}-{(-1)}^{n+1}{F}_n& \hfill & \\ \hfill & ={(-1)}^n{F}_{n-1}-{(-1)}^{n+1}{F}_n& \hfill & \\ \hfill & ={(-1)}^n{F}_{n-1}+{(-1)}^n{F}_n& \hfill & \\ \hfill & ={(-1)}^n\left(F_{n-1}+F_n\right)& \hfill & \\ \hfill & ={(-1)}^n{F}_{n+1}& \hfill & \\ \hfill & ={(-1)}^{n+2}{F}_{n+1}& \hfill & \\ \hfill & ={(-1)}^{(n+1)+1}{F}_{n+1}& \hfill & \\ \hfill & & \hfill \end{array}$$

as we needed to show. □

9. [M20] Using the conventions of exercise 8, determine whether Eqs. (4), (6), (14), and (15) still hold when the subscripts are allowed to be any integers.

We determine that Eqs. (4), (6), and (14) hold if $n$ is allowed to range over all the integers, but not Eq. (15), as given by counterexample.

Proposition. $F_{n+1}{F}_{n-1}-F_n^2={(-1)}^n$ for negative $n$.

Proof. Let $n$ be an arbitrary negative integer. We must show that

$$F_{n+1}{F}_{n-1}-F_n^2={(-1)}^n\text{.}$$

In the case that $n=-1$,

$$F_0{F}_{-2}-F_{-1}^2=-1={(-1)}^{-1}\text{;}$$

and in the case that $n=-2$,

$$F_{-1}{F}_{-3}-F_{-2}^2=2-1=1={(-1)}^{-2}\text{.}$$

Then, assuming

$$F_{n+1}{F}_{n-1}-F_n^2={(-1)}^n\text{,}$$

we must show that

$$F_n{F}_{n-2}-F_{n-1}^2={(-1)}^{n-1}\text{.}$$

But

$$\begin{array}{llll}\hfill F_n{F}_{n-2}-F_{n-1}^2& =(F_{n+1}-F_{n-1})(F_n-F_{n-1})-F_{n-1}^2& \hfill & \\ \hfill & =F_{n+1}{F}_n-F_{n-1}{F}_n-F_{n+1}{F}_{n-1}+F_{n-1}^2-F_{n-1}^2& \hfill & \\ \hfill & =F_{n+1}{F}_n-F_{n-1}{F}_n-F_{n+1}{F}_{n-1}& \hfill & \\ \hfill & =F_n(F_{n+1}-F_{n-1})-F_{n+1}{F}_{n-1}& \hfill & \\ \hfill & =F_n{F}_n-F_{n+1}{F}_{n-1}& \hfill & \\ \hfill & =F_n^2-F_{n+1}{F}_{n-1}& \hfill & \\ \hfill & =(-1)(F_{n+1}{F}_{n-1}-F_n^2)& \hfill & \\ \hfill & =(-1){(-1)}^n& \hfill & \\ \hfill & ={(-1)}^{n-1}& \hfill & \\ \hfill & & \hfill \end{array}$$

as we needed to show. □

Proposition. $F_{n+m}=F_m{F}_{n+1}+F_{m-1}{F}_n$ for negative $n$.

Proof. Let $n$ and $m$ be arbitrary integers such that $n$ is negative and $m$ is nonnegative. We must show that

$$F_{n+m}=F_m{F}_{n+1}+F_{m-1}{F}_n\text{.}$$

In the case that $n=-1$,

$$F_{-1+m}=F_{m-1}=F_m{F}_0+F_{m-1}{F}_{-1}\text{;}$$

and in the case that $n=-2$,

$$F_{-2+m}=F_m-F_{m-1}=F_m{F}_{-1}+F_{m-1}{F}_{-2}\text{.}$$

Then, assuming

$$F_{n+m}=F_m{F}_{n+1}+F_{m-1}{F}_n$$

we must show that

$$F_{n+m-1}=F_m{F}_n+F_{m-1}{F}_{n-1}\text{.}$$

But

$$\begin{array}{llll}\hfill F_{n+m-1}& =F_{n+m+1}-F_{n+m}& \hfill & \\ \hfill & =F_m{F}_{n+2}+F_{m-1}{F}_{n+1}-F_m{F}_{n+1}-F_{m-1}{F}_n& \hfill & \\ \hfill & =F_m(F_{n+2}-F_{n+1})+F_{m-1}(F_{n+1}-F_n)& \hfill & \\ \hfill & =F_m{F}_n+F_{m-1}{F}_{n-1}& \hfill & \\ \hfill & & \hfill \end{array}$$

as we needed to show. □

Proposition. $F_n=\frac{1}{\sqrt{5}}\left({\varphi }^n-{\widehat{\varphi }}^n\right)$ for negative $n$.

Proof. Let $n$ be an arbitrary negative integer. We must show that

$$F_n=\frac{1}{\sqrt{5}}\left({\varphi }^n-{\widehat{\varphi }}^n\right)\text{.}$$

In the case that $n=-1$,

$$\begin{array}{llll}\hfill F_{-1}& =1& \hfill & \\ \hfill & =\frac{\sqrt{5}}{\sqrt{5}}& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{-4\sqrt{5}}{-4}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{2(1-\sqrt{5})-2(1+\sqrt{5})}{(1+\sqrt{5})(1-\sqrt{5})}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{2}{1+\sqrt{5}}-\frac{2}{1-\sqrt{5}}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^{-1}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{-1}-{\widehat{\varphi }}^{-1}\right)\text{;}& \hfill & \\ \hfill & & \hfill \end{array}$$

and in the case that $n=-2$,

$$\begin{array}{llll}\hfill F_{-2}& =-1& \hfill & \\ \hfill & =\frac{-\sqrt{5}}{\sqrt{5}}& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{-16\sqrt{5})}{16}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{4(6-2\sqrt{5})-4(6+2\sqrt{5})}{6^2-4{\sqrt{5}}^2}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{4}{6+2\sqrt{5}}-\frac{4}{6-2\sqrt{5}}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{4}{{\left(1+\sqrt{5}\right)}^2}-\frac{4}{{\left(1-\sqrt{5}\right)}^2}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^{-2}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{-2}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{-2}-{\widehat{\varphi }}^{-2}\right)\text{.}& \hfill & \end{array}$$

Then, assuming

$$F_n=\frac{1}{\sqrt{5}}\left({\varphi }^n-{\widehat{\varphi }}^n\right)\text{,}$$

we must show that

$$F_{n-1}=\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-{\widehat{\varphi }}^{n-1}\right)\text{.}$$

But

$$\begin{array}{llll}\hfill F_{n-1}& =F_{n+1}-F_n& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n+1}-{\widehat{\varphi }}^{n+1}\right)-\frac{1}{\sqrt{5}}\left({\varphi }^n-{\widehat{\varphi }}^n\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n+1}-{\widehat{\varphi }}^{n+1}-{\varphi }^n+{\widehat{\varphi }}^n\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n+1}-{\varphi }^n-{\widehat{\varphi }}^{n+1}+{\widehat{\varphi }}^n\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\left(\varphi -1\right){\varphi }^n-\left(\widehat{\varphi }-1\right){\widehat{\varphi }}^n\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\left({\varphi }^2-\varphi \right){\varphi }^{n-1}-\left({\widehat{\varphi }}^2-\widehat{\varphi }\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\varphi \left(\frac{1+\sqrt{5}}{2}-1\right){\varphi }^{n-1}-\left({\widehat{\varphi }}^2-\widehat{\varphi }\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\varphi \left(\frac{-1+\sqrt{5}}{2}\right){\varphi }^{n-1}-\left({\widehat{\varphi }}^2-\widehat{\varphi }\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\frac{-1+\sqrt{5}}{2}{\varphi }^{n-1}-\left({\widehat{\varphi }}^2-\widehat{\varphi }\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{-1+{\sqrt{5}}^2}{4}{\varphi }^{n-1}-\left({\widehat{\varphi }}^2-\widehat{\varphi }\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left(\frac{4}{4}{\varphi }^{n-1}-\left({\widehat{\varphi }}^2-\widehat{\varphi }\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-\left({\widehat{\varphi }}^2-\widehat{\varphi }\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-\widehat{\varphi }\left(\frac{1-\sqrt{5}}{2}-1\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-\widehat{\varphi }\left(\frac{-1-\sqrt{5}}{2}\right){\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-\frac{1-\sqrt{5}}{2}\frac{-1-\sqrt{5}}{2}{\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-\frac{-1+{\sqrt{5}}^2}{4}{\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-\frac{4}{4}{\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & =\frac{1}{\sqrt{5}}\left({\varphi }^{n-1}-{\widehat{\varphi }}^{n-1}\right)& \hfill & \\ \hfill & & \hfill \end{array}$$

as we needed to show. □

Proposition. $F_n\ne \frac{{\varphi }^n}{\sqrt{5}}$ rounded to the nearest integer for negative $n$.

Proof. Consider $n=-1$. Then $F_{-1}=1$ but since $\sqrt{5}>2$,

$$\begin{array}{llll}\hfill \frac{{\varphi }^{-1}}{\sqrt{5}}& =\frac{2}{1+\sqrt{5}}\frac{1}{\sqrt{5}}& \hfill & \\ \hfill & =\frac{2}{\sqrt{5}+5}& \hfill & \\ \hfill & <\frac{2}{2+5}& \hfill & \\ \hfill & =\frac{2}{7}& \hfill & \end{array}$$

rounded to the nearest integer is $0$. □

10. [15] Is ${\varphi }^n∕\sqrt{5}$ greater than $F_n$ or less than $F_n$?

From Eq. (14),

$$F_n=\frac{1}{\sqrt{5}}\left({\varphi }^n-{\widehat{\varphi }}^n\right)\text{,}$$

if and only if

$$\frac{{\varphi }^n}{\sqrt{5}}-F_n=\frac{{\widehat{\varphi }}^n}{\sqrt{5}}\text{.}$$

That is, $\frac{{\varphi }^n}{\sqrt{5}}$ is greater than $F_n$ when

$$\frac{{\widehat{\varphi }}^n}{\sqrt{5}}>0\iff {\widehat{\varphi }}^n>0$$

and less than $F_n$ when negative. Since

$$\begin{array}{llll}\hfill \sqrt{5}>1& \iff 1-\sqrt{5}<0& \hfill & \\ \hfill & \iff \frac{1-\sqrt{5}}{2}<0& \hfill & \\ \hfill & \iff \widehat{\varphi }<0\text{,}& \hfill & \\ \hfill & & \hfill \end{array}$$

we have that ${\widehat{\varphi }}^n>0$ when $n$ is even, negative when odd. That is, $\frac{{\varphi }^n}{\sqrt{5}}$ is greater than $F_n$ when $n$ is even, less than $F_n$ when $n$ is odd.