Exercises from Section 1.2.8

Tord M. Johnson

February 22, 2016

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 Sk, so that that initially we start with

S0 = 1 = F2 = F0+2 pair.

After a year, we have

S12 = F12+2 = F14 = 377 pairs,

and in general, after k months, we have

Sk = Fk+2 pairs.

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

Given Eq. (15)

Fn = ϕn∕5 rounded to the nearest integer,

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

F1000 ≈ eln ⁡ (ϕ1000∕5) = e1000 ln ⁡ ϕ−1 2 ln ⁡ 5 = e1000 ln ⁡ ϕ−1 2 ln ⁡ 5 = e1000 ln ⁡ ϕ−1 2 (ln ⁡ 10−ln ⁡ 2) ≈ e408.40711 ≈ 10408.40711∕ ln ⁡ 10 ≈ 10208.63816 ≈ 4.34666 × 10208..

That is, F1000 is a 209-digit number whose leading digit is 4.

3. [25] Write a computer program that calculates and prints F1 through F1000 in decimal notation. (The previous exercise determines the size of numbers that must be handled.)

The following Java code calculates and prints F1 through F1000, 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,

nFn
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 F1000 is printed as anticipated, a 209-digit number whose leading digit is 4:

43466557686937456435688527675040625802564660517371
78040 24817 29089 53655 54179 49051 89040 38798 40079 25516
92959 225930803226347752096896232398733224711616429
96440 90653 31879 38298 96964 99285 16003 70447 61377 95166
84922 8875.

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

Manually inspecting Fn until Fn−1 > n

nFn
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13

reveals Fn = n for n = 0, 1, and 5. For n > 5, Fn 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 Fn = F6 = 8 > 6 = n. Similarly, in the case that n = 7, Fn = F7 = 13 > 7 = n. Then, assuming Fn > n for n > 5, we must show that Fn+1 > n + 1. But

Fn+1 = Fn + Fn−1 > n + n − 1 > n + 1

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

5. [20] Find all n for which Fn = n2.

Manually inspecting Fn until Fn−1 > n2

nn2Fn
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 Fn = n2 for n = 0, 1, and 12. For n > 12, Fn 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 Fn = F13 = 233 > 169 = 132 = n2. Similarly, in the case that n = 14, Fn = F14 = 377 > 196 = 142 = n2. Then, assuming Fn > n2 for n > 12, we must show that Fn+1 > (n + 1)2. But

Fn+1 = Fn + Fn−1 > n2 + (n − 1)2 = n2 + n2 − 2n + 1 > n2 + 2n + 1 = (n + 1)2

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

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

Proposition. Fn+1 Fn Fn Fn−1 = 11 1 0 n.

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

Fn+1 Fn Fn Fn−1 = 11 1 0 n.

In the case that n = 1,

F1+1 F1 F1 F1−1 = F2F1 F1F0 = 11 1 0 = 11 1 0 1;

and in the case that n = 2,

F2+1 F2 F2 F2−1 = F3F2 F2F1 = 21 1 1 = 1 + 11 + 0 1 + 0 1 + 0 = 1 ⋅ 1 + 1 ⋅ 11 ⋅ 1 + 1 ⋅ 0 1 ⋅ 1 + 0 ⋅ 1 1 ⋅ 1 + 0 ⋅ 0 = 11 1 0 2.

Then, assuming

Fn+1 Fn Fn Fn−1 = 11 1 0 n,

we must show that

Fn+2Fn+1 Fn+1 Fn = 11 1 0 n+1.

But

Fn+2Fn+1 Fn+1 Fn = Fn+1 + FnFn + Fn−1 Fn+1 Fn = 1 ⋅ Fn+1 + 1 ⋅ Fn1 ⋅ Fn + 1 ⋅ Fn−1 1 ⋅ Fn+1 + 0 ⋅ Fn1 ⋅ Fn + 0 ⋅ Fn−1 = 11 1 0 Fn+1 Fn Fn Fn−1 = 11 1 0 11 1 0 n = 11 1 0 n+1.

as we needed to show. □

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

Proposition. If n is not a prime number, Fn is not a prime number, with the one exception being n = 4 where F4 = 3.

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

In the case that n = 0 not prime, F0 = 0 not prime; similarly for n = 1, F1 = 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 Fd divides Fn. Since d > 1, Fd ≥ 1; and since n > 2, Fd < Fn. That is, 1 ≤ Fd < Fn.

Hence, Fn is not prime in all cases except where Fd = 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 F4 = 3, as we needed to show. □

8. [15] In many cases it is convenient to define Fn for negative n, by assuming that Fn+2 = Fn+1 + Fn 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 Fn?

Allowing n to range over all integers, we require

F1 = F0 + F−1,

or equivalently,

F−1 = F1 − F0 = 1 − 0 = 1.

Similarly,

F−2 = F0 − F−1 = 0 − 1 = −1,

and in general for nonegative n,

F−n = (−1)n+1F n,

as is shown below.

Proposition. F−n = F−n+2 − F−n+1 = (−1)n+1Fn.

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

F−n = F−n+2 − F−n+1 = (−1)n+1F n.

In the case that n = 0,

F0 = F2 − F1 = 1 − 1 = 0 = (−1)0+1F 0;

and in the case that n = 1,

F−1 = F1 − F0 = 1 − 0 = 1 = (−1)1+1F 1.

Then, assuming

F−n = F−n+2 − F−n+1 = (−1)n+1F n,

we must show that

F−(n+1) = F−(n+1)+2 − F−(n+1)+1 = (−1)(n+1)+1F n+1.

But

F−(n+1) = F−(n+1)+2 − F−(n+1)+1 = F−n+1 − F−n = (−1)(n−1)+1F n−1 − (−1)n+1F n = (−1)nF n−1 − (−1)n+1F n = (−1)nF n−1 + (−1)nF n = (−1)n F n−1 + Fn = (−1)nF n+1 = (−1)n+2F n+1 = (−1)(n+1)+1F n+1

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. Fn+1Fn−1 − Fn2 = (−1)n for negative n.

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

Fn+1Fn−1 − Fn2 = (−1)n.

In the case that n = −1,

F0F−2 − F−12 = −1 = (−1)−1;

and in the case that n = −2,

F−1F−3 − F−22 = 2 − 1 = 1 = (−1)−2.

Then, assuming

Fn+1Fn−1 − Fn2 = (−1)n,

we must show that

FnFn−2 − Fn−12 = (−1)n−1.

But

FnFn−2 − Fn−12 = (F n+1 − Fn−1)(Fn − Fn−1) − Fn−12 = Fn+1Fn − Fn−1Fn − Fn+1Fn−1 + Fn−12 − F n−12 = Fn+1Fn − Fn−1Fn − Fn+1Fn−1 = Fn(Fn+1 − Fn−1) − Fn+1Fn−1 = FnFn − Fn+1Fn−1 = Fn2 − F n+1Fn−1 = (−1)(Fn+1Fn−1 − Fn2) = (−1)(−1)n = (−1)n−1

as we needed to show. □

Proposition. Fn+m = FmFn+1 + Fm−1Fn for negative n.

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

Fn+m = FmFn+1 + Fm−1Fn.

In the case that n = −1,

F−1+m = Fm−1 = FmF0 + Fm−1F−1;

and in the case that n = −2,

F−2+m = Fm − Fm−1 = FmF−1 + Fm−1F−2.

Then, assuming

Fn+m = FmFn+1 + Fm−1Fn

we must show that

Fn+m−1 = FmFn + Fm−1Fn−1.

But

Fn+m−1 = Fn+m+1 − Fn+m = FmFn+2 + Fm−1Fn+1 − FmFn+1 − Fm−1Fn = Fm(Fn+2 − Fn+1) + Fm−1(Fn+1 − Fn) = FmFn + Fm−1Fn−1

as we needed to show. □

Proposition. Fn = 1 5 ϕn −ϕ̂n for negative n.

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

Fn = 1 5 ϕn −ϕ̂n .

In the case that n = −1,

F−1 = 1 = 5 5 = 1 5 − 45 − 4 = 1 5 2(1 −5) − 2(1 + 5) (1 + 5)(1 −5) = 1 5 2 1 + 5 − 2 1 −5 = 1 5 1 + 5 2 −1 −1 −5 2 −1 = 1 5 ϕ−1 −ϕ̂−1 ;

and in the case that n = −2,

F−2 = −1 = −5 5 = 1 5 − 165) 16 = 1 5 4(6 − 25) − 4(6 + 25) 62 − 452 = 1 5 4 6 + 25 − 4 6 − 25 = 1 5 4 1 + 52 − 4 1 −52 = 1 5 1 + 5 2 −2 −1 −5 2 −2 = 1 5 ϕ−2 −ϕ̂−2 .

Then, assuming

Fn = 1 5 ϕn −ϕ̂n ,

we must show that

Fn−1 = 1 5 ϕn−1 −ϕ̂n−1 .

But

Fn−1 = Fn+1 − Fn = 1 5 ϕn+1 −ϕ̂n+1 − 1 5 ϕn −ϕ̂n = 1 5 ϕn+1 −ϕ̂n+1 − ϕn + ϕ̂n = 1 5 ϕn+1 − ϕn −ϕ̂n+1 + ϕ̂n = 1 5 ϕ − 1ϕn −ϕ̂ − 1ϕ̂n = 1 5 ϕ2 − ϕϕn−1 −ϕ̂2 −ϕ̂ϕ̂n−1 = 1 5 ϕ 1 + 5 2 − 1ϕn−1 −ϕ̂2 −ϕ̂ϕ̂n−1 = 1 5 ϕ − 1 + 5 2 ϕn−1 −ϕ̂2 −ϕ̂ϕ̂n−1 = 1 5 1 + 5 2 − 1 + 5 2 ϕn−1 −ϕ̂2 −ϕ̂ϕ̂n−1 = 1 5 − 1 + 52 4 ϕn−1 −ϕ̂2 −ϕ̂ϕ̂n−1 = 1 5 4 4ϕn−1 −ϕ̂2 −ϕ̂ϕ̂n−1 = 1 5 ϕn−1 −ϕ̂2 −ϕ̂ϕ̂n−1 = 1 5 ϕn−1 −ϕ̂ 1 −5 2 − 1ϕ̂n−1 = 1 5 ϕn−1 −ϕ̂ − 1 −5 2 ϕ̂n−1 = 1 5 ϕn−1 −1 −5 2 − 1 −5 2 ϕ̂n−1 = 1 5 ϕn−1 −− 1 + 52 4 ϕ̂n−1 = 1 5 ϕn−1 −4 4ϕ̂n−1 = 1 5 ϕn−1 −ϕ̂n−1

as we needed to show. □

Proposition. Fn≠ϕn 5 rounded to the nearest integer for negative n.

Proof. Consider n = −1. Then F−1 = 1 but since 5 > 2,

ϕ−1 5 = 2 1 + 5 1 5 = 2 5 + 5 < 2 2 + 5 = 2 7

rounded to the nearest integer is 0. □

10. [15] Is ϕn∕5 greater than Fn or less than Fn?

From Eq. (14),

Fn = 1 5 ϕn −ϕ̂n ,

if and only if

ϕn 5 − Fn = ϕ̂n 5 .

That is, ϕn 5 is greater than Fn when

ϕ̂n 5 > 0⇔ϕ̂n > 0

and less than Fn when negative. Since

5 > 1 ⇔1 −5 < 0 ⇔1 −5 2 < 0 ⇔ϕ̂ < 0,

we have that ϕ̂n > 0 when n is even, negative when odd. That is, ϕn 5 is greater than Fn when n is even, less than Fn when n is odd.

11. [M20] Show that ϕn = Fnϕ + Fn−1 and ϕ̂n = Fnϕ̂ + Fn−1, for all integers n.

We show both identities.

Proposition. ϕn = Fnϕ + Fn−1.

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

ϕn = F nϕ + Fn−1.

We divide the proof into two cases: n nonnegative, or n nonpositive.

In the case that n is nonnegative, if n = 0,

ϕ0 = 1 = 0 + 1 = F 0ϕ + F−1;

and if n = 1,

ϕ1 = ϕ + 0 = F 1ϕ + F0.

Then, assuming

ϕn = F nϕ + Fn−1

we must show that

ϕn+1 = F n+1ϕ + Fn.

But

ϕn+1 = ϕϕn = ϕ Fnϕ + Fn−1 = Fnϕ2 + F n−1ϕ = Fn ϕ + 1 + Fn−1ϕ = Fnϕ + Fn−1ϕ + Fn = Fn + Fn−1 ϕ + Fn = Fn+1ϕ + Fn.

In the case that n is nonpositive, if n = 0,

ϕ0 = 1 = 0 + 1 = F 0ϕ + F−1;

and if n = −1,

ϕ−1 = ϕ − 1 = F −1ϕ + F−2.

Then, assuming

ϕn = F nϕ + Fn−1

we must show that

ϕn−1 = F n−1ϕ + Fn−2.

But

ϕn−1 = ϕ−1ϕn = ϕ−1 F nϕ + Fn−1 = Fn + Fn−1ϕ−1 = Fn−1ϕ−1 + F n = Fn−1 ϕ − 1 + Fn = Fn−1ϕ + Fn − Fn−1 = Fn−1ϕ + Fn−2.

Therefore,

ϕn = F nϕ + Fn−1

for all integers n as we needed to show. □

Proposition. ϕ̂n = Fnϕ̂ + Fn−1.

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

ϕ̂n = F nϕ̂ + Fn−1.

We divide the proof into two cases: n nonnegative, or n nonpositive.

In the case that n is nonnegative, if n = 0,

ϕ̂0 = 1 = 0 + 1 = F 0ϕ̂ + F−1;

and if n = 1,

ϕ̂1 = ϕ̂ + 0 = F 1ϕ̂ + F0.

Then, assuming

ϕ̂n = F nϕ̂ + Fn−1

we must show that

ϕ̂n+1 = F n+1ϕ̂ + Fn.

But

ϕ̂n+1 = ϕ̂ϕ̂n = ϕ̂ Fnϕ̂ + Fn−1 = Fnϕ̂2 + F n−1ϕ̂ = Fn ϕ̂ + 1 + Fn−1ϕ̂ = Fnϕ̂ + Fn−1ϕ̂ + Fn = Fn + Fn−1 ϕ̂ + Fn = Fn+1ϕ̂ + Fn.

In the case that n is nonpositive, if n = 0,

ϕ̂0 = 1 = 0 + 1 = F 0ϕ̂ + F−1;

and if n = −1,

ϕ̂−1 = ϕ̂ − 1 = F −1ϕ̂ + F−2.

Then, assuming

ϕ̂n = F nϕ̂ + Fn−1

we must show that

ϕ̂n−1 = F n−1ϕ̂ + Fn−2.

But

ϕ̂n−1 = ϕ̂−1ϕ̂n = ϕ̂−1 F nϕ̂ + Fn−1 = Fn + Fn−1ϕ̂−1 = Fn−1ϕ̂−1 + F n = Fn−1 ϕ̂ − 1 + Fn = Fn−1ϕ̂ + Fn − Fn−1 = Fn−1ϕ̂ + Fn−2.

Therefore,

ϕ̂n = F nϕ̂ + Fn−1

for all integers n as we needed to show. □

▸ 12. [M26] The “second order” Fibonacci sequence is defined by the rule

ℱ0 = 0,ℱ1 = 1,ℱn+2 = ℱn+1 + ℱn + Fn.

Express ℱn in terms of Fn and Fn+1. [Hint: Use generating functions.]

Let

𝒢(z) = ∑ ℱnzn = ℱ 0 + ℱ1z + ℱ2z2 + ⋯,
G(z) = ∑ Fnzn = F 0 + F1z + F2z2 + ⋯,

and note that

Fn = ℱn+2 −ℱn+1 −ℱn.

Then

z𝒢(z) = ∑ ℱnzn+1 = ℱ 0z + ℱ1z2 + ℱ 2z3 + ⋯,
z2𝒢(z) = ∑ ℱnzn+2 = ℱ 0z2 + ℱ 1z3 + ℱ 2z4 + ⋯,

and

(1 − z − z2)𝒢(z) = ℱ 0 + (ℱ1 −ℱ0)z + ∑ n≥2(ℱn −ℱn−1 −ℱn−2)zn = ℱ0 + (ℱ1 −ℱ0)z + (ℱ2 −ℱ1 −ℱ0)z2 + ⋯ = 0 + z + F0z2 + ⋯ = z + ∑ Fnzn+2 = z + z2 ∑ Fnzn = z + z2G(z).

From Eq. (11)

z G(z)𝒢(z) = z + z2G(z)

if and only if by definition and from Eq. (17)

𝒢(z) = G(z) + zG2(z) = ∑ Fnzn + z∑ 1 2 n − 1Fn + 2 5nFn−1 zn = ∑ Fn+1zn+1 + ∑ 1 2 n − 1Fn + 2 5nFn−1 zn+1 = ∑ Fn+1 + 1 2 n − 1Fn + 2 5nFn−1 zn+1 = ∑ Fn + 1 2 n − 2Fn−1 + 2 5(n − 1)Fn−2 zn.

But

Fn + 1 2 n − 2Fn−1 + 2 5(n − 1)Fn−2 = Fn−1 + Fn−2 + n − 2 5 Fn−1 + 2n − 2 5 Fn−2 = n + 3 5 Fn−1 + 2n + 3 5 Fn−2 = 2n + 3 5 Fn−1 + 2n + 3 5 Fn−2 −n 5 Fn−1 = 2n + 3 5 Fn −n 5 Fn−1 = 3n + 3 5 Fn −n 5 Fn −n 5 Fn−1 = 3n + 3 5 Fn −n 5 Fn+1.

That is

ℱn = 3n + 3 5 Fn −n 5 Fn+1.

▸ 13. [M22] Express the following sequences in terms of the Fibonacci numbers, when r, s, and c are given constants.

a)
a0 = r, a1 = s; an+2 = an+1 + an for n ≥ 0.
b)
b0 = 0, b1 = 1; bn+2 = bn+1 + bn + c, for n ≥ 0.

We may express the sequences in terms of the Fibonacci numbers.

a)
Allowing for negative n so that F−1 = 1, we can express an in terms of the Fibonacci numbers as
a0 = r = sF0 + rF−1 a1 = s = sF1 + rF0 a2 = a1 + a0 = sF1 + rF0 + sF0 + rF−1 = sF2 + rF1 ⋯

and in general for n ≥ 0 as

an = sFn + rFn−1.

We may prove this by induction. In the case that n = 0, a0 = sF0 + rF−1; and in the case that n = 1, a1 = sF1 + rF0. Then, assuming an = sFn + rFn−1, we must show that an+1 = sFn+1 + rFn. But

an+1 = an + an−1 = sFn + rFn−1 + sFn−1 + rFn−2 = s Fn + Fn−1 + r Fn−1 + Fn−2 = sFn+1 + rFn

and hence the result.

b)
We can express bn in terms of the Fibonacci numbers by first analyzing the derivative sequence bn′ = bn + c as
b0′ = b 0 + c = 0 + c = c b1′ = b 1 + c = 1 + c ⋯ bn+2′ = b n+2 + c = bn+1 + bn + c + c = bn+1′ + b n′.

From (a) we have that

bn′ = (1 + c)F n + cFn−1

if and only if

bn = (1 + c)Fn + cFn−1 − c

for n ≥ 0.

14. [M28] Let m be a fixed positive integer. Find an, given that

a0 = 0,a1 = 1;an+2 = an+1 + an + n m,for n ≥ 0.

First, we note that for nonnegative integers n ≥ 0

Fn = ∑ 0≤k≤n−1 k n − k − 1, (14.1)

which may be shown using induction, since

F0 = 0 = ∑ 0≤k≤−1 k −k − 1

and

F1 = 1 = ∑ 0≤k≤0 k −k;

and assuming

Fn = ∑ 0≤k≤n−1 k n − k − 1

implies

Fn+1 = Fn + Fn−1 = ∑ 0≤k≤n−1 k n − k − 1 + ∑ 0≤k≤n−2 k n − k − 2 = n − 1 0 + ∑ 0≤k≤n−2 k n − k − 1 + ∑ 0≤k≤n−2 k n − k − 2 = 1 + ∑ 0≤k≤n−2 k n − k − 1 + ∑ 0≤k≤n−2 k n − k − 2 = 1 + ∑ 0≤k≤n−2 k + 1 n − k − 1 = 1 + ∑ 1≤k≤n−1 k n − k = 1 + ∑ 0≤k≤n−1 k n − k − 0 n = 1 + ∑ 0≤k≤n−1 k n − k = 1 + ∑ 0≤k≤n k n − k − n 0 = 1 + ∑ 0≤k≤n k n − k − 1 = ∑ 0≤k≤n k n − k = ∑ 0≤k≤n−1+1 k n + 1 − k − 1.

Second, we note that for nonnegative integers m,n ≥ 0

∑ 0≤k≤m n + k m − k − n + k + 1 m − k − 1 = n m, (14.2)

which may be shown using induction, since

n 0 − n + 1 −1 = 1 − 0 = 1 = n 0

and

n 0 − n + 1 −1 + n 1 − n + 1 0 = 1 + n − 1 = n = n 1 ;

and assuming

∑ 0≤k≤m n + k m − k − n + k + 1 m − k − 1 = n m,

including the induction basis n−1 n−m−2 = n−1 n−1−(m+1) = n−1 m+1, implies

∑ 0≤k≤m+1 n + k m + 1 − k − n + k + 1 m + 1 − k − 1 = ∑ 0≤k≤m+1 n + k m − k + 1 − n + k + 1 m − k = n + (m + 1) m − (m + 1) + 1 − n + (m + 1) + 1 m − (m + 1) + ∑ 0≤k≤m n + k m − k + 1 − n + k + 1 m − k = n + m + 1 0 − n + m + 2 −1 + ∑ 0≤k≤m n + k m − k + 1 − n + k + 1 m − k = 1 − 0 + ∑ 0≤k≤m n + k m − k + 1 − n + k + 1 m − k = n + m 0 − n + m + 1 −1 + ∑ 0≤k≤m n + k m − k + 1 − n + k + 1 m − k = n − 1 + (m + 1) m + 1 − (m + 1) − n + (m + 1) m − (m + 1) + ∑ 0≤k≤m n − 1 + k m + 1 − k − n + k m − k + n − 1 + k m − k − n + k m − k − 1 = ∑ 0≤k≤m+1 n − 1 + k m + 1 − k − n + k m − k + ∑ 0≤k≤m n − 1 + k m − k − n + k m − k − 1 = ∑ 0≤k≤m+1 n − 1 + k m + 1 − k − n − 1 + k + 1 m + 1 − k − 1 + ∑ 0≤k≤m n − 1 + k m − k − n − 1 + k + 1 m − k − 1 = n − 1 m + 1 + n − 1 m . = n m + 1.

Finally, we claim that

an = Fm+n+1 + Fn −∑ 0≤k≤m n + k m − k.

In the case that n = 0,

a0 = 0 = Fm+1 −∑ 0≤k≤m+1−1 k m + 1 − k − 1 from (14.1) = Fm+1 −∑ 0≤k≤m k m − k = Fm+1 + 0 −∑ 0≤k≤m 0 + k m − k = Fm+1 + F0 −∑ 0≤k≤m 0 + k m − k;

and in the case that n = 1,

a1 = 1 = F1 = F1 + 0 = F1 + Fm+2 −∑ 0≤1+k≤m+2−1 1 + k m + 2 − (1 + k) − 1 from (14.1) = Fm+2 + F1 −∑ −1≤k≤m 1 + k m − k = Fm+2 + F1 −∑ 0≤k≤m 1 + k m − k − 0 m + 1 = Fm+2 + F1 −∑ 0≤k≤m 1 + k m − k − 0 = Fm+2 + F1 −∑ 0≤k≤m 1 + k m − k.

Then, assuming

an = Fm+n+1 + Fn −∑ 0≤k≤m n + k m − k,

we must show that

an+1 = Fm+n+2 + Fn+1 −∑ 0≤k≤mn + k + 1 m − k .

But

an+1 = an + an−1 + n − 1 m = Fm+n+1 + Fn −∑ 0≤k≤m n + k m − k + Fm+n + Fn−1 −∑ 0≤k≤mn + k − 1 m − k + n − 1 m = Fm+n+2 + Fn+1 −∑ 0≤k≤m n + k m − k −∑ 0≤k≤mn + k − 1 m − k + n − 1 m = Fm+n+2 + Fn+1 −∑ 0≤k≤m n + k m − k + n + k − 1 m − k + ∑ 0≤k≤m n − 1 + k m − k − n − 1 + k + 1 m − k − 1 from (14.2) = Fm+n+2 + Fn+1 + ∑ 0≤k≤m n + k − 1 m − k − n + k m − k − n + k − 1 m − k − n + k m − k − 1 = Fm+n+2 + Fn+1 −∑ 0≤k≤m n + k m − k + n + k m − k − 1 = Fm+n+2 + Fn+1 −∑ 0≤k≤mn + k + 1 m − k

and hence the result.

15. [M22] Let f(n) and g(n) be arbitrary functions, and for n ≥ 0 let

a0 = 0, a1 = 1, an+2 = an+1 + an + f(n); b0 = 0, b1 = 1, bn+2 = bn+1 + bn + g(n); c0 = 0, c1 = 1, cn+2 = cn+1 + cn + xf(n) + yg(n).

Express cn in terms of x, y, an, bn, and Fn.

We first prove two corollaries.

Proposition. an = Fn + ∑ ⁡ 1≤k≤n−1Fkf(n − k − 1).

Proof. Let f(n) be an arbitrary function and an defined as

an+2 = an+1 + an + f(n)

for n ≥ 0 with a1 = 1 and a0 = 0. We will show that

an = Fn + ∑ 1≤k≤n−1Fkf(n − k − 1). (15.1)

In the case that n = 0,

a0 = 0 = F0 + ∑ 1≤k≤−1Fkf(n − k − 1);

and in the case that n = 1,

a1 = 1 = F1 + ∑ 1≤k≤0Fkf(n − k − 1).

Then, assuming

an = Fn + ∑ 1≤k≤n−1Fkf(n − k − 1)

we must show that

an+1 = Fn+1 + ∑ 1≤k≤nFkf(n − k).

But

an+1 = an + an−1 + f(n − 1) = Fn + ∑ 1≤k≤n−1Fkf(n − k − 1) + Fn−1 + ∑ 1≤k≤n−2Fkf(n − k − 2) + f(n − 1) = Fn + Fn−1 + f(n − 1) + ∑ 1≤k≤n−1Fkf(n − k − 1) + ∑ 1≤k≤n−2Fkf(n − k − 2) = Fn+1 + f(n − 1) + ∑ 1≤k≤n−1Fkf(n − k − 1) + ∑ 1≤k≤n−2Fkf(n − k − 2) = Fn+1 + f(n − 1) + ∑ 2≤k≤nFk−1f(n − k) + ∑ 3≤k≤nFk−2f(n − k) = Fn+1 + f(n − 1) + ∑ 2≤k≤nFk−1f(n − k) + ∑ 2≤k≤nFk−2f(n − k) = Fn+1 + f(n − 1) + ∑ 2≤k≤n Fk−1 + Fk−2 f(n − k) = Fn+1 + f(n − 1) + ∑ 2≤k≤nFkf(n − k) = Fn+1 + ∑ 1≤k≤nFkf(n − k)

and hence the result. □

Proposition. cn = Fn + x∑ ⁡ 1≤k≤n−1Fkf(n − k − 1) + y∑ ⁡ 1≤k≤n−1Fkg(n − k − 1).

Proof. Let f(n) and g(n) be arbitrary functions; and an, bn, cn defined as

a0 = 0, a1 = 1, an+2 = an+1 + an + f(n); b0 = 0, b1 = 1, bn+2 = bn+1 + bn + g(n); c0 = 0, c1 = 1, cn+2 = cn+1 + cn + xf(n) + yg(n).

We will show that

cn = Fn + x∑ 1≤k≤n−1Fkf(n − k − 1) + y∑ 1≤k≤n−1Fkg(n − k − 1). (15.2)

In the case that n = 0,

c0 = 0 = F0 + x∑ 1≤k≤−1Fkf(n − k − 1) + y∑ 1≤k≤−1Fkg(n − k − 1);

and in the case that n = 1,

c1 = 1 = F1 + x∑ 1≤k≤0Fkf(n − k − 1) + y∑ 1≤k≤0Fkf(n − k − 1).

Then, assuming

cn = Fn + x∑ 1≤k≤n−1Fkf(n − k − 1) + y∑ 1≤k≤n−1Fkg(n − k − 1)

we must show that

cn+1 = Fn+1 + x∑ 1≤k≤nFkf(n − k) + y∑ 1≤k≤nFkg(n − k).

But

cn+1 = cn + cn−1 + xf(n − 1) + yg(n − 1) = Fn + x∑ 1≤k≤n−1Fkf(n − k − 1) + y∑ 1≤k≤n−1Fkg(n − k − 1) + Fn−1 + x∑ 1≤k≤n−2Fkf(n − k − 2) + y∑ 1≤k≤n−2Fkg(n − k − 2) + xf(n − 1) + yg(n − 1) = Fn+1 + xf(n − 1) + yg(n − 1) + x∑ 1≤k≤n−1Fkf(n − k − 1) + y∑ 1≤k≤n−1Fkg(n − k − 1) + x∑ 1≤k≤n−2Fkf(n − k − 2) + y∑ 1≤k≤n−2Fkg(n − k − 2) = Fn+1 + xf(n − 1) + yg(n − 1) + x∑ 2≤k≤nFk−1f(n − k) + y∑ 2≤k≤nFk−1g(n − k) + x∑ 3≤k≤nFk−2f(n − k) + y∑ 3≤k≤nFk−2g(n − k) = Fn+1 + xf(n − 1) + yg(n − 1) + x∑ 2≤k≤nFk−1f(n − k) + y∑ 2≤k≤nFk−1g(n − k) + x∑ 2≤k≤nFk−2f(n − k) + y∑ 2≤k≤nFk−2g(n − k) = Fn+1 + xf(n − 1) + yg(n − 1) + x∑ 2≤k≤n Fk−1 + Fk−2 f(n − k) + y∑ 2≤k≤n Fk−1 + Fk−2 g(n − k) = Fn+1 + xf(n − 1) + yg(n − 1) + x∑ 2≤k≤nFkf(n − k) + y∑ 2≤k≤nFkg(n − k) = Fn+1 + x∑ 1≤k≤nFkf(n − k) + y∑ 1≤k≤nFkg(n − k)

and hence the result. □

We then solve for cn as

cn = Fn + x∑ 1≤k≤n−1Fkf(n − k − 1) + y∑ 1≤k≤n−1Fkg(n − k − 1) from (15.2) = Fn + x an − Fn + y bn − Fn from (15.1) = xan + ybn + Fn − xFn − yFn = xan + ybn + (1 − x − y)Fn.

▸ 16. [M20] Fibonacci numbers appear implicitly in Pascal’s triangle if it is viewed from the right angle. Show that the following sum of binomial coefficients is a Fibonacci number:

∑ k=0nn − k k .

We may prove that the sum is a Fibonacci number.

Proposition. ∑ ⁡ 0≤k≤nn−k k = Fn+1.

Proof. Let n be an arbitrary nonnegative integer such that n ≥ 0. We must show that

∑ 0≤k≤nn − k k = Fn+1.

In the case that n = 0,

∑ 0≤k≤0−k k = 0 0 = 1 = F1;

and in the case that n = 1,

∑ 0≤k≤11 − k k = 1 0 + 0 1 = 1 + 0 = F2.

Then, assuming

∑ 0≤k≤nn − k k = Fn+1,

we must show that

∑ 0≤k≤n+1n + 1 − k k = Fn+2.

But

∑ 0≤k≤n+1n + 1 − k k = 0 n + 1 + ∑ 0≤k≤nn + 1 − k k = ∑ 0≤k≤nn + 1 − k k = ∑ 0≤k≤n n − k k + n − k k − 1 = ∑ 0≤k≤nn − k k + ∑ 0≤k≤n(n − 1) − (k − 1) k − 1 = Fn+1 + ∑ 0≤k≤n(n − 1) − (k − 1) k − 1 = Fn+1 + ∑ −1≤k≤n−1n − 1 − k k = Fn+1 + n −1 + ∑ 0≤k≤n−1n − 1 − k k = Fn+1 + ∑ 0≤k≤n−1n − 1 − k k = Fn+1 + Fn = Fn+2

as we needed to show. □

17. [M24] Using the conventions of exercise 8, prove the following generalization of Eq. (4): Fn+kFm−k − FnFm = (−1)nFm−n−kFk.

We may prove the generalization, but first, a corollary.

Proposition. (xn+k − yn+k)(xm−k − ym−k) − (xn − yn)(xm − ym) = (xy)n(xm−n−k − ym−n−k)(xk − yk).

Proof. Let x,y be arbitrary reals and m,n,k arbitrary integers. We must show that

(xn+k − yn+k)(xm−k − ym−k) − (xn − yn)(xm − ym) = (xy)n(xm−n−k − ym−n−k)(xk − yk).

But

(xn+k − yn+k)(xm−k − ym−k) − (xn − yn)(xm − ym) = (xy)n((xky−n − x−nyk)(xm−n−ky−n − x−nym−n−k) − (y−n − x−n)(xm−ny−n − x−nym−n)) = −xm−kyn+k − xn+kym−k + xmyn + xnym = (xy)n(−xm−n−kyk − xkym−n−k + xm−n + ym−n) = (xy)n(xm−n−k − ym−n−k)(xk − yk)

and hence the result. □

Finally, the proof.

Proposition. Fn+kFm−k − FnFm = (−1)nFm−n−kFk.

Proof. Let m, n, k be arbitrary integers, and allow for negative indexed Fibonacci numbers so that F−n = (−1)n+1Fn. We must show that

Fn+kFm−k − FnFm = (−1)nF m−n−kFk.

But since ϕn = (1 −ϕ̂)n = −ϕ̂−n,

Fn+kFm−k − FnFm = 1 5 ϕn+k −ϕ̂n+k 1 5 ϕm−k −ϕ̂m−k − 1 5 ϕn −ϕ̂n 1 5 ϕm −ϕ̂m = 1 52 ϕn+k −ϕ̂n+k ϕm−k −ϕ̂m−k −ϕn −ϕ̂n ϕm −ϕ̂m = 1 52 ϕϕ̂n ϕm−n−k −ϕ̂m−n−k ϕk −ϕ̂k from (17.1) = ϕϕ̂n 1 5 ϕm−n−k −ϕ̂m−n−k 1 5 ϕk −ϕ̂k = ϕϕ̂nF m−n−kFk = 1 2(1 + 5)1 2(1 −5)nF m−n−kFk = 1 4(1 + 5 −5 −52)nF m−n−kFk = − 4 4 nF m−n−kFk = (−1)nF m−n−kFk

as we needed to show. □

18. [20] Is Fn2 + Fn+12 always a Fibonacci number?

Yes, F2n+1, as shown below.

Proposition. Fn2 + Fn+12 = F2n+1.

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

Fn2 + F n+12 = F 2n+1.

In the case that n = 0,

F02 + F 12 = 0 + 1 = 1 = F 1;

and in the case that n = 1,

F12 + F 22 = 1 + 1 = 2 = F 3.

Then, assuming

Fn2 + F n+12 = F 2n+1.

we must show that

Fn+12 + F n+22 = F 2n+3.

But

Fn+12 + F n+22 = F n + Fn−1 2 + F n+1 + Fn 2 = Fn2 + 2F nFn−1 + Fn−12 + F n+12 + 2F n+1Fn + Fn2 = Fn−12 + F n2 + F n2 + F n+12 + 2F nFn−1 + 2Fn+1Fn = F2n−1 + F2n+1 + 2FnFn−1 + 2Fn+1Fn = F2n−1 + F2n+1 + 2FnFn−1 + 2(Fn+n − Fn−1Fn) from Eq. (6) = F2n−1 + F2n+1 + 2FnFn−1 + 2F2n − 2Fn−1Fn = F2n−1 + F2n+1 + 2F2n = F2n+1 + F2n + F2n+1 = F2n+2 + F2n+1 = F2n+3

as we needed to show. □

▸ 19. [M27] What is cos ⁡ 36∘?

We have that

cos ⁡ 36∘ = 1 + 5 4 ,

derived as follows. From the double angle formulas we have that

cos ⁡ 72∘ = cos ⁡ (2 ⋅ 36∘) = 2cos ⁡ 236∘− 1

and

cos ⁡ 36∘ = cos ⁡ (2 ⋅ 18∘) = 1 − 2sin ⁡ 218∘ = 1 − 2sin ⁡ 2(90∘− 72∘) = 1 − 2cos ⁡ 272∘.

That is, that

cos ⁡ 72∘ + cos ⁡ 36∘ = 2cos ⁡ 236∘− 1 + 1 − 2cos ⁡ 272∘ = 2 cos ⁡ 236∘− cos ⁡ 272∘

if and only if

1 = 2 cos ⁡ 236∘− cos ⁡ 272∘ cos ⁡ 72∘ + cos ⁡ 36∘ = 2 cos ⁡ 36∘− cos ⁡ 72∘cos ⁡ 272∘ + cos ⁡ 36∘ cos ⁡ 72∘ + cos ⁡ 36∘ = 2 cos ⁡ 36∘− cos ⁡ 72∘ = 2cos ⁡ 36∘− 2cos ⁡ 72∘ = 2cos ⁡ 36∘− 2 2cos ⁡ 236∘− 1 = 2cos ⁡ 36∘− 4cos ⁡ 236∘ + 2;

or equivalently that

2cos ⁡ 36∘ + 1 = 2cos ⁡ 36∘2.

And so, in terms of the golden ratio, since 2cos ⁡ 36∘ = ϕ,

cos ⁡ 36∘ = 1 2ϕ = 1 2 1 + 5 2 = 1 + 5 4

and hence the result.

20. [M16] Express ∑ ⁡ k=0nFk in terms of Fibonacci numbers.

We have that

∑ k=0nF k = Fn+2 − 1,

as shown here. In the case that n = 0,

∑ k=00F k = F0 = 0 = 1 − 1 = F2 − 1;

Then, assuming

∑ k=0nF k = Fn+2 − 1

we must show that

∑ k=0n+1F k = Fn+3 − 1.

But

∑ k=0n+1F k = ∑ k=0nF k + Fn+1 = Fn+2 − 1 + Fn+1 = Fn+3 − 1

and hence the result.

21. [M25] What is ∑ ⁡ k=0nFkxk?

We have that

∑ k=0nF kxk = xn+1F n+1+xn+2F n−x x2+x−1 if x2 + x≠1 n+1−xnF n+1 2x+1 otherwise

as shown here. First we consider the case that x2 + x≠1. For n = 0,

∑ k=00F kxk = F 0x0 = 0 = 0 x2 + x − 1 = x + 0 − x x2 + x − 1 = x1F1 + x2F0 − x x2 + x − 1 .

Then, assuming

∑ k=0nF kxk = xn+1F n+1 + xn+2F n − x x2 + x − 1 ,

we must show that

∑ k=0n+1F kxk = xn+2F n+2 + xn+3F n+1 − x x2 + x − 1 .

But

∑ k=0n+1F kxk = Fn+1xn+1 + ∑ k=0nF kxk = Fn+1xn+1 + xn+1F n+1 + xn+2F n − x x2 + x − 1 = (x2 + x − 1)Fn+1xn+1 x2 + x − 1 + xn+1Fn+1 + xn+2Fn − x x2 + x − 1 = xn+3Fn+1 + xn+2Fn+1 − xn+1Fn+1 x2 + x − 1 + xn+1Fn+1 + xn+2Fn − x x2 + x − 1 = xn+3Fn+1 + xn+2Fn+1 − xn+1Fn+1 + xn+1Fn+1 + xn+2Fn − x x2 + x − 1 = xn+2Fn+1 + xn+2Fn + xn+3Fn+1 − x x2 + x − 1 = xn+2 Fn+1 + Fn + xn+3Fn+1 − x x2 + x − 1 = xn+2Fn+2 + xn+3Fn+1 − x x2 + x − 1 .

Last we consider the case that x2 + x = 1. Note that in general since xn+2 = xn − xn+1,

1 = xnF n+1 + xn+1F n, (21.1)

since 1 = 1 + 0 = x0F1 + x1F0 and 1 = xnFn+1 + xn+1Fn⇒1 = xn+1Fn+2 + xn+2Fn+1 as

xn+1F n+2 + xn+2F n+1 = xn+1F n+2 + xn − xn+1 F n+1 = xn+1F n+2 + xnF n+1 − xn+1F n+1 = xn+1F n+2 − xn+1F n+1 + xnF n+1 = xn+1 F n+2 − Fn+1 + xnF n+1 = xn+1F n + xnF n+1 = xnF n+1 + xn+1F n = 1.

Again, considering the case that x2 + x = 1, for n = 0,

∑ k=00F kxk = F 0x0 = 0 = 1 − 1 2x + 1 = 1 − F1 2x + 1 = 0 + 1 − x0F1 2x + 1 .

Then, assuming

∑ k=0nF kxk = n + 1 − xnF n+1 2x + 1 ,

we must show that

∑ k=0n+1F kxk = n + 2 − xn+1F n+2 2x + 1 .

But in this case,

∑ k=0n+1F kxk = Fn+1xn+1 + ∑ k=0nF kxk = Fn+1xn+1 + n + 1 − xnF n+1 2x + 1 = (2x + 1)Fn+1xn+1 2x + 1 + n + 1 − xnFn+1 2x + 1 = 2xFn+1xn+1 + Fn+1xn+1 2x + 1 + n + 1 − xnFn+1 2x + 1 = 2Fn+1xn+2 + Fn+1xn+1 + n + 1 − xnFn+1 2x + 1 = n + 2 + 2Fn+1xn+2 + Fn+1xn+1 − 1 − xnFn+1 2x + 1 = n + 2 + 2Fn+1(xn − xn+1) + Fn+1xn+1 − 1 − xnFn+1 2x + 1 = n + 2 + 2Fn+1xn − 2Fn+1xn+1 + Fn+1xn+1 − 1 − xnFn+1 2x + 1 = n + 2 −xn+1Fn+1 − Fn+1xn + 1 2x + 1 = n + 2 −xn+1Fn+1 − Fn+1xn + xnFn+1 + xn+1Fn 2x + 1 from (21.1) = n + 2 −xn+1Fn+1 + xn+1Fn 2x + 1 = n + 2 − xn+1 Fn+1 + Fn 2x + 1 = n + 2 − xn+1Fn+2 2x + 1 .

Hence the result in either case.

▸ 22. [M20] Show that ∑ ⁡ kn k Fm+k is a Fibonacci number.

We have, by the binomial theorem, and since 1 + ϕ = ϕ2 and 1 + ϕ̂ = ϕ̂2,

∑ kn kFm+k = ∑ kn k 1 5 ϕm+k −ϕ̂m+k = 1 5 ϕm ∑ kn kϕk −ϕ̂m ∑ kn kϕ̂k = 1 5 ϕm 1 + ϕn −ϕ̂m 1 + ϕ̂n = 1 5 ϕm ϕ2 n −ϕ̂m ϕ̂2 n = 1 5 ϕmϕ2n −ϕ̂mϕ̂2n = 1 5 ϕm+2n −ϕ̂m+2n = Fm+2n.

23. [M23] Generalizing the preceding exercise, show that ∑ ⁡ kn k FtkF t−1n−kF m+k is always a Fibonacci number.

First, a corollary.

Proposition. Fnϕ + Fn−1 = ϕn and Fnϕ̂ + Fn−1 = ϕ̂n.

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

Fnϕ + Fn−1 = ϕn (23.1)

and

Fnϕ̂ + Fn−1 = ϕ̂n. (23.2)

In the case that n = 1,

F1ϕ + F1−1 = F1ϕ + F0 = ϕ + 0 = ϕ = ϕ1;

and in the case that n = 2,

F2ϕ + F2−1 = F2ϕ + F1 = ϕ + 1 = ϕ2.

Then, assuming

Fnϕ + Fn−1 = ϕn

we must show that

Fn+1ϕ + Fn = ϕn+1.

But

Fn+1ϕ + Fn = Fn + Fn−1 ϕ + Fn−1 + Fn−2 = Fnϕ + Fn−1 + Fn−1ϕ + Fn−2 = ϕn + ϕn−1 = ϕn+1

and hence the result for ϕ. The result for ϕ̂ follows similarly as F1ϕ̂ + F1−1 = F1ϕ̂ + F0 = ϕ̂ + 0 = ϕ̂ = ϕ̂1, F2ϕ̂ + F2−1 = F2ϕ̂ + F1 = ϕ̂ + 1 = ϕ̂2, and Fnϕ̂ + Fn−1 = ϕ̂n⇒Fn+1ϕ̂ + Fn = ϕ̂n+1 since

Fn+1ϕ̂ + Fn = Fn + Fn−1 ϕ̂ + Fn−1 + Fn−2 = Fnϕ̂ + Fn−1 + Fn−1ϕ̂ + Fn−2 = ϕ̂n + ϕ̂n−1 = ϕ̂n+1,

as we needed to show. □

Then we have, by the binomial theorem, and by both (23.1) and (23.2),

∑ kn kFtkF t−1n−kF m+k = ∑ kn kFtkF t−1n−k 1 5 ϕm+k −ϕ̂m+k = 1 5∑ kn kFtkF t−1n−k ϕmϕk −ϕ̂mϕ̂k = 1 5 ϕm ∑ kn kϕkF tkF t−1n−k −ϕ̂m ∑ kn kϕ̂kF tkF t−1n−k = 1 5 ϕm ∑ kn k ϕFt kF t−1n−k −ϕ̂m ∑ kn k ϕ̂Ft kF t−1n−k = 1 5 ϕm F tϕ + Ft−1 n −ϕ̂m F tϕ̂ + Ft−1 n = 1 5 ϕm ϕt n −ϕ̂m ϕ̂t n = 1 5 ϕmϕtn −ϕ̂mϕ̂tn = 1 5 ϕm+tn −ϕ̂m+tn = Fm+tn.

24. [HM20] Evaluate the n × n determinant

1−1 0 0 … ⁡00 0 1 1 −1 0 … ⁡ 0 0 0 0 1 1 −1… ⁡00 0 ⋮ ⁡ ⋮ ⁡ ⋮ ⁡ ⋮ ⁡ ⋱ ⋮ ⁡ ⋮ ⁡ ⋮ ⁡ 0 0 0 0 … ⁡11−1 0 0 0 0 … ⁡ 0 1 1 .

Given

aij = 1 if i = j 1 if i = j + 1 −1if j = i + 1 0 otherwise

we want to find det ⁡ [aij]n. In the case that n = 1,

det ⁡ [aij]1 = 1 = 1 = F2 = F1+1;

and in the case that n = 2,

det ⁡ [aij]2 = 1−1 1 1 = 1⋅1−(−1)⋅1 = 1+1 = 2 = F3 = F2+1.

Then, assuming

det ⁡ [aij]n = Fn+1

we need to show that

det ⁡ [aij]n+1 = Fn+2

But

det ⁡ [aij]n+1 = ∑ 1≤j≤n+1a1j ⋅ cofactor ⁡ (a1j) = a11 ⋅ cofactor ⁡ (a11) + a12 ⋅ cofactor ⁡ (a12) + ∑ 3≤j≤n+1a1j ⋅ cofactor ⁡ (a1j) = cofactor ⁡ (a11) − cofactor ⁡ (a12) + 0 = (−1)1+1 det ⁡ minor ⁡ ([a] n+1,1,1) − (−1)1+2 det ⁡ minor ⁡ ([a] n+1,1,2) = det ⁡ minor ⁡ ([a]n+1,1,1) + det ⁡ minor ⁡ ([a]n+1,1,2).

Note that minor ⁡ ([a]n+1,1,1) preserves symmetry about the diagonal so that

minor ⁡ ([a]n+1,1,1) = [a]n; (24.1)

and for

aij′ = aijif i≠2 ∨ j≠1 0 otherwise ,

that det ⁡ minor ⁡ ([a]n+1,1,2) can be expanded further as

det ⁡ minor ⁡ ([a]n+1,1,2) = det ⁡ [a′] n = ∑ 1≤i≤nai1′⋅ cofactor ⁡ (a i1′) = a11′⋅ cofactor ⁡ (a 11′) + ∑ 2≤i≤nai1′⋅ cofactor ⁡ (a i1′) = a11 ⋅ cofactor ⁡ (a11′) + 0 = cofactor ⁡ (a11′) = (−1)1+1 det ⁡ minor ⁡ ([a′] n,1,1) = det ⁡ [a]n−1;

that is, that

det ⁡ minor ⁡ ([a]n+1,1,2) = det ⁡ [a]n−1. (24.2)

And so,

det ⁡ [aij]n+1 = det ⁡ minor ⁡ ([a]n+1,1,1) + det ⁡ minor ⁡ ([a]n+1,1,2) = det ⁡ [a]n + det ⁡ minor ⁡ ([a]n+1,1,2) by (24.1) = det ⁡ [a]n + det ⁡ [a]n−1 by (24.2) = Fn+1 + Fn = Fn+2

and hence the result,

det ⁡ [aij]n = Fn+1.

25. [M21] Show that

2nF n = 2∑ k oddn k 5(k−1)∕2.

Proposition. 2nFn = 2∑ ⁡ k oddn k 5(k−1)∕2.

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

2nF n = 2∑ k oddn k 5(k−1)∕2.

But

Fn = 1 5 ϕn −ϕ̂n ⇔5Fn = 1 + 5 2 n −1 −5 2 n ⇔2n5F n = 1 + 5n −1 −5n ⇔2nF n = 1 5 1 + 5n −1 −5n .

Therefore

2nF n = 1 5 1 + 5n −1 −5n = 1 5 ∑ kn k 5k∕2 −∑ kn k (−1)k5k∕2 = ∑ kn k 5(k−1)∕2 −∑ kn k (−1)k5(k−1)∕2 = ∑ k evenn k 5(k−1)∕2 + ∑ k oddn k 5(k−1)∕2 −∑ k evenn k (−1)k5(k−1)∕2 −∑ k oddn k (−1)k5(k−1)∕2 = ∑ k evenn k 5(k−1)∕2 + ∑ k oddn k 5(k−1)∕2 −∑ k evenn k 5(k−1)∕2 + ∑ k oddn k 5(k−1)∕2 = ∑ k oddn k 5(k−1)∕2 + ∑ k oddn k 5(k−1)∕2 = 2∑ k oddn k 5(k−1)∕2

as we needed to show. □

▸ 26. [M20] Using the previous exercise, show that Fp ≡ 5(p−1)∕2(modulo p) if p is an odd prime.

Proposition. Fp ≡ 5(p−1)∕2(mod ⁡p) if p is an odd prime.

Proof. Let p be an arbitrary odd prime so that p > 2. We must show that

Fp ≡ 5(p−1)∕2(mod ⁡p).

By Fermat’s theorem, Theorem 1.2.4-F,

2p ≡ 2(mod ⁡p)⇔1 ≡ 2p−1(mod ⁡p).

Then, by exercise 25,

2pF p = 2∑ k oddp k5(k−1)∕2.

And so

2pF p ≡ 2p−12∑ k oddp k5(k−1)∕2(modp) ⇔2pF p ≡ 2p ∑ k oddp k5(k−1)∕2(modp) ⇔Fp ≡∑ k oddp k5(k−1)∕2(modp).

Then

Fp ≡∑ k oddp k5(k−1)∕2 ≡ p p5(p−1)∕2 + ∑ 1≤k≤p−1 k odd p k5(k−1)∕2 ≡ 5(p−1)∕2 + ∑ 1≤k≤p−1 k odd p k5(k−1)∕2 ≡ 5(p−1)∕2 + 0 by exercise 1.2.6-10(b) ≡ 5(p−1)∕2(mod ⁡p)

as we needed to show. □

27. [M20] Using the previous exercise, show that if p is a prime different from 5, then either Fp−1 or Fp+1 (not both) is a multiple of p.

Proposition. If p is a prime different from 5, then either p∣Fp−1 or p∣Fp+1 (exclusively).

Proof. Let p be an arbitrary prime different from 5. We must show that

p∣Fp−1orp∣Fp+1

(exclusively). In the case that p = 2,

2∣F2+1and2 ∤ F2−1

since k2 = F2+1 = F3 = 2 for k = 1 but 2 > 1 = F1 = F2−1. Hereafter, we consider the case that p is an odd prime different from 5. By Eq. (4),

Fp+1Fp−1 − Fp2 = (−1)p ⇔Fp+1Fp−1 − Fp2 = −1 ⇔Fp+1Fp−1 = Fp2 − 1 ⇒Fp+1Fp−1 ≡ Fp2 − 1(mod ⁡p).

From the previous exercise,

Fp ≡ 5(p−1)∕2(mod ⁡p) ⇔Fp2 ≡ 5p−1(mod ⁡p) ⇔Fp2 − 1 ≡ 5p−1 − 1(mod ⁡p);

and by Fermat’s theorem, Theorem 1.2.4-F,

5p ≡ 5(mod ⁡p) ⇔5p−1 ≡ 1(mod ⁡p) ⇔5p−1 − 1 ≡ 0(mod ⁡p).

And so,

Fp+1Fp−1 ≡ Fp2 − 1 ≡ 5p−1 − 1 ≡ 0(mod ⁡p).

That is, that

p∣Fp−1orp∣Fp+1.

To see that this is exclusive, consider the case that p∣Fp−1. Then Fp−1 = mp for some m. If we assume Fp+1 = np for some n,

Fp+1 = Fp + Fp−1 = Fp + mp = np,

then p∣Fp. But by Fermat’s theorem, again,

5p ≡ 5(mod ⁡p) ⇔5p−1 ≡ 1(mod ⁡p) ⇔5(p−1)∕2 ≡ 1(mod ⁡p),

and from the previous exercise

Fp ≡ 5(p−1)∕2 ≡ 1(mod ⁡p),

contradicting the assumption Fp+1 = np, so that p ∤ Fp+1 if p∣Fp−1. Similarly, consider the case that p∣Fp+1. Then Fp+1 = np for some n. If we assume Fp−1 = mp for some m,

Fp−1 = −Fp + Fp+1 = −Fp + mp = np,

then p∣Fp. But as with the previous case,

Fp ≡ 1(mod ⁡p)

contradicting the assumption Fp−1 = mp, so that p ∤ Fp−1 if p∣Fp+1. This is what we needed to show. □

28. [M21] What is Fn+1 − ϕFn?

We have

Fn+1 − ϕFn = 1 5 ϕn+1 −ϕ̂n+1 − ϕ 1 5 ϕn −ϕ̂n = 1 5 ϕn+1 −ϕ̂n+1 − ϕϕn + ϕϕ̂n = 1 5 ϕn+1 − ϕn+1 + ϕ̂nϕ −ϕ̂nϕ̂ = 1 5 0 + ϕ̂n ϕ −ϕ̂ = ϕ̂nϕ −ϕ̂ 5 = ϕ̂n 1 + 5 2 −1 −5 2 1 5 = ϕ̂n 1 2 + 5 2 −1 2 + 5 2 1 5 = ϕ̂n 5 2 + 5 2 1 5 = ϕ̂n25 2 1 5 = ϕ̂n5 5 = ϕ̂n.

▸ 29. [M23] (Fibonomial coefficients.) Édouard Lucas defined the quantities

n kℱ = FnFn−1… ⁡Fn−k+1 FkFk−1… ⁡F1 = ∏ j=1k Fn−k+j Fj

in a manner analogous to binomial coefficients. (a) Make a table of n k ℱ for 0 ≤ k ≤ n ≤ 6. (b) Show that n k ℱ is always an integer because we have

n kℱ = Fk−1n − 1 k ℱ + Fn−k+1n − 1 k − 1ℱ.
a)
The table of Fibonomial coefficients n k ℱ for 0 ≤ k ≤ n ≤ 6 would appear as below.
nn 0 ℱn 1 ℱn 2 ℱn 3 ℱn 4 ℱn 5 ℱn 6 ℱ
0 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0
2 1 1 1 0 0 0 0
3 1 2 2 1 0 0 0
4 1 3 6 3 1 0 0
5 1 5 15 15 5 1 0
6 1 8 40 60 40 8 1

This is based on the observations that

n 0 ℱ = ∏ 1≤j≤0Fn−0+j Fj = 1, n 1 ℱ = ∏ 1≤j≤1Fn−1+j Fj = Fn F1 = Fn, n 2 ℱ = ∏ 1≤j≤2Fn−2+j Fj = Fn−1 F1 Fn F2 = Fn−1Fn, n 3 ℱ = ∏ 1≤j≤3Fn−3+j Fj = Fn−2 F1 Fn−1 F2 Fn F3 = 1 2Fn−2Fn−1Fn, n 4 ℱ = ∏ 1≤j≤4Fn−4+j Fj = Fn−3 F1 Fn−2 F2 Fn−1 F3 Fn F4 = 1 6Fn−3Fn−2Fn−1Fn, n 5 ℱ = ∏ 1≤j≤5Fn−5+j Fj = Fn−4 F1 Fn−3 F2 Fn−2 F3 Fn−1 F4 Fn F5 = 1 30Fn−4Fn−3Fn−2Fn−1Fn, and n 6 ℱ = ∏ 1≤j≤6Fn−6+j Fj = Fn−5 F1 Fn−4 F2 Fn−3 F3 Fn−2 F4 Fn−1 F5 Fn F6 = 1 240Fn−5Fn−4Fn−3Fn−2Fn−1Fn.
b)
We may show that n k ℱ is always an integer by proving the recursive relation below.

Proposition. n k ℱ = Fk−1n−1 k ℱ + Fn−k+1n−1 k−1 ℱ.

Proof. We must show that

n kℱ = Fk−1n − 1 k ℱ + Fn−k+1n − 1 k − 1ℱ

for 1 ≤ k ≤ n. But

n kℱ = ∏ 1≤j≤kFn−k+j Fj = FkFn−k+1 + Fk−1Fn−k Fn−k+k ∏ 1≤j≤kFn−k+j Fj by Eq. (6) = Fn−kFk−1 + Fn−k+1Fk Fn ∏ 1≤j≤kFn−k+j Fj = Fn−kFk−1 Fn ∏ 1≤j≤kFn−k+j Fj + Fn−k+1Fk Fn ∏ 1≤j≤kFn−k+j Fj = Fn−kFk−1 Fn ∏ 1≤j≤kFn−k+j Fj + Fn−k+1 Fk Fn ∏ 1≤j≤kFn−k+j Fj = Fn−kFk−1 Fn ∏ 2≤j≤k+1Fn−k+j−1 Fj−1 + Fn−k+1 ∏ 1≤j≤k−1Fn−k+j Fj = Fn−kFk−1 Fn Fn ∏ 2≤j≤kFn−k+j−1 ∏ 1≤j≤kFj + Fn−k+1 ∏ 1≤j≤k−1Fn−k+j Fj = Fn−kFk−1 ∏ 2≤j≤kFn−k+j−1 ∏ 1≤j≤kFj + Fn−k+1 ∏ 1≤j≤k−1Fn−k+j Fj = Fk−1Fn−k+1−1 ∏ 2≤j≤kFn−k+j−1 ∏ 1≤j≤kFj + Fn−k+1 ∏ 1≤j≤k−1Fn−k+j Fj = Fk−1 ∏ 1≤j≤kFn−k+j−1 ∏ 1≤j≤kFj + Fn−k+1 ∏ 1≤j≤k−1Fn−k+j Fj = Fk−1 ∏ 1≤j≤kFn−k+j−1 Fj + Fn−k+1 ∏ 1≤j≤k−1Fn−k+j Fj = Fk−1 ∏ 1≤j≤kFn−1−k+j Fj + Fn−k+1 ∏ 1≤j≤k−1Fn−1−(k−1)+j Fj = Fk−1n − 1 k ℱ + Fn−k+1n − 1 k − 1ℱ

as we needed to show. □

______________________________________________________________________________________________________________________________

[É. Lucas, Amer. J. Math. 1 (1878), 201–204]

▸ 30. [M38] (D. Jarden, T. Motzkin.) The sequence of mth powers of Fibonacci numbers satisfies a recurrence relation in which each term depends on the preceding m + 1 terms. Show that

∑ km k ℱ(−1)⌈(m−k)∕2⌉F n+km−1 = 0,if m > 0.

For example, when m = 3 we get the identity Fn2 − 2Fn+12 − 2Fn+22 + Fn+32 = 0.

We may prove the equality as a particular case of the proof outlined by Cooper and Kennedy.1

Proposition. ∑ ⁡ km k ℱ(−1)⌈(m−k)∕2⌉F n+km−1 = 0 if m > 0.

Proof. Let m,n,k be arbitrary integers such that m > 0. We must show that

∑ km k ℱ(−1)⌈(m−k)∕2⌉F n+km−1 = 0,

or equivalently for n′ = n + m that

∑ km k ℱ(−1)⌈(m−k)∕2⌉F n+km−1 = 0 ⇔∑ 0≤k≤mm k ℱ(−1)⌈(m−k)∕2⌉F n+km−1 = 0 ⇔∑ 0≤k≤m m m − kℱ(−1)⌈(m−k)∕2⌉F n′−(m−k)m−1 = 0 ⇔∑ 0≤m−k≤m m m − kℱ(−1)⌈(m−k)∕2⌉F n′−(m−k)m−1 = 0 ⇔∑ 0≤k≤mm k ℱ(−1)⌈k∕2⌉F n′−km−1 = 0.

Preliminary result 30.1. From Eq. (14), we have that

Fn = 1 5 ϕn −ϕ̂n = ϕn −ϕ̂n ϕ −ϕ̂ . (30.1)

Preliminary result 30.2. As shown in exercise 14, we may show that

Fn+1 = ∑ 0≤k≤n k n − k. (30.2)

In the case that n = 0,

F1 = 1 = 1 = 0 0 = ∑ 0≤k≤0 k 0 − k;

and in the case that n = 1,

F2 = 1 = 0 + 1 = 0 1 + 1 1 = ∑ 0≤k≤1 k 1 − k;

Then assuming

Fn+1 = ∑ 0≤k≤n k n − k,

we must show

Fn+2 = ∑ 0≤k≤n+1 k n − k + 1.

But

Fn+2 = Fn+1 + Fn = ∑ 0≤k≤n k n − k + ∑ 0≤k≤n−1 k n − k − 1 = n 0 + ∑ 0≤k≤n−1 k n − k + ∑ 0≤k≤n−1 k n − k − 1 = 1 + ∑ 0≤k≤n−1 k n − k + k n − k − 1 = 1 + ∑ 0≤k≤n−1 k + 1 n − k = 1 + ∑ 1≤k≤n k n − k + 1 = n + 1 0 + ∑ 1≤k≤n k n − k + 1 = n + 1 n − (n + 1) + 1 + ∑ 1≤k≤n k n − k + 1 = ∑ 1≤k≤n+1 k n − k + 1 = 0 + ∑ 1≤k≤n+1 k n − k + 1 = 0 n − 0 + 1 + ∑ 1≤k≤n+1 k n − k + 1 = ∑ 0≤k≤n+1 k n − k + 1

and hence the result.

Preliminary result 30.3. We have that

Fn + Fn−2 = ϕn−1 + ϕ̂n−1 (30.3)

since by definition and (30.1)

Fn + Fn−2 = Fn + Fn − Fn−1 = 2Fn − Fn−1 = 2ϕn −ϕ̂n ϕ −ϕ̂ −ϕn−1 −ϕ̂n−1 ϕ −ϕ̂ = 2ϕn − 2ϕ̂n − ϕn−1 + ϕ̂n−1 ϕ −ϕ̂ = 2ϕn − ϕn−1 + ϕ̂n−1 − 2ϕ̂n ϕ −ϕ̂ = 2ϕϕn−1 − ϕn−1 + ϕ̂n−1 − 2ϕ̂ϕ̂n−1 ϕ −ϕ̂ = 2ϕ − 1ϕn−1 + 1 − 2ϕ̂ϕ̂n−1 ϕ −ϕ̂ = 2ϕ − 1ϕn−1 + 2ϕ − 1ϕ̂n−1 ϕ −ϕ̂ = 2ϕ − 1 ϕn−1 + ϕ̂n−1 ϕ −ϕ̂ = ϕ −ϕ̂ ϕn−1 + ϕ̂n−1 ϕ −ϕ̂ = ϕn−1 + ϕ̂n−1.

Preliminary result 30.4. We have that

FnFn−2 − Fn−12 = ϕn−1ϕ̂n−1 (30.4)

since by definition and (30.1)

FnFn−2 − Fn−12 = F n Fn − Fn−1 − Fn−12 = Fn2 − F nFn−1 − Fn−12 = Fn2 − F n−1 Fn + Fn−1 = Fn2 − F n−1Fn+1 = ϕn −ϕ̂n ϕ −ϕ̂ 2 −ϕn−1 −ϕ̂n−1 ϕ −ϕ̂ ϕn+1 −ϕ̂n+1 ϕ −ϕ̂ = ϕ2n − 2ϕnϕ̂n + ϕ̂2n − ϕ2n + ϕn+1ϕ̂n−1 + ϕn−1ϕ̂n+1 −ϕ̂2n ϕ −ϕ̂2 = ϕn+1ϕ̂n−1 − 2ϕnϕ̂n + ϕn−1ϕ̂n+1 ϕ −ϕ̂2 = ϕn−1ϕ̂n−1 ϕ2 − 2ϕϕ̂ + ϕ̂2 ϕ −ϕ̂2 = ϕn−1ϕ̂n−1 ϕ −ϕ̂2 ϕ −ϕ̂2 = ϕn−1ϕ̂n−1.

Preliminary result 30.5. We may show that

Fkx + Fk−1 r F k+1x + Fk n−r = ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk xn−sk (30.5)

for 0 ≤ r ≤ n. In the case that k = 1,

F1x + F1−1 r F 1+1x + F1 n−r = xr x + 1n−r = xr 1 + xn−r = xr ∑ 0≤s1≤n−rn − r s1 xs1 = ∑ 0≤n−r−s1≤n−r n − r n − r − s1xn−r−s1 xr = ∑ 0≤s1≤n−rn − r s1 xn−s1 = ∑ s1 n − r s1 xn−s1 .

Then, assuming

Fkx + Fk−1 r F k+1x + Fk n−r = ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk xn−sk ,

we must show that

Fk+1x + Fk r F k+2x + Fk+1 n−r = ∑ s1,⋯,sk+1 n − r s1 n − s1 s2 ⋯n − sk sk+1 xn−sk+1 .

But for x′ = 1 + x−1,

Fk+1x + Fk r F k+2x + Fk+1 n−r = xr F k+1 + Fkx−1 rxn−r F k+2 + Fk+1x−1 n−r = xn F k + Fk−1 + Fkx−1 r F k+1 + Fk + Fk+1x−1 n−r = xn F k + Fkx−1 + F k−1 r F k+1 + Fk+1x−1 + F k n−r = xn F k 1 + x−1 + F k−1 r F k+1 1 + x−1 + F k n−r = xn F kx′ + F k−1 r F k+1x′ + F k n−r = xn ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk x′n−sk = ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk 1 + x−1 n−sk xn = ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk x + 1n−sk xsk = ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk ∑ sk+1 n − sk sk+1 xn−sk−sk+1 xsk = ∑ s1,⋯,sk+1 n − r s1 n − s1 s2 ⋯n − sk sk+1 xn−sk+1

and hence the result.

Preliminary Result 30.6. From Eq. (1.2.6-19), we have that

n k = (−1)n−k−k − 1 n − k . (30.6)

Preliminary Result 30.7. Define

An+1 = [aij]n+1 = i n − jn+1 = 0 n 0 n−1⋯ 0 0 1 n 1 n−1⋯ 1 0 ⋮ ⁡ ⋮ ⁡ ⋯⋮ ⁡ n n n n−1⋯n 0 n+1.

Then

tr ⁡ An+1k = Fkn+k Fk (30.7)

for k > 0, where tr ⁡ Bn+1 is the trace of Bn+1 defined as

tr ⁡ Bn+1 = ∑ 0≤i≤nbij.

Note that the case k = 1 is (30.2). But by (30.5),

Fkx + Fk−1 r F k+1x + Fk n−r = ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk xn−sk ⇔ Fkx + Fk−1 r F k+1x + Fk n−rxr = ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk xn+r−sk ⇔∑ 0≤r≤n Fkx + Fk−1 r F k+1x + Fk n−rxr = ∑ 0≤r≤n ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk xn+r−sk ⇔∑ n≥0 ∑ 0≤r≤n Fkx + Fk−1 r F k+1x + Fk n−rxr = ∑ n≥0 ∑ 0≤r≤n ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk xr−sk xn

and since

tr ⁡ An+1k = ∑ 0≤i≤n ∑ s1,s2,⋯,sk i=s1=s2=⋯=sk i n − s1 s1 n − s2⋯ sk−1 n − sk = ∑ 0≤n−i≤n ∑ n−s1,n−s2,⋯,n−sk n−i=n−s1=n−s2=⋯=n−sk i n − s1 s1 n − s2⋯ sk−1 n − sk = ∑ 0≤r≤n ∑ s1,s2,⋯,sk i=s1=s2=⋯=sk n − r s1 n − s1 s2 ⋯n − sk−1 sk = ∑ 0≤r≤n ∑ s1,s2,⋯,sk i=s1=s2=⋯=sk n − r s1 n − s1 s2 ⋯n − sk−1 sk x0 = ∑ 0≤r≤n ∑ s1,s2,⋯,sk i=s1=s2=⋯=sk n − r s1 n − s1 s2 ⋯n − sk−1 sk xr−sk

we have that

∑ n≥0 ∑ 0≤r≤n ∑ s1,⋯,skn − r s1 n − s1 s2 ⋯n − sk−1 sk xr−sk xn = ∑ n≥0 tr ⁡ An+1k xn = ∑ n≥0 ∑ 0≤r≤n Fkx + Fk−1 r F k+1x + Fk n−rxr.

But

∑ 0≤r≤n Fkx + Fk−1 r F k+1x + Fk n−rxr = ∑ 0≤r≤n ∑ 0≤s≤rr s FkxsF k−1r−s ∑ 0≤t≤n−rn − r t Fk+1xtF kn−r−txr = ∑ 0≤r≤n ∑ 0≤s≤r ∑ 0≤t≤n−rr s n − r t Fk+1tF ksF kn−r−tF k−1r−sxsxtxr = ∑ 0≤r≤n ∑ 0≤s≤r ∑ 0≤t≤n−rr s n − r t Fk+1tF kn−r+s−tF k−1r−sxr+s+t = ∑ n=r+s+tr s n − r t Fk+1tF kn−r+s−tF k−1r−sxn = ∑ n=r+s+tr s n − r n − r − sFk+1n−r−sF k2sF k−1r−sxn = ∑ n≥r+sr s n − r s Fk+1n−r−sF k2sF k−1r−sxn = ∑ r,s≥0r sFk−1r−sF k2sxr+s ∑ n≥r+sn − r s Fk+1xn−r−s = ∑ r,s≥0r sFk−1r−sF k2sxr+s ∑ n≥r+sn − r s Fk+1n−r−sxn−r−s = ∑ r,s≥0r sFk−1r−sF k2sxr+s ∑ s≤n−r(−1)n−r−s −s − 1 n − r − s Fk+1xn−r−s by (30.6) = ∑ r,s≥0r sFk−1r−sF k2sxr+s ∑ 0≤n−r−s −s − 1 n − r − s −Fk+1xn−r−s = ∑ r,s≥0r sFk−1r−sF k2sxr+s 1 − F k+1x−s−1 = ∑ s≥0Fk2sx2s 1 − F k+1x−s−1 ∑ r≥0r sFk−1r−sxr−s = ∑ s≥0Fk2sx2s 1 − F k+1x−s−1 ∑ s≤rr sFk−1r−sxr−s = ∑ s≥0Fk2sx2s 1 − F k+1x−s−1 ∑ s≤rr s Fk−1xr−s = ∑ s≥0Fk2sx2s 1 − F k+1x−s−1 ∑ s≤r(−1)r−s−s − 1 r − s Fk−1xr−s by (30.6) = ∑ s≥0Fk2sx2s 1 − F k+1x−s−1 ∑ 0≤r−s−s − 1 r − s −Fk−1xr−s = ∑ s≥0Fk2sx2s 1 − F k+1x−s−1 1 − F k−1x−s−1 = 1 1 − Fk+1x 1 − Fk−1x∑ s≥0 Fk2x2 1 − Fk+1x 1 − Fk−1xs.

Then

1 1 − Fk+1x 1 − Fk−1x∑ s≥0 Fk2x2 1 − Fk+1x 1 − Fk−1xs = 1 1 − Fk+1x 1 − Fk−1x 1 1 − Fk2x2 1−Fk+1x1−Fk−1x = 1 1 − Fk+1x 1 − Fk−1x 1 − Fk+1x 1 − Fk−1x 1 − Fk+1x 1 − Fk−1x − Fk2x2 = 1 1 − Fk+1x 1 − Fk−1x − Fk2x2 = 1 1 − Fk+1x − Fk−1x + Fk+1Fk−1x2 − Fk2x2 = 1 1 −Fk+1 + Fk−1 x + Fk+1Fk−1 − Fk2 x2 = 1 1 −ϕk + ϕ̂k x + Fk+1Fk−1 − Fk2 x2 by (30.3) = 1 1 −ϕk + ϕ̂k x + ϕkϕ̂kx2 by (30.4) = 1 1 − ϕkx −ϕ̂kx + ϕkϕ̂kx2 = 1 ϕk −ϕ̂k ϕk 1 −ϕ̂kx −ϕ̂k 1 − ϕkx 1 − ϕkx 1 −ϕ̂kx = 1 ϕk −ϕ̂k ϕk 1 − ϕkx − ϕ̂k 1 −ϕ̂kx = 1 ϕk −ϕ̂k ϕk 1 1 − ϕkx −ϕ̂k 1 1 −ϕ̂kx = 1 ϕk −ϕ̂k ϕk ∑ n≥0 ϕkxn −ϕ̂k ∑ n≥0 ϕ̂kxn = 1 ϕk −ϕ̂k ϕk ∑ n≥0 ϕk nxn −ϕ̂k ∑ n≥0 ϕ̂k nxn = 1 ϕk −ϕ̂k ∑ n≥0ϕkn+kxn −∑ n≥0ϕ̂kn+kxn = 1 ϕk −ϕ̂k ∑ n≥0 ϕkn+k −ϕ̂kn+k xn = ∑ n≥0ϕkn+k −ϕ̂kn+k ϕk −ϕ̂k xn = ∑ n≥0ϕkn+k −ϕ̂kn+k ϕ −ϕ̂ ϕ −ϕ̂ ϕk −ϕ̂kxn = ∑ n≥0Fkn+k Fk xn.

And so,

∑ n≥0 tr ⁡ An+1k xn = ∑ n≥0Fkn+k Fk xn,

hence the result.

Preliminary Result 30.8. We may show that the eigenvalues of An+1 are

λj = ϕjϕ̂n−j (30.8)

for 0 ≤ j ≤ n. Let

pAn+1(x) = det ⁡ (xIn+1 −An+1)

be the characteristic polynomial of An+1, where In+1 is the (n + 1) × (n + 1) identity matrix. Using partial fraction decomposition we find that

pAn+1′(x) pAn+1(x) = ∑ 0≤j≤npAn+1′(λj) pAn+1′(λj) 1 x − λj = ∑ 0≤j≤n 1 x − λj = ∑ 0≤j≤n1 x x x − λj = ∑ 0≤j≤n 1∕x 1 − λj∕x = ∑ 0≤j≤n ∑ k≥0 1 x λj x k = ∑ 0≤j≤n ∑ k≥0 λjk xk+1 = ∑ 0≤j≤n ∑ k≥0λjkx−k−1 = ∑ k≥0x−k−1 ∑ 0≤j≤nλjk = ∑ k≥0x−k−1 tr ⁡ (A n+1k) = ∑ k≥0x−k−1Fkn+k Fk by (30.7) = ∑ k≥0x−k−1ϕkn+k −ϕ̂kn+k ϕ −ϕ̂ ϕ −ϕ̂ ϕk −ϕ̂k by (30.1) = ∑ k≥0x−k−1ϕkn+k −ϕ̂kn+k ϕk −ϕ̂k = ∑ k≥0x−k−1 ϕ̂k n1 −ϕk∕ϕ̂k n+1 1 − ϕk∕ϕ̂k = ∑ k≥0x−k−1 ∑ 0≤j≤n ϕ̂k n ϕk ϕ̂k j = ∑ k≥0x−k−1 ∑ 0≤j≤nϕjkϕ̂(n−j)k = ∑ 0≤j≤n ∑ k≥0 1 x ϕjϕ̂n−j x k = ∑ 0≤j≤n1 x 1 1 − ϕjϕ̂n−j∕x = ∑ 0≤j≤n 1 x − ϕjϕ̂n−j

so that

∑ 0≤j≤n 1 x − λj = ∑ 0≤j≤n 1 x − ϕjϕ̂n−j ⇔λj = ϕjϕ̂n−j

and

pAn+1(x) = ∏ 0≤j≤n x − λj = ∏ 0≤j≤n x − ϕjϕ̂n−j ,

hence the result.

Preliminary Result 30.9. We may show that

(−1)k(k+1)∕2 = (−1)⌈k∕2⌉. (30.9)

In the case that k = 2m even and m even,

(−1)k(k+1)∕2 = (−1)2m(2m+1)∕2 = (−1)m(2m+1) = 1 = (−1)m = (−1)⌈m⌉ = (−1)⌈2m∕2⌉ = (−1)⌈k∕2⌉;

that k = 2m even and m odd,

(−1)k(k+1)∕2 = (−1)2m(2m+1)∕2 = (−1)m(2m+1) = −1 = (−1)m = (−1)⌈m⌉ = (−1)⌈2m∕2⌉ = (−1)⌈k∕2⌉;

that k = 2m + 1 odd and m even,

(−1)k(k+1)∕2 = (−1)(2m+1)(2m+2)∕2 = (−1)(2m+1)(m+1) = −1 = (−1)m+1 = (−1)⌈m+1∕2⌉ = (−1)⌈(2m+1)∕2⌉ = (−1)⌈k∕2⌉;

and that k = 2m + 1 odd and m odd,

(−1)k(k+1)∕2 = (−1)(2m+1)(2m+2)∕2 = (−1)(2m+1)(m+1) = 1 = (−1)m+1 = (−1)⌈m+1∕2⌉ = (−1)⌈(2m+1)∕2⌉ = (−1)⌈k∕2⌉;

hence the result.

Preliminary Result 30.10. We may show that

∏ 0≤j≤n x − ϕjϕ̂n−j = ∑ 0≤k≤n+1(−1)⌈k∕2⌉n + 1 k ℱxn+1−k. (30.10)

By the q-nomial theorem2 ,

∏ 0≤k≤n−1 1 − qkx = ∑ 0≤k≤n(−1)kn kqqk(k−1)∕2xk,

where

n kq = ∏ 1≤j≤k1 − qn−k+j 1 − qj ,

for q = ϕ̂∕ϕ,

n kϕ̂∕ϕ = ∏ 1≤j≤k1 − (ϕ̂∕ϕ)n−k+j 1 − (ϕ̂∕ϕ)j = ∏ 1≤j≤k ϕn−k+j −ϕ̂n−k+j ϕj ϕj −ϕ̂j ϕn−k+j = ∏ 1≤j≤kϕj −ϕ̂n−k+jϕk−n ϕj −ϕ̂j = ∏ 1≤j≤kϕj −ϕ̂n−k+jϕ̂n−k ϕj −ϕ̂j = ∏ 1≤j≤kϕj −ϕ̂2n−2k+j ϕj −ϕ̂j = ∏ 1≤j≤kϕj −ϕ̂n−kϕ̂n−k+j ϕj −ϕ̂j = ∏ 1≤j≤kϕk−nϕn−k+j − ϕk−nϕ̂n−k+j ϕj −ϕ̂j = ∏ 1≤j≤kϕk−n ϕn−k+j −ϕ̂n−k+j ϕj −ϕ̂j = ϕk−n k ∏ 1≤j≤kϕn−k+j −ϕ̂n−k+j ϕj −ϕ̂j = ϕk2−nk ∏ 1≤j≤kϕn−k+j −ϕ̂n−k+j ϕj −ϕ̂j = ϕk2−nk ∏ 1≤j≤kϕn−k+j −ϕ̂n−k+j ϕ −ϕ̂ ϕ −ϕ̂ ϕj −ϕ̂j = ϕk2−nk ∏ 1≤j≤kFn−k+j Fj by (30.1) = ϕk2−nk n kℱ.

And so,

∏ 0≤k≤n−1 1 − (ϕ̂∕ϕ)kx = ∏ 0≤k≤n−1 1 − ϕ−kϕ̂kx = ∑ 0≤k≤n(−1)kn kϕ̂∕ϕ(ϕ̂∕ϕ)k(k−1)∕2xk = ∑ 0≤k≤n(−1)kϕk2−nk n kℱ(ϕ̂∕ϕ)k(k−1)∕2xk = ∑ 0≤k≤n(−1)kϕk(k+1)∕2−nkϕ̂k(k−1)∕2n kℱxk.

Substituting ϕn−1x for x yields

∏ 0≤k≤n−1 1 − ϕ−kϕ̂kϕn−1x = ∏ 0≤k≤n−1 1 − ϕn−k−1ϕ̂kx = ∑ 0≤k≤n(−1)kϕk(k+1)∕2−nkϕ̂k(k−1)∕2n kℱ(ϕn−1x)k = ∑ 0≤k≤n(−1)kϕk(k+1)∕2−nkϕ̂k(k−1)∕2n kℱϕkn−kxk = ∑ 0≤k≤n(−1)kϕk(k+1)∕2−kϕ̂k(k−1)∕2n kℱxk = ∑ 0≤k≤n(−1)kϕk(k−1)∕2ϕ̂k(k−1)∕2n kℱxk = ∑ 0≤k≤n(−1)k(ϕϕ̂)k(k−1)∕2n kℱxk = ∑ 0≤k≤n(−1)k(−1)k(k−1)∕2n kℱxk = ∑ 0≤k≤n(−1)k(k+1)∕2n kℱxk.

Substituting 1∕x for x yields

∏ 0≤k≤n−1 1 − ϕn−k−1ϕ̂k∕x = ∏ 0≤k≤n−1x − ϕn−k−1ϕ̂k x = 1 xn ∏ 0≤k≤n−1 x − ϕn−k−1ϕ̂k = ∑ 0≤k≤n(−1)k(k+1)∕2n kℱ(1∕x)k = ∑ 0≤k≤n(−1)k(k+1)∕2n kℱ 1 xk = ∑ 0≤k≤n(−1)⌈k∕2⌉n kℱ 1 xk by (30.9)

if and only if

∏ 0≤k≤n−1 x − ϕn−k−1ϕ̂k = ∑ 0≤k≤n(−1)⌈k∕2⌉n kℱxn−k,

or equivalently,

∏ 0≤j≤n x − ϕjϕ̂n−j = ∑ 0≤k≤n+1(−1)⌈k∕2⌉n + 1 k ℱxn+1−k,

and hence the result.

Preliminary Result 30.11. We may show that

An+1k n,j = n j Fk+1jF kn−j. (30.11)

In the case that k = 0,

An+10 n,j = δnj = n j F0+1jF 0n−j.

Then, assuming

An+1k n,j = n j Fk+1jF kn−j,

we must show that

An+1k+1 n,j = n j Fk+2jF k+1n−j.

But

An+1k+1 n,j = An+1k ⋅A n+1 n,j = ∑ 0≤m≤n An+1k n,m An+1 m,j = ∑ 0≤m≤n n mFk+1mF kn−m A n+1 m,j = ∑ 0≤m≤n n mFk+1mF kn−m m n − j = ∑ 0≤m≤n n n − j n − (n − j) m − (n − j)Fk+1mF kn−m by Eq. (1.2.6-2) = ∑ 0≤m≤n n n − j j j + m − nFk+1mF kn−m = ∑ 0≤m≤n n n − jFk+1n−j j j + m − nFk+1j+m−nF kn−m = n j Fk+1n−j ∑ 0≤m≤j j mFk+1mF kj−m = n j Fk+1n−j F k+1 + Fk j = n j Fk+2jF k+1n−j

and hence the result.

Conclusion. We will now show that

∑ 0≤k≤mm k ℱ(−1)⌈k∕2⌉F n′−km−1 = 0.

From (30.8) and (30.10), the characteristic polynomial satisifes

pAn+1(x) = ∏ 0≤j≤n x − ϕjϕ̂n−j = ∑ 0≤k≤n+1(−1)⌈k∕2⌉n + 1 k ℱxn+1−k.

But, by the Cayley-Hamilton theorem, every matrix satisifes its characteristic polynomial. And so,

∑ 0≤k≤n+1(−1)⌈k∕2⌉n + 1 k ℱAn+1n′−1−k = 𝒪

for n′− 1 ≥ n + 1, where 𝒪 denotes the (n + 1) × (n + 1) zero matrix. By (30.11), for n = j and k = n′− 1 − k,

An+1n′−1−k n,n = n nFn′−1−k+1nF n′−1−kn−n = F n′−kn.

And so,

∑ 0≤k≤n+1(−1)⌈k∕2⌉n + 1 k ℱFn′−kn = 0,

or equivalently,

∑ 0≤k≤mm k ℱ(−1)⌈k∕2⌉F n′−km−1 = 0.

This concludes the proof. □

______________________________________________________________________________________________________________________________

[D. Jarden, Recurring Sequences, 2nd ed. (Jerusalem, 1966), 30–33; J. Riordan, Duke Math. J. 29 (1962), 5–12]

31. [M20] Show that F2nϕ mod 1 = 1 − ϕ−2n and F2n+1ϕ mod 1 = ϕ−2n−1.

We may show both identities.

Proposition. F2nϕ mod 1 = 1 − ϕ−2n.

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

F2nϕ mod 1 = 1 − ϕ−2n,

or equivalently that

1∣F2nϕ − (1 − ϕ−2n).

But clearly, 1∣F2n+1 − 1, and

F2n+1 − 1 = F2nϕ − F2nϕ + F2n+1 − 1 = F2nϕ + (−1)2n+1F 2nϕ + (−1)2(n+1)F 2n+1 − 1 = F2nϕ + (−1)2n+1F 2nϕ + (−1)2n+2F 2n+1 − 1 = F2nϕ + F−2nϕ + F−(2n+1) − 1 by exercise 8 = F2nϕ − 1 + F−2nϕ + F−2n−1 = F2nϕ − 1 + ϕ−2n by exercise 11 = F2nϕ − (1 − ϕ−2n).

That is,

1∣F2nϕ − (1 − ϕ−2n)

as we needed to show. □

Proposition. F2n+1ϕ mod 1 = ϕ−2n−1.

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

F2n+1ϕ mod 1 = ϕ−2n−1,

or equivalently that

1∣F2n+1ϕ − ϕ−2n−1.

But clearly, 1∣F2n+2, and

F2n+2 = F2n+1ϕ − F2n+1ϕ + F2n+2 = F2n+1ϕ − (−1)2(n+1)F 2n+1ϕ − (−1)2(n+1)+1F 2n+2 = F2n+1ϕ − (−1)2n+2F 2n+1ϕ − (−1)2n+3F 2n+2 = F2n+1ϕ − F−(2n+1)ϕ − F−(2n+2) by exercise 8 = F2n+1ϕ −F−2n−1ϕ + F−2n−2 = F2n+1ϕ − ϕ−2n−1. by exercise 11

That is,

1∣F2n+1ϕ − ϕ−2n−1

as we needed to show. □

32. [M24] The remainder of one Fibonacci number divided by another is ± a Fibonacci number: Show that, modulo Fn,

Fmn+r ≡ Fr, if m mod 4 = 0; (−1)r+1Fn−r, if m mod 4 = 1; (−1)nFr, if m mod 4 = 2; (−1)r+1+nFn−r,if m mod 4 = 3.

Proposition. Fmn+r ≡ Fr if m mod 4 = 0 (−1)r+1Fn−r if m mod 4 = 1 (−1)nFr if m mod 4 = 2 (−1)r+1+nFn−rif m mod 4 = 3 (mod ⁡Fn).

Proof. Let m,n,r be arbitrary integers, such that m = n = r = 0 or 0 ≤ r < m ≤ n. We must show that

Fmn+r ≡ Fr if m mod 4 = 0 (−1)r+1Fn−r if m mod 4 = 1 (−1)nFr if m mod 4 = 2 (−1)r+1+nFn−rif m mod 4 = 3 (mod ⁡Fn).

As preliminaries, note that since

Fn ≡ 0(mod ⁡Fn),

by repeated applications of Law 1.2.4-A,

aFn ≡ 0(mod ⁡Fn),

for any integer a, which will be hereafter indicated as by Law 1.2.4-A*. Also

Fn ≡ 0 ≡ Fn ≡ Fn+1 − Fn−1(mod ⁡Fn)

if and only if

Fn+1 ≡ Fn−1(mod ⁡Fn). (32.1)

In the case that m mod 4 = 0, we have that

Fr ≡ Fr ≡ Fn+10F r ≡ Fn+1mmod4F r(mod ⁡Fn).

In the case that m mod 4 = 1, we have that

(−1)r+1F n−r ≡ (−1)r+1F n−rF1 ≡ (−1)r+1F n−r(−1)2F 1 ≡ (−1)r+1F n−r(−1)1+1F 1 ≡ (−1)r+1F n−rF−1 by exercise 8 ≡ (−1)r+1F n−(r+1)−(−1)F−1 ≡ F(r+1)+(−1)Fn−(−1) − Fr+1Fn by exercise 17 ≡ FrFn+1 − Fr+1Fn ≡ FrFn+1 by Law 1.2.4-A* ≡ Fn+11F r ≡ Fn+1mmod4F r(mod ⁡Fn).

In the case that m mod 4 = 2, we have that

(−1)nF r ≡ (−1)nF 1Fr ≡ (−1)n(−1)2F 1Fr ≡ (−1)n(−1)1+1F 1Fr ≡ (−1)nF −1F1Fr by exercise 8 ≡ (−1)nF n−n−1F1Fr ≡ (Fn+1Fn−1 − FnFn)Fr by exercise 17 ≡ Fn+1Fn−1Fr − Fn2F r ≡ Fn+1Fn−1Fr by Law 1.2.4-A* ≡ Fn+1Fn+1Fr by (32.1) ≡ Fn+12F r ≡ Fn+1mmod4F r(mod ⁡Fn).

In the case that m mod 4 = 3, we have that

(−1)r+1+nF n−r ≡ (−1)n(−1)r+1F n−r ≡ (−1)n(−1)r+1F n−rF1 ≡ (−1)n(−1)r+1F n−r(−1)2F 1 ≡ (−1)n(−1)r+1F n−r(−1)1+1F 1 ≡ (−1)n(−1)r+1F n−rF−1 by exercise 8 ≡ (−1)n(−1)r+1F n−(r+1)−(−1)F−1 ≡ (−1)nF (r+1)+(−1)Fn−(−1) − Fr+1Fn by exercise 17 ≡ (−1)nF rFn+1 − Fr+1Fn ≡ (−1)nF rFn+1 by Law 1.2.4-A* ≡ (−1)nF 1FrFn+1 ≡ (−1)n(−1)2F 1FrFn+1 ≡ (−1)n(−1)1+1F 1FrFn+1 ≡ (−1)nF −1F1FrFn+1 by exercise 8 ≡ (−1)nF n−n−1F1FrFn+1 ≡ (Fn+1Fn−1 − FnFn)FrFn+1 by exercise 17 ≡ Fn+12F n−1Fr − Fn2F rFn+1 ≡ Fn+12F n−1Fr by Law 1.2.4-A* ≡ Fn+12F n+1Fr by (32.1) ≡ Fn+13F r ≡ Fn+1mmod4F r(mod ⁡Fn).

That is, we must show that

Fmn+r ≡ Fn+1mmod4F r(mod ⁡Fn).

If m = 0, then n = m = r = 0, m mod 4 = 0, and

Fmn+r ≡ F0⋅0+0 ≡ F0 ≡ F10F 0 ≡ F0+10F 0 ≡ Fn+1mmod4F r(mod ⁡Fn).

If m = 1, then m mod 4 = 1, and

Fmn+r ≡ F1⋅n+r ≡ Fn+r ≡ FrFn+1 + Fr−1Fn by Eq. (4) ≡ FrFn+1 by Law 1.2.4-A* ≡ Fn+11F r ≡ Fn+1mmod4F r(mod ⁡Fn).

If m = 2, then m mod 4 = 2, and

Fmn+r ≡ F2⋅n+r ≡ Fn+n+r ≡ Fn+rFn+1 + Fn+r−1Fn by Eq. (4) ≡ Fn+rFn+1 by Law 1.2.4-A* ≡ (FrFn+1 + Fr−1Fn)Fn+1 by Eq. (4) ≡ FrFn+12 + F r−1Fn+1Fn ≡ FrFn+12 by Law 1.2.4-A* ≡ Fn+12F r ≡ Fn+1mmod4F r(mod ⁡Fn).

If m = 3, then m mod 4 = 3, and

Fmn+r ≡ F3⋅n+r ≡ Fn+2n+r ≡ F2n+rFn+1 + F2n+r−1Fn by Eq. (4) ≡ F2n+rFn+1 by Law 1.2.4-A* ≡ Fn+n+rFn+1 ≡ (Fn+rFn+1 + Fn+r−1Fn)Fn+1 by Eq. (4) ≡ Fn+rFn+12 + F n+r−1Fn+1Fn ≡ Fn+rFn+12 by Law 1.2.4-A* ≡ (FrFn+1 + Fr−1Fn)Fn+12 by Eq. (4) ≡ FrFn+13 + F r−1Fn+12F n ≡ FrFn+13 by Law 1.2.4-A* ≡ Fn+13F r ≡ Fn+1mmod4F r(mod ⁡Fn).

Then, assuming

Fmn+r ≡ Fn+1mmod4F r(mod ⁡Fn),

we must show that

F(m+1)n+r ≡ Fn+1(m+1)mod4F r(mod ⁡Fn).

But

F(m+1)n+r ≡ Fmn+n+r ≡ Fn+mn+r ≡ Fmn+rFn+1 + Fmn+r−1Fn by Eq. (4) ≡ Fmn+rFn+1 by Law 1.2.4-A* ≡ Fn+1mmod4F rFn+1 ≡ Fn+1mmod4+1F r(mod ⁡Fn).

Here, we divide the proof into cases depending on m mod 4. In the case that m mod 4 = 0, (m + 1) mod 4 = 1 and

Fn+1mmod4+1F r ≡ Fn+10+1F r ≡ Fn+11F r ≡ Fn+1(m+1)mod4F r(mod ⁡Fn).

In the case that m mod 4 = 1, (m + 1) mod 4 = 2 and

Fn+1mmod4+1F r ≡ Fn+11+1F r ≡ Fn+12F r ≡ Fn+1(m+1)mod4F r(mod ⁡Fn).

In the case that m mod 4 = 2, (m + 1) mod 4 = 3 and

Fn+1mmod4+1F r ≡ Fn+12+1F r ≡ Fn+13F r ≡ Fn+1(m+1)mod4F r(mod ⁡Fn).

In the case that m mod 4 = 3, (m + 1) mod 4 = 0 and

Fn+1mmod4+1F r ≡ Fn+13+1F r ≡ Fn+14F r ≡ Fn+1Fn+1 2F r ≡ Fn+1Fn−1 2F r by (32.1) ≡ Fn+1Fn−1 2F r + FnFr −2FnFn+1Fn−1 + Fn3 by Law 1.2.4-A* ≡ Fn+1Fn−1 2 + F n −2FnFn+1Fn−1 + Fn3 F r ≡ Fn+1Fn−1 2 − 2F n2F n+1Fn−1 + Fn2 2 F r ≡ Fn+1Fn−1 − Fn2 2F r ≡ Fn+1Fn−1 − FnFn 2F r ≡ (−1)nF n−n−1F1 2F r by exercise 17 ≡ (−1)nF −1F1 2F r ≡ (−1)nF −1 2F r ≡ (−1)n(−1)1+1F 1 2F r by exercise 8 ≡ (−1)n(−1)2F 1 2F r ≡ (−1)n(−1)2 2F r ≡ (−1)n 2F r ≡ (−1)2nF r ≡ (−1)2 nF r ≡ 1nF r ≡ 1 ⋅ Fr ≡ Fn+10F r ≡ Fn+1(m+1)mod4F r(mod ⁡Fn).

And so,

F(m+1)n+r ≡ Fn+1mmod4+1F r ≡ Fn+1(m+1)mod4F r(mod ⁡Fn)

as we needed to show. □

33. [HM24] Given that z = π∕2 + iln ⁡ ϕ, show that sin ⁡ nz∕sin ⁡ z = i1−nFn.

Proposition. sin ⁡ (nz)∕sin ⁡ (z) = i1−nFn if z = π∕2 + iln ⁡ ϕ.

Proof. Let n be an arbitrary nonnegative integer, and z = π∕2 + iln ⁡ ϕ. We must show that

sin ⁡ (nz)∕sin ⁡ (z) = i1−nF n.

As preliminaries, note that

cos ⁡ (z) = 1 2(eiz + e−iz) = 1 2(ei(π∕2+i ln ⁡ ϕ) + e−i(π∕2+i ln ⁡ ϕ)) = 1 2(eiπ∕2+i2 ln ⁡ ϕ + e−(iπ∕2+i2 ln ⁡ ϕ )) = 1 2(eiπ∕2−ln ⁡ ϕ + e−iπ∕2+ln ⁡ ϕ) = 1 2(eiπ∕2e− ln ⁡ ϕ + e−iπ∕2eln ⁡ ϕ) = 1 2(eiπ(eln ⁡ ϕ)−1 + (eiπ)−1eln ⁡ ϕ) = 1 2(−1(ϕ)−1 + (−1)−1ϕ) = 1 2(i(ϕ)−1 + (i)−1ϕ) = 1 2(i∕ϕ + ϕ∕i) = 1 2(2i∕(1 + 5) + (1 + 5)∕2i) = 1 2((2i)2∕2i(1 + 5) + (1 + 5)2∕2i(1 + 5)) = 1 2(−4∕(2i + 2i5) + (1 + 25 + 5)∕(2i + 2i5)) = 1 2(−4 + (1 + 25 + 5))∕(2i + 2i5) = 1 2(−4 + 1 + 25 + 5)∕(2i + 2i5) = 1 2(2 + 25)∕(2i + 2i5) = (1 + 5)∕2i(1 + 5) = 1∕2i = −i∕2

and

2sin ⁡ (nz)cos ⁡ (z) = sin ⁡ (nz + z) + sin ⁡ (nz − z) = sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z)

so that

2sin ⁡ (nz)cos ⁡ (z) = sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z) ⇔ − 2isin ⁡ (nz)∕2 = sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z) ⇔ − isin ⁡ (nz) = sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z) ⇔sin ⁡ (nz) = −(sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z))∕i ⇔sin ⁡ (nz) = i(sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z)) ⇔sin ⁡ (nz)∕sin ⁡ (z) = i(sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z))∕sin(z).

If n = 0,

sin ⁡ (nz)∕sin ⁡ (z) = i(sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z))∕sin(z) = i(sin ⁡ (z) + sin ⁡ (−z))∕sin(z) = i(sin ⁡ (z) − sin ⁡ (z))∕sin(z) = i ⋅ 0 = i1F 0 = i1−nF n;

and if n = 1,

sin ⁡ (nz)∕sin ⁡ (z) = i(sin ⁡ ((n + 1)z) + sin ⁡ ((n − 1)z))∕sin(z) = i(sin ⁡ (2z) + sin ⁡ (0))∕sin(z) = isin ⁡ (2z)∕sin(z) = 2icos ⁡ (z)sin ⁡ (z)∕sin ⁡ (z) = 2icos ⁡ (z) = −2i2∕2 = −i2 = −(−1) = 1 = i0 = i1−1F 1 = i1−nF n.

Then, assuming that

sin ⁡ (nz)∕sin ⁡ (z) = i1−nF n,

we must show that

sin ⁡ ((n + 1)z)∕sin ⁡ (z) = i1−(n+1)F n+1.

But

sin ⁡ ((n + 1)z)∕sin ⁡ (z) = (2cos ⁡ (z)sin ⁡ (nz) − sin ⁡ ((n − 1)z))∕sin ⁡ (z) = (−2isin ⁡ (nz)∕2 − sin ⁡ ((n − 1)z))∕sin ⁡ (z) = (−isin ⁡ (nz) − sin ⁡ ((n − 1)z))∕sin ⁡ (z) = i−1 sin ⁡ (nz)∕sin ⁡ (z) − sin ⁡ ((n − 1)z)∕sin ⁡ (z) = i−1i1−nF n − i1−(n−1)F n−1 = i1−(n+1)F n − i1−n+1F n−1 = i1−(n+1)F n + i1−n−1F n−1 = i1−(n+1)F n + i1−(n+1)F n−1 = i1−(n+1)(F n + Fn−1) = i1−(n+1)F n+1

as we needed to show. □

▸ 34. [M24] (The Fibonacci number system.) Let the notation k ≫ m mean that k ≥ m + 2. Show that every positive integer n has a unique representation n = Fk1 + Fk2 + ⋯ + Fkr, where k1 ≫ k2 ≫⋯ ≫ kr ≫ 0.

First, we prove a corollary.

Proposition. ∑ ⁡ 1≤j≤rFkj < Fkr+1, where kj > kj+1 + 1 for 1 ≤ j < r and kr > 1.

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

∑ 1≤j≤rFkj < Fk1+1 (34.1)

where kj > kj+1 + 1 for 1 ≤ j < r and kr > 1. If r = 1,

∑ 1≤j≤1Fkj = Fk1 = F2 = 1 < 2 = F3 = F2+1 = Fk1+1

where k1 = 2 > 1. Then, assuming

∑ 1≤j≤rFkj < Fk1+1

where kj > kj+1 + 1 for 1 ≤ j < r and kr > 1, we must show that

∑ 1≤j≤r′Fkj′ < Fk1′+1

where r′ = r + 1, kj′ > kj+1′ + 1 for 1 ≤ j < r′ and kr′ > 1. But since

k1′ > k 2′ + 1 ⇔k 1′≥ k 2′ + 2 ⇔k1′− 1 ≥ k 2′ + 1 ⇔Fk2′+1 ≤ Fk1′−1

then

∑ 1≤j≤r′Fkj′ = Fk1′ + ∑ 2≤j≤r′Fkj′ < Fk1′ + Fk2′+1 ≤ Fk1′ + Fk1′−1 = Fk1′+1

as we needed to show. □

Then, we proceed with the requested proof.

Proposition. Every positive integer n has a unique representation n = ∑ ⁡ 1≤j≤rFkj, where kj > kj+1 + 1 for 1 ≤ j < r and kr > 1.

Proof. Let n be an arbitrary positive integer. We must show that for n there exists a representation

n = ∑ 1≤j≤rFkj

where kj > kj+1 + 1 for 1 ≤ j < r and kr > 1; and that this representation is unique.

Existence. If n = 1,

1 = ∑ 1≤j≤1Fkj = Fk1 = F2

where k1 = 2 > 1; if n = 2,

2 = ∑ 1≤j≤1Fkj = Fk1 = F3

where k1 = 3 > 1; if n = 3,

3 = ∑ 1≤j≤1Fkj = Fk1 = F4

where k1 = 4 > 1; and if n = 4,

4 = ∑ 1≤j≤2Fkj = Fk1 + Fk2 = F4 + F2 = 3 + 1

where k1 = 4 > 2 + 1 = k2 + 1, k2 = 2 > 1. Then, assuming there exists a representation

n = ∑ 1≤j≤rFkj,

we must show that there exists a representation

n + 1 = ∑ 1≤j≤r′Fkj′.

In the case that n + 1 is a Fibonacci number Fk′, we have that

n + 1 = ∑ 1≤j≤1Fkj′ = Fk1′ = Fk′

where k1′ = k′ > 1. Otherwise, in the case that n + 1 is not a Fibonacci number, it must lie between two Fibonacci numbers. That is, there must exist a j′ such that

Fj′ < n + 1 < Fj′+1.

Let m = n + 1 − Fj′. Since m ≤ n, by the inductive hypothesis, there exists a representation

m = ∑ 1≤j≤rFkj.

But

n + 1 < Fj′+1 ⇔m + Fj′ < Fj′+1 ⇔m < Fj′+1 − Fj′ ⇔m < Fj′−1.

That is, m does not contain Fj′−1, and so

n + 1 = ∑ 1≤j≤r′Fkj′ = Fj′ + m = Fj′ + ∑ 1≤j≤rFkj

where r′ = r + 1, kj′ = kj−1 if 2 ≤ j ≤ r′, k1′ = j′ otherwise, and k1′ = j′ > k1 + 1, and hence existence.

Uniqueness. Let n have the two representations

n = ∑ 1≤j≤rFkj

and

n = ∑ 1≤j≤r′Fkj′;

and let the Fibonacci numbers of each be represented by the sets S = {Fkj} and S′ = {Fkj′}. The previous result has shown that they each contain non-consecutive Fibonacci numbers, and have the same cardinality: r = r′. Then let T = S − S′ and T′ = S′− S. Since ∑ ⁡ s∈Ss = ∑ ⁡ s′∈S′s′, we also have that ∑ ⁡ t∈Tt = ∑ ⁡ t′∈T′t′. We will assume that S≠S′, so that neither T nor T′ is empty. Select the largest element of each, and let these be Ft and Ft′, respectively. Note that Ft≠Ft′. Without loss of generaltiy, assume Ft < Ft′. Then, by (34.1),

∑ t∈Tt < Ft+1 ≤ Ft′ ≤∑ t′∈T′t′.

But ∑ ⁡ t∈Tt = ∑ ⁡ t′∈T′t′, a contradiction, and so, T = T′ = ∅ and S = S′, and hence uniqueness.

This concludes the proof. □

______________________________________________________________________________________________________________________________

[C. G. Lekkerkerker, Simon Stevin 29 (1952), 190–195; section 7.2.1.7; exercise 5.4.2-10; section 7.1.3]

35. [M24] (A phi number system.) Consider real numbers written with the digits 0 and 1 using base ϕ; thus (100.1)ϕ = ϕ2 + ϕ−1. Show that there are infinitely many ways to represent the number 1; for example, 1 = (.11)ϕ = (.011111… ⁡)ϕ. But if we require that no two adjacent 1s occur and that the representation does not end with the infinite sequence 01010101… ⁡, then every nonnegative number has a unique representation. What are the representations of integers?

In the phi number system, there are infinitely many ways to represent the number 1. To see why, note that since ϕk = ϕk−1 + ϕk−2,

1 = ϕ0 = 1 ϕ.

We may continue to expand the last term for infinitely many ways to represent the number 1. As

1 = ϕ0 = ϕ−1 + ϕ−2 = .11 ϕ,
1 = ϕ−1 + ϕ−2 = ϕ−1 + ϕ−3 + ϕ−4 = .1011 ϕ,

or

1 = ϕ−1 + ϕ−3 + ϕ−4 = ϕ−1 + ϕ−3 + ϕ−5 + ϕ−6 = .101011 ϕ,

ad infinitum. But we may avoid this by requiring that no two adjacent 1s occur and that the representation does not end with the infinite sequence 01010101… ⁡. That is, by requiring that all adjacent ϕk−1 + ϕk−2 terms be instead represented by their sum ϕk and not avoided by further, infinite expansion of the last term.

The representations of nonnegative integers are then as follows.

Algorithm 35.1 (Representation of nonnegative integers in a phi number system.). Given a nonnegative integer n, find its unique representation in the phi number system.

35.1.a.
[Initialize.] Set x ← n, D ← ∅, the set of integer phi exponents.
35.1.b.
[Test for zero.] If x = 0, the algorithm terminates; we have the representation of n by the integer phi exponents in D, empty if n zero.
35.1.c.
[Find largest exponent.] If x > 0, find the largest k such that ϕk ≤ x, set D ← D ∪{k}, x ← x − ϕk, and return to step 35.1.b. ■

For example, if n = 0, D = ∅ and n = 0ϕ; if n = 1, D = {0} and n = 1ϕ; if n = 2, D = {1,−2} and n = 10.01ϕ; etc. Since we always choose ϕk over any of the terms of the sum ϕk−1 + ϕk−2, we satisfy the requirement of having no two adjacent 1s and not ending with the infinite sequence 01010101… ⁡

________________________________________________________________________________

[G. M. Bergman, Mathematics Magazine 31 (1957), 98–110]

▸ 36. [M32] (Fibonacci strings.) Let S1 = “a”, S2 = “b”, and Sn+2 = Sn+1Sn, n > 0; in other words, Sn+2 is formed by placing Sn at the right of Sn+1. We have S3 = “ba”, S4 = “bab”, S5 = “babba”, etc. Clearly Sn has Fn letters. Explore the properties of Sn. (Where do double letters occur? Can you predict the value of the kth letter of Sn? What is the density of the bs? And so on.)

As noted, Sn has Fn letters.

Except for S1 = a, no Sn starts with a, but all with b; and since S2 = b, every a is preceded by a b. The letter b is doubled only when two terms are concatenated. That is, there are no a doubles, only b doubles.

The kth letter of Sn is α(Sn,k) where

α(Sn,k) = bif n > 1 and ⌊(k + 1)ϕ−1⌋−⌊kϕ−1⌋ = 1 aotherwise,

for n > 0, 1 ≤ k ≤ Fn, as proven next.

In the case that n = 1, k = 1, α(S1,1) = α(a,1) = a, and n ≯ 1. In the case that n = 2, k = 1, α(S2,1) = α(b,1) = b, and

⌊(1 + 1)ϕ−1⌋−⌊1 ⋅ ϕ−1⌋ = ⌊2 ⋅ ϕ−1⌋−⌊1 ⋅ ϕ−1⌋ = 1 − 0 = 1.

In the case that n = 3, 1 ≤ k ≤ F3 = 2, α(S3,k) = α(ba,k); and if k = 1, then α(ba,1) = b and

⌊(1 + 1)ϕ−1⌋−⌊1 ⋅ ϕ−1⌋ = ⌊2 ⋅ ϕ−1⌋−⌊1 ⋅ ϕ−1⌋ = 1 − 0 = 1;

and if k = 2, then α(ba,2) = a and

⌊(2 + 1)ϕ−1⌋−⌊2 ⋅ ϕ−1⌋ = ⌊3 ⋅ ϕ−1⌋−⌊2 ⋅ ϕ−1⌋ = 1 − 1 = 0.

Then, assuming the definition of α holds for Sn+1, we must show that it holds for Sn+1. But

α(Sn+1,k) = α(SnSn−1,k).

In the case that 1 ≤ k ≤ Fn, then α(SnSn−1,k) = α(Sn,k), and α holds by the inductive hypothesis. Otherwise, in the case that Fn + 1 ≤ k ≤ Fn+1, then α(SnSn−1,k) = α(Sn−1,k − Fn) = α(Sn−1,k′) for 1 ≤ k′ = k − Fn ≤ Fn−1, and α holds again by the inductive hypothesis, and hence the result.

The density of the bs is is β(Sn) where

β(Sn) = ⌊(Fn + 1)ϕ−1⌋if n > 1 0 otherwise,

for n > 0, as proven next.

In the case that n = 1, β(S1) = β(a) = 0, and n ≯ 1. In the case that n = 2, β(S2) = β(b) = 1, and

⌊(F2 + 1)ϕ−1⌋ = ⌊(1 + 1)ϕ−1⌋ = ⌊2 ⋅ ϕ−1⌋ = 1.

In the case that n = 3, β(S3) = β(ba) = 1, and

⌊(F3 + 1)ϕ−1⌋ = ⌊(2 + 1)ϕ−1⌋ = ⌊3 ⋅ ϕ−1⌋ = 1.

Then, assuming the definition of β holds for Sn+1, we must show that it holds for Sn+1. But

β(Sn+1) = β(Sn) + β(Sn−1).

For either term, β holds by the inductive hypothesis, and hence the result.

______________________________________________________________________________________________________________________________

[K. B. Stolarsky, Canadian Math. Bull. 19 (1976), 473–482]

▸ 37. [M35] (R. E. Gaskell, M. J. Whinihan.) Two players compete in the following game: There is a pile containing n chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding player has taken. The player who removes the last chip wins. (For example, suppose that n = 11; player A removes 3 chips; player B may remove up to 6 chips, and he takes 1. There remain 7 chips; player A may take 1 or 2 chips, and he takes 2; player B may remove up to 4, and he picks up 1. There remain 4 chips; player A now takes 1; player B must take at least one chip and player A wins in the following turn.)

What is the best move for the first player to make if there are initially 1000 chips?

The best move for the first player to make if there are initially 1000 chips is to take 13 chips, as explained below.

Definitions. Define the game as follows. Let nκ be the number of chips on the κth move, 1 ≤ κ, nκ ≥ 0, so that n1 represents the number of chips started with. Let tκ be the number of chips taken in the κth move, so that

nκ = nκ−1 − tκ−1

for κ > 1. In addition, the rules require that

1 ≤ tκ ≤ qκ = n1 − 1if κ = 1 2tκ−1 otherwise

for κ ≥ 1, thus n1 > 1 necessarily. The game is won on the κth move when finally nκ+1 = 0. We want to find the winning move(s) for the first player, for κ odd.

Let

nκ = ∑ 1≤j≤rκFkκ,j

be the unique Fibonacci representation of nκ, kκ,j > kκ,j+1 + 1 for 1 ≤ j < rκ and kκ,rκ > 1; and

μ(nκ) = Fkκ,rκ.

The winning move, if it exists, is to remove tκ ∈ Tκ chips where

Tκ = 1 ≤∑ j1≤j≤rκFkκ,j ≤ qκj1 = 1 ∨ Fkκ,j 1−1 > 2∑ j1≤j≤rκFkκ,j ,

where 1 ≤ j1 ≤ rκ.

Preliminary Result 37.1. Since kκ,rκ > 1,

Fkκ,rκ+1 > Fkκ,rκ ⇒Fkκ,rκ+1 + Fkκ,rκ > Fkκ,rκ + Fkκ,rκ ⇒Fkκ,rκ+2 > 2Fkκ,rκ ⇒Fkκ,rκ+2 > 2μ ∑ 1≤j≤rκFkκ,j ⇒Fkκ,rκ+2 > 2μ(nκ)

and since kκ,rκ > kκ,rκ+1 + 1,

Fkκ,rκ > Fkκ,rκ+1+1 ⇒Fkκ,rκ−1+1 > Fkκ,rκ+2 ⇒Fkκ,rκ−1 ≥ Fkκ,rκ+2

so that

2μ(nκ) < Fkκ,rκ+2 ≤ Fkκ,rκ−1 = μ ∑ 1≤j≤rκ−1Fkκ,j = μ ∑ 1≤j≤rκFkκ,j − Fkκ,rκ = μ ∑ 1≤j≤rκFkκ,j − μ ∑ 1≤j≤rκFkκ,j = μ(nκ − μ(nκ)).

That is,

μ(nκ − μ(nκ)) > 2μ(nκ). (37.1)

Preliminary Result 37.2. First note that for j > 1 arbitrary, since Fj = Fj−1 + Fj−2 and Fj−2 ≤ Fj−1, we have that

Fj ≤ Fj−1 + Fj−1 = 2Fj−1

or equivalently that

Fj ≤ 2Fj−1 ⇔2Fj−1 ≥ Fj ⇔Fj−1 ≥ 1 2Fj ⇔ − Fj−1 ≤−1 2Fj.

Also note that for k > j > 0 arbitrary, if k = 2u + 1 and j = 2v + 1 so that (k − 1 − j) mod 2 = ((2u + 1) − 1 − (2v + 1)) mod 2 = (2(u − v) − 1) mod 2 = 1 and k mod 2 = 1,

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = Fk − Fj−1+(k−1−j)mod2.

If u = v + 1⇒k = j + 2,

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = ∑ v+1≤i≤uF2i−1+kmod2 = ∑ v+1≤i≤uF2i = ∑ u≤i≤uF2i = F2u = F2u+1 − F2u−1 = Fk − F2(v+1)−1 = Fk − F2v+2−1 = Fk − F2v+1 = Fk − Fj = Fk − Fj−1+1 = Fk − Fj−1+1 = Fk − Fj−1+(k−1−j)mod2.

Assuming

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = Fk − Fj−1+(k−1−j)mod2,

we must show that

∑ v+(k+2−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2.

But since (k + 2 − 1 − j) mod 2 = 1 and (k + 2) mod 2 = 1,

∑ v+(k+2−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = ∑ v+1≤i≤u+1F2i−1+(k+2)mod2 = ∑ v+1≤i≤u+1F2i = F2(u+1) + ∑ v+1≤i≤uF2i = F2(u+1) + ∑ v+1≤i≤uF2i−1+kmod2 = F2(u+1) + Fk − Fj−1+(k−1−j)mod2 = F2u+2 + Fk − Fj−1+(k−1−j)mod2 = Fk+1 + Fk − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2

and hence the result for k = 2u + 1 and j = 2v + 1.

If k = 2u and j = 2v so that (k − 1 − j) mod 2 = (2u − 1 − 2v) mod 2 = (2(u − v) − 1) mod 2 = 1 and k mod 2 = 0,

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = Fk − Fj−1+(k−1−j)mod2.

If u = v + 1⇒k = j + 2,

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = ∑ v+1≤i≤uF2i−1+kmod2 = ∑ v+1≤i≤uF2i−1 = ∑ u≤i≤uF2i−1 = F2u−1 = F2u − F2u−2 = Fk − F2(v+1)−2 = Fk − F2v+2−2 = Fk − F2v = Fk − Fj = Fk − Fj−1+1 = Fk − Fj−1+1 = Fk − Fj−1+(k−1−j)mod2.

Assuming

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = Fk − Fj−1+(k−1−j)mod2,

we must show that

∑ v+(k+2−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2.

But since (k + 2 − 1 − j) mod 2 = 1 and (k + 2) mod 2 = 0,

∑ v+(k+2−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = ∑ v+1≤i≤u+1F2i−1+(k+2)mod2 = ∑ v+1≤i≤u+1F2i−1 = F2(u+1)−1 + ∑ v+1≤i≤uF2i−1 = F2(u+1)−1 + ∑ v+1≤i≤uF2i−1+kmod2 = F2(u+1)−1 + Fk − Fj−1+(k−1−j)mod2 = F2u+2−1 + Fk − Fj−1+(k−1−j)mod2 = F2u+1 + Fk − Fj−1+(k−1−j)mod2 = Fk+1 + Fk − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2

and hence the result for k = 2u and j = 2v.

If k = 2u + 1 and j = 2v so that (k − 1 − j) mod 2 = (2u + 1 − 1 − 2v) mod 2 = 2(u − v) mod 2 = 0 and k mod 2 = 1,

∑ v+(k−1−j)mod2≤i≤uF2i+1+kmod2 = Fk − Fj−1+(k−1−j)mod2.

If u = v⇒k = j + 1,

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = ∑ v+0≤i≤uF2i−1+kmod2 = ∑ v≤i≤uF2i = ∑ u≤i≤uF2i = F2u = F2u+1 − F2u−1 = Fk − F2u−1 = Fk − F2v−1 = Fk − Fj−1 = Fk − Fj−1+0 = Fk − Fj−1+(k−1−j)mod2.

Assuming

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = Fk − Fj−1+(k−1−j)mod2,

we must show that

∑ v+(k+2−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2.

But since (k + 2 − 1 − j) mod 2 = 0 and (k + 2) mod 2 = 1,

∑ v+(k−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = ∑ v+0≤i≤u+1F2i−1+(k+2)mod2 = ∑ v≤i≤u+1F2i = F2(u+1) + ∑ v≤i≤uF2i = F2u+2 + ∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = F2u+2 + Fk − Fj−1+(k−1−j)mod2 = Fk+1 + Fk − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2

and hence the result for k = 2u + 1 and j = 2v.

If k = 2u and j = 2v − 1 so that (k − 1 − j) mod 2 = (2u − 1 − (2v − 1)) mod 2 = 2(u − v) mod 2 = 0 and k mod 2 = 0,

∑ v+(k−1−j)mod2≤i≤uF2i+1+kmod2 = Fk − Fj−1+(k−1−j)mod2.

If u = v⇒k = j + 1,

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = ∑ v+0≤i≤uF2i−1+kmod2 = ∑ v≤i≤uF2i−1 = ∑ u≤i≤uF2i−1 = F2u−1 = F2u − F2u−2 = Fk − F2v−2 = Fk − Fj−1 = Fk − Fj−1+0 = Fk − Fj−1+(k−1−j)mod2.

Assuming

∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = Fk − Fj−1+(k−1−j)mod2,

we must show that

∑ v+(k+2−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2.

But since (k + 2 − 1 − j) mod 2 = 0 and (k + 2) mod 2 = 0,

∑ v+(k−1−j)mod2≤i≤u+1F2i−1+(k+2)mod2 = ∑ v+0≤i≤u+1F2i−1+(k+2)mod2 = ∑ v≤i≤u+1F2i−1 = F2(u+1)−1 + ∑ v≤i≤uF2i−1 = F2u+2−1 + ∑ v+(k−1−j)mod2≤i≤uF2i−1+kmod2 = F2u+1 + Fk − Fj−1+(k−1−j)mod2 = Fk+1 + Fk − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k−1−j)mod2 = Fk+2 − Fj−1+(k+2−1−j)mod2

and hence the result for k = 2u and j = 2v − 1.

Hence, in any and all cases

∑ v+(k−1−j)mod2≤i≤uF2i+1+kmod2 = ∑ ⌊j∕2⌋+(k−1−j)mod2≤i≤⌊k∕2⌋F2i+1+kmod2 = ∑ 2⌊j∕2⌋+2((k−1−j)mod2)+1+kmod2≤i≤2⌊k∕2⌋+1+kmod2Fi = Fk − Fj−1+(k−1−j)mod2.

Also, if k = 2u, so that k mod 2 = 0,

Fk = F2u = ∑ 0≤i≤u−1F2i+1 = ∑ 1≤i≤uF2i−1 = ∑ 1≤i≤u F2i+1 − F2i = ∑ 1≤i≤uF2i+1 −∑ 1≤i≤uF2i = ∑ 1≤i≤uF2i+1 −∑ 0≤i≤u−1F2i+2 ≤∑ 1≤i≤uF2i+1 −∑ 1≤i≤u−1F2i+1 ≤∑ 1≤i≤uF2i+1 −∑ 1≤i≤v+(k−1−j)mod2−1F2i+1 = ∑ v+(k−1−j)mod2≤i≤uF2i+1 = ∑ v+(k−1−j)mod2≤i≤uF2i+1+kmod2, ,

and if k = 2u + 1, so that k mod 2 = 1,

Fk = F2u+1 = 1 + ∑ 1≤i≤uF2i = 1 + ∑ 1≤i≤u F2i+1 − F2i−1 = 1 + ∑ 1≤i≤uF2i+1 −∑ 1≤i≤uF2i−1 = 1 + ∑ 1≤i≤uF2i+1 −∑ 0≤i≤u−1F2i+1 = ∑ 1≤i≤uF2i+1 −∑ 1≤i≤u−1F2i+1 ≤∑ 1≤i≤uF2i+1 −∑ 1≤i≤v+(k−1−j)mod2−1F2i+1 = ∑ v+(k−1−j)mod2≤i≤uF2i+1 ≤∑ v+(k−1−j)mod2≤i≤uF2i+1+kmod2, ,

so that in either case,

Fk ≤∑ v+(k−1−j)mod2≤i≤uF2i+1+kmod2 = ∑ 2⌊j∕2⌋+2((k−1−j)mod2)+1+kmod2≤i≤2⌊k∕2⌋+1+kmod2Fi.

Then let μ(m) = Fj, so that if m < Fk,

m < Fk ≤∑ 2⌊j∕2⌋+2((k−1−j)mod2)+1+kmod2≤i≤2⌊k∕2⌋+1+kmod2Fi = −Fj−1+(k−1−j)mod2 + Fk

In the case that (k − 1 − j) mod 2 = 0,

− Fj−1+(k−1−j)mod2 = −Fj−1+0 = −Fj−1 ≤−1 2Fj;

and in the case that (k − 1 − j) mod 2 = 1,

− Fj−1+(k−1−j)mod2 = −Fj−1+1 = −Fj ≤−1 2Fj+1 ≤−1 2Fj.

And so, in either case,

− Fj−1+(k−1−j)mod2 + Fk ≤−1 2Fj + Fk = −1 2μ(m) + Fk

if and only if

m ≤−1 2μ(m) + Fk ⇔ − Fk + m ≤−1 2μ(m) ⇔Fk − m ≥ 1 2μ(m) ⇔2(Fk − m) ≥ μ(m).

That is,

μ(m) ≤ 2(Fk − m) (37.2)

for 1 ≤ m < Fk.

Preliminary Result 37.3. Since Fκ,rκ = μ(nκ) > m ≥ 1, by (37.2)

2(Fκ,rκ − m) = 2(μ(nκ) − m) ≥ μ(m) = μ ∑ 1≤j≤rκ−1Fkκ,j + m = μ(nκ − Fkκ,rκ + m) = μ(nκ − μ(nκ) + m).

That is,

μ(nκ − μ(nκ) + m) ≤ 2(μ(nκ) − m) (37.3)

for 1 ≤ m < μ(nκ).

Preliminary Result 37.4. By (37.3), with m = μ(nκ) − m′,

μ(nκ − μ(nκ) + μ(nκ) − m′) = μ(n κ − m′) ≤ 2(μ(nκ) − μ(nκ) − m′) = 2m′.

That is,

μ(nκ − m) ≤ 2m (37.4)

for 1 ≤ m < μ(nκ).

Proof . In the case that μ(nκ) ≤ qκ and qκ ≥ nκ, we may win immediately in the κth move by taking tκ = nκ chips. But since nκ ≥ 1,

qκ ≥ nκ ≥ 1 ⇔1 ≤∑ j1≤j≤rκFkκ,j ≤ qκ

with j1 = 1, so that nκ ∈ Tκ.

Otherwise, if μ(nκ) ≤ qκ but qκ < nκ, we may take tκ = μ(nκ) chips in order to leave the other player in an unwinnable state where μ(nκ+1) > qκ+1. The move is valid since μ(nκ) ≥ 1,

qκ ≥ μ(nκ) ≥ 1 ⇔1 ≤∑ j1≤j≤rκFkκ,j ≤ qκ

with j1 = rκ, so that μ(nκ) ∈ Tκ, since by (37.1),

2∑ j1≤j≤rκFkκ,j = 2μ(nκ) < μ(nκ − μ(nκ)) = Fkκ,rκ−1.

The next state (to be shown to be unwinnable further below) is indeed one where μ(nκ+1) > qκ+1, since also by (37.1),

μ(nκ+1) = μ(nκ − tκ) = μ(nκ − μ(nκ)) > 2μ(nκ) = 2tκ = qκ+1.

In the case that μ(nκ) > qκ, there is no winnable move since qκ < nκ; but any move tκ will lead to a winnable state for the next player with μ(nκ+1) ≤ qκ+1. This follows from (37.4), since 1 ≤ tκ < μ(nκ) and

μ(nκ+1) = μ(nκ − tκ) ≤ 2tκ = qκ+1.

Example. Here we explain how we determined that taking 13 chips is the only winning move for the first player to make if there are initially 1000 chips. In this example,

n1 = 1000 = Fk1,1 + Fk1,r 1 = Fk1,1 + Fk1,2 = F16 + F7 = 987 + 13,

and κ = 1, so that q = 1000 − 1 = 999. For j1 = r1, since

987 = Fk1,1 = Fk1,2−1 = Fk1,r 1−1 > 2∑ r1≤j≤r1Fk1,j = 2Fk1,r 1 = 2 ⋅ 13 = 26,

we have a single winning move

t1 ∈ T1 = 13,

hence the unique solution.

________________________________________________________________________________

[M. J. Whinihan, Fibonacci Quart. 1 (December 1963), 9–12; A. Schwenk, Fibonacci Quarterly 8 (1970), 225–234]

38. [35] Write a computer program that plays the game described in the previous exercise and that plays optimally.

The following Java code plays the game described in exercise 37, and plays optimally.

class Options { 
 
   public Options(String[] arguments) throws NumberFormatException { 
      for (int index = 0; index < arguments.length; ++index) { 
         switch (arguments[index]) { 
            case "-n": 
               if ((numberOfChips = Integer.parseInt(arguments[++index])) <= 1) { 
                  throw new IllegalArgumentException( 
                     String.format( 
                        "number␣of␣chips␣n␣must␣be␣n␣>␣1:␣%d", 
                        numberOfChips 
                     ) 
                  ); 
               } 
               break; 
            case "-p": 
               isUserFirst = Integer.parseInt(arguments[++index]) % 2 == 1; 
               break; 
            default: 
               throw new IllegalArgumentException(arguments[index]); 
         } 
      } 
 
      assert (numberOfChips > 1); 
 
   } 
 
   public     int getNumberOfChips() { return numberOfChips; } 
   public boolean isUserFirst()      { return isUserFirst;   } 
 
   public int readNumberOfChipsTaken(InputStream in, int numberOfChipsTakeable) { 
      int numberOfChipsTaken = (new Scanner(in)).nextInt(); 
      if ((numberOfChipsTaken < 1) || (numberOfChipsTaken > numberOfChipsTakeable)) { 
         throw new IllegalArgumentException( 
            String.format( 
               "number␣of␣chips␣taken␣t␣must␣be␣1␣<=␣t␣<=␣%d:␣%d", 
               numberOfChipsTakeable, 
               numberOfChipsTaken 
            ) 
         ); 
      } 
      return numberOfChipsTaken; 
   } 
 
   private     int numberOfChips = 2; 
   private boolean isUserFirst   = true; 
 
} 
 
class State { 
 
   public State(int initialNumberOfChips, boolean isUserFirst) { 
      turn = 1; 
      isUserTurn = isUserFirst; 
      numberOfChips = initialNumberOfChips; 
      numberOfChipsTakeable = numberOfChips - 1; 
   } 
 
   public void take(int numberOfChipsTaken) { 
 
      assert ((1 <= numberOfChipsTaken) && (numberOfChipsTaken <= numberOfChipsTakeable)); 
 
      ++turn; 
      isUserTurn = !isUserTurn; 
      numberOfChips -= numberOfChipsTaken; 
      numberOfChipsTakeable = 2*numberOfChipsTaken; 
   } 
 
   public     int getTurn()                  { return turn;                  } 
   public boolean isUserTurn()               { return isUserTurn;            } 
   public     int getNumberOfChips()         { return numberOfChips;         } 
   public     int getNumberOfChipsTakeable() { return numberOfChipsTakeable; } 
 
   public void writePreSummary(PrintStream out) { 
      out.printf("Number␣of␣Chips:␣%d%n", numberOfChips); 
      out.printf("␣␣␣␣␣Goes␣First:␣%s%n", isUserTurn? "User" : "Computer"); 
      out.printf("---------------%n"); 
   } 
 
   public void writeSummary(PrintStream out) { 
      out.printf( 
         "[State]␣Turn:␣%d␣(%s);␣Chips:␣%d;␣Takeable:␣%d%n", 
         turn, 
         isUserTurn? "User" : "Computer", 
         numberOfChips, 
         numberOfChipsTakeable 
      ); 
   } 
 
   public void writePostSummary(PrintStream out) { 
      out.printf("------%n"); 
      out.printf("␣Turns:␣%d%n", turn - 1); 
      out.printf("Winner:␣%s%n", !isUserTurn? "User" : "Computer"); 
   } 
 
   private     int turn; 
   private boolean isUserTurn; 
   private     int numberOfChips; 
   private     int numberOfChipsTakeable; 
 
} 
 
class FibonacciNumber { 
 
   public FibonacciNumber(int index, int value) { 
      this.index = index; 
      this.value = value; 
   } 
 
   public int getIndex() { return index; } 
   public int getValue() { return value; } 
 
   private int index; 
   private int value; 
 
} 
 
class FibonacciNumbers { 
 
   public FibonacciNumber get(int index) { 
 
      assert (index >= 0); 
 
      FibonacciNumber fibonacciNumber = fibonacciNumberCache.get(index); 
      if (fibonacciNumber == null) { 
         fibonacciNumber = calculate(index); 
         fibonacciNumberCache.put(index, fibonacciNumber); 
      } 
      return fibonacciNumber; 
   } 
 
   public FibonacciNumber getLargestLessThanOrEqualTo(int value) { 
      int index = 0; 
      FibonacciNumber fibonacciNumber = get(index++); 
      while (true) { 
         FibonacciNumber nextFibonacciNumber = get(index++); 
         if (nextFibonacciNumber.getValue() > value) { 
            break; 
         } 
         fibonacciNumber = nextFibonacciNumber; 
      } 
      return fibonacciNumber; 
   } 
 
   protected FibonacciNumber calculate(int index) { 
      FibonacciNumber fibonacciNumber; 
      switch (index) { 
         case 0: 
         case 1: 
            fibonacciNumber = new FibonacciNumber(index, index); 
            break; 
         default: 
            fibonacciNumber = new FibonacciNumber( 
               index, 
               get(index-1).getValue() + get(index-2).getValue() 
            ); 
            break; 
      } 
      return fibonacciNumber; 
   } 
 
   private Map<Integer,FibonacciNumber> fibonacciNumberCache = new HashMap<>(); 
 
} 
 
class FibonacciBaseNumber { 
 
   public FibonacciBaseNumber(FibonacciNumbers fibonacciNumbers, int value) { 
 
      assert (value > 0); 
 
      this.value = value; 
      while (value > 0) { 
         FibonacciNumber digit = fibonacciNumbers.getLargestLessThanOrEqualTo(value); 
         digits.add(digit); 
         value -= digit.getValue(); 
      } 
   } 
 
   public int getSum(int fromIndex, int toIndex) { 
      int sum = 0; 
      for (int index = fromIndex; index <= toIndex; ++index) { 
         sum += get(index).getValue(); 
      } 
      return sum; 
   } 
 
   public                     int getValue()     { return value;             } 
   public                     int size()         { return digits.size();     } 
   public         FibonacciNumber get(int index) { return digits.get(index); } 
   public Stream<FibonacciNumber> stream()       { return digits.stream();   } 
 
   private                   int value; 
   private List<FibonacciNumber> digits = new ArrayList<FibonacciNumber>(); 
 
} 
 
class Solver { 
 
   public Solver(FibonacciNumbers fibonacciNumbers, State state) { 
      fibonacciBaseNumber = new FibonacciBaseNumber(fibonacciNumbers, state.getNumberOfChips()); 
      for (int index = 0; index < fibonacciBaseNumber.size(); ++index) { 
         int sum = fibonacciBaseNumber.getSum(index, fibonacciBaseNumber.size() - 1); 
         if ((1 <= sum) && (sum <= state.getNumberOfChipsTakeable())) { 
            if ((index == 0) || (fibonacciBaseNumber.get(index - 1).getValue() > 2*sum)) { 
               numberOfChipsToTake.add(sum); 
            } 
         } 
      } 
   } 
 
   public int getOptimalNumberOfChipsToTake() { 
      int optimalNumberOfChipsToTake = 1; 
      if (numberOfChipsToTake.size() > 0) { 
         optimalNumberOfChipsToTake = numberOfChipsToTake.first(); 
      } 
      return optimalNumberOfChipsToTake; 
   } 
 
   public void writeSummary(PrintStream out) { 
      out.printf( 
         "[Solve]␣Chips:␣%d␣=␣%s␣=␣%s%n", 
         fibonacciBaseNumber.getValue(), 
         String.join("␣+␣", fibonacciBaseNumber.stream() 
            .map(f -> String.format("F_%d", f.getIndex())).collect(Collectors.toList()) 
         ), 
         String.join("␣+␣", fibonacciBaseNumber.stream() 
               .map(f -> Integer.toString(f.getValue())).collect(Collectors.toList()) 
         ) 
      ); 
      out.printf( 
         "[Solve]␣Optimal:␣%d;␣Possible:␣{%s}%n", 
         getOptimalNumberOfChipsToTake(), 
         String.join(",␣", numberOfChipsToTake.stream() 
               .map(t -> Integer.toString(t)).collect(Collectors.toList()) 
         ) 
      ); 
   } 
 
   private FibonacciBaseNumber fibonacciBaseNumber; 
   private  SortedSet<Integer> numberOfChipsToTake = new TreeSet<Integer>(); 
 
} 
 
Options options = new Options(arguments); 
State state = new State(options.getNumberOfChips(), options.isUserFirst()); 
FibonacciNumbers fibonacciNumbers = new FibonacciNumbers(); 
state.writePreSummary(System.out); 
do { 
   Solver solver = new Solver(fibonacciNumbers, state); 
   state.writeSummary(System.out); 
   solver.writeSummary(System.out); 
   int numberOfChipsTaken; 
   if (state.isUserTurn()) { 
      System.out.printf("[Input]␣User␣Takes:␣"); 
      numberOfChipsTaken = options.readNumberOfChipsTaken(System.in, state.getNumberOfChipsTakeable()); 
   } else { 
      System.out.printf("[Input]␣Computer␣Takes:␣"); 
      numberOfChipsTaken = solver.getOptimalNumberOfChipsToTake(); 
      System.out.printf("%d%n", numberOfChipsTaken); 
   } 
   state.take(numberOfChipsTaken); 
} while (state.getNumberOfChips() > 0); 
state.writePostSummary(System.out);

Sample output for a game starting with 1000 chips where the computer went first (-n 1000 -p 2), lasting for 351 turns, is shown below.

Number of Chips: 1000 
     Goes First: Computer 
--------------- 
[State] Turn: 1 (Computer); Chips: 1000; Takeable: 999 
[Solve] Chips: 1000 = F_16 + F_7 = 987 + 13 
[Solve] Optimal: 13; Possible: {13} 
[Input] Computer Takes: 13 
[State] Turn: 2 (User); Chips: 987; Takeable: 26 
[Solve] Chips: 987 = F_16 = 987 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 26 
[State] Turn: 3 (Computer); Chips: 961; Takeable: 52 
[Solve] Chips: 961 = F_15 + F_13 + F_11 + F_8 + F_6 = 610 + 233 + 89 + 21 + 8 
[Solve] Optimal: 8; Possible: {8, 29} 
[Input] Computer Takes: 8 
[State] Turn: 4 (User); Chips: 953; Takeable: 16 
[Solve] Chips: 953 = F_15 + F_13 + F_11 + F_8 = 610 + 233 + 89 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 16 
[State] Turn: 5 (Computer); Chips: 937; Takeable: 32 
[Solve] Chips: 937 = F_15 + F_13 + F_11 + F_5 = 610 + 233 + 89 + 5 
[Solve] Optimal: 5; Possible: {5} 
[Input] Computer Takes: 5 
[State] Turn: 6 (User); Chips: 932; Takeable: 10 
[Solve] Chips: 932 = F_15 + F_13 + F_11 = 610 + 233 + 89 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 10 
[State] Turn: 7 (Computer); Chips: 922; Takeable: 20 
[Solve] Chips: 922 = F_15 + F_13 + F_10 + F_8 + F_4 = 610 + 233 + 55 + 21 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 8 (User); Chips: 919; Takeable: 6 
[Solve] Chips: 919 = F_15 + F_13 + F_10 + F_8 = 610 + 233 + 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 9 (Computer); Chips: 913; Takeable: 12 
[Solve] Chips: 913 = F_15 + F_13 + F_10 + F_7 + F_3 = 610 + 233 + 55 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 10 (User); Chips: 911; Takeable: 4 
[Solve] Chips: 911 = F_15 + F_13 + F_10 + F_7 = 610 + 233 + 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 11 (Computer); Chips: 907; Takeable: 8 
[Solve] Chips: 907 = F_15 + F_13 + F_10 + F_6 + F_2 = 610 + 233 + 55 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 12 (User); Chips: 906; Takeable: 2 
[Solve] Chips: 906 = F_15 + F_13 + F_10 + F_6 = 610 + 233 + 55 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 13 (Computer); Chips: 904; Takeable: 4 
[Solve] Chips: 904 = F_15 + F_13 + F_10 + F_5 + F_2 = 610 + 233 + 55 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 14 (User); Chips: 903; Takeable: 2 
[Solve] Chips: 903 = F_15 + F_13 + F_10 + F_5 = 610 + 233 + 55 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 15 (Computer); Chips: 901; Takeable: 4 
[Solve] Chips: 901 = F_15 + F_13 + F_10 + F_4 = 610 + 233 + 55 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 16 (User); Chips: 898; Takeable: 6 
[Solve] Chips: 898 = F_15 + F_13 + F_10 = 610 + 233 + 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 17 (Computer); Chips: 892; Takeable: 12 
[Solve] Chips: 892 = F_15 + F_13 + F_9 + F_7 + F_3 = 610 + 233 + 34 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 18 (User); Chips: 890; Takeable: 4 
[Solve] Chips: 890 = F_15 + F_13 + F_9 + F_7 = 610 + 233 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 19 (Computer); Chips: 886; Takeable: 8 
[Solve] Chips: 886 = F_15 + F_13 + F_9 + F_6 + F_2 = 610 + 233 + 34 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 20 (User); Chips: 885; Takeable: 2 
[Solve] Chips: 885 = F_15 + F_13 + F_9 + F_6 = 610 + 233 + 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 21 (Computer); Chips: 883; Takeable: 4 
[Solve] Chips: 883 = F_15 + F_13 + F_9 + F_5 + F_2 = 610 + 233 + 34 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 22 (User); Chips: 882; Takeable: 2 
[Solve] Chips: 882 = F_15 + F_13 + F_9 + F_5 = 610 + 233 + 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 23 (Computer); Chips: 880; Takeable: 4 
[Solve] Chips: 880 = F_15 + F_13 + F_9 + F_4 = 610 + 233 + 34 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 24 (User); Chips: 877; Takeable: 6 
[Solve] Chips: 877 = F_15 + F_13 + F_9 = 610 + 233 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 25 (Computer); Chips: 871; Takeable: 12 
[Solve] Chips: 871 = F_15 + F_13 + F_8 + F_5 + F_3 = 610 + 233 + 21 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 26 (User); Chips: 869; Takeable: 4 
[Solve] Chips: 869 = F_15 + F_13 + F_8 + F_5 = 610 + 233 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 27 (Computer); Chips: 865; Takeable: 8 
[Solve] Chips: 865 = F_15 + F_13 + F_8 + F_2 = 610 + 233 + 21 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 28 (User); Chips: 864; Takeable: 2 
[Solve] Chips: 864 = F_15 + F_13 + F_8 = 610 + 233 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 29 (Computer); Chips: 862; Takeable: 4 
[Solve] Chips: 862 = F_15 + F_13 + F_7 + F_5 + F_2 = 610 + 233 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 30 (User); Chips: 861; Takeable: 2 
[Solve] Chips: 861 = F_15 + F_13 + F_7 + F_5 = 610 + 233 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 31 (Computer); Chips: 859; Takeable: 4 
[Solve] Chips: 859 = F_15 + F_13 + F_7 + F_4 = 610 + 233 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 32 (User); Chips: 856; Takeable: 6 
[Solve] Chips: 856 = F_15 + F_13 + F_7 = 610 + 233 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 33 (Computer); Chips: 850; Takeable: 12 
[Solve] Chips: 850 = F_15 + F_13 + F_5 + F_3 = 610 + 233 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 34 (User); Chips: 848; Takeable: 4 
[Solve] Chips: 848 = F_15 + F_13 + F_5 = 610 + 233 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 35 (Computer); Chips: 844; Takeable: 8 
[Solve] Chips: 844 = F_15 + F_13 + F_2 = 610 + 233 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 36 (User); Chips: 843; Takeable: 2 
[Solve] Chips: 843 = F_15 + F_13 = 610 + 233 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 37 (Computer); Chips: 841; Takeable: 4 
[Solve] Chips: 841 = F_15 + F_12 + F_10 + F_8 + F_6 + F_4 = 610 + 144 + 55 + 21 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 38 (User); Chips: 838; Takeable: 6 
[Solve] Chips: 838 = F_15 + F_12 + F_10 + F_8 + F_6 = 610 + 144 + 55 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 39 (Computer); Chips: 832; Takeable: 12 
[Solve] Chips: 832 = F_15 + F_12 + F_10 + F_8 + F_3 = 610 + 144 + 55 + 21 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 40 (User); Chips: 830; Takeable: 4 
[Solve] Chips: 830 = F_15 + F_12 + F_10 + F_8 = 610 + 144 + 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 41 (Computer); Chips: 826; Takeable: 8 
[Solve] Chips: 826 = F_15 + F_12 + F_10 + F_7 + F_4 + F_2 = 610 + 144 + 55 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 42 (User); Chips: 825; Takeable: 2 
[Solve] Chips: 825 = F_15 + F_12 + F_10 + F_7 + F_4 = 610 + 144 + 55 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 43 (Computer); Chips: 823; Takeable: 4 
[Solve] Chips: 823 = F_15 + F_12 + F_10 + F_7 + F_2 = 610 + 144 + 55 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 44 (User); Chips: 822; Takeable: 2 
[Solve] Chips: 822 = F_15 + F_12 + F_10 + F_7 = 610 + 144 + 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 45 (Computer); Chips: 820; Takeable: 4 
[Solve] Chips: 820 = F_15 + F_12 + F_10 + F_6 + F_4 = 610 + 144 + 55 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 46 (User); Chips: 817; Takeable: 6 
[Solve] Chips: 817 = F_15 + F_12 + F_10 + F_6 = 610 + 144 + 55 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 47 (Computer); Chips: 811; Takeable: 12 
[Solve] Chips: 811 = F_15 + F_12 + F_10 + F_3 = 610 + 144 + 55 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 48 (User); Chips: 809; Takeable: 4 
[Solve] Chips: 809 = F_15 + F_12 + F_10 = 610 + 144 + 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 49 (Computer); Chips: 805; Takeable: 8 
[Solve] Chips: 805 = F_15 + F_12 + F_9 + F_7 + F_4 + F_2 = 610 + 144 + 34 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 50 (User); Chips: 804; Takeable: 2 
[Solve] Chips: 804 = F_15 + F_12 + F_9 + F_7 + F_4 = 610 + 144 + 34 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 51 (Computer); Chips: 802; Takeable: 4 
[Solve] Chips: 802 = F_15 + F_12 + F_9 + F_7 + F_2 = 610 + 144 + 34 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 52 (User); Chips: 801; Takeable: 2 
[Solve] Chips: 801 = F_15 + F_12 + F_9 + F_7 = 610 + 144 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 53 (Computer); Chips: 799; Takeable: 4 
[Solve] Chips: 799 = F_15 + F_12 + F_9 + F_6 + F_4 = 610 + 144 + 34 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 54 (User); Chips: 796; Takeable: 6 
[Solve] Chips: 796 = F_15 + F_12 + F_9 + F_6 = 610 + 144 + 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 55 (Computer); Chips: 790; Takeable: 12 
[Solve] Chips: 790 = F_15 + F_12 + F_9 + F_3 = 610 + 144 + 34 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 56 (User); Chips: 788; Takeable: 4 
[Solve] Chips: 788 = F_15 + F_12 + F_9 = 610 + 144 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 57 (Computer); Chips: 784; Takeable: 8 
[Solve] Chips: 784 = F_15 + F_12 + F_8 + F_6 + F_2 = 610 + 144 + 21 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 58 (User); Chips: 783; Takeable: 2 
[Solve] Chips: 783 = F_15 + F_12 + F_8 + F_6 = 610 + 144 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 59 (Computer); Chips: 781; Takeable: 4 
[Solve] Chips: 781 = F_15 + F_12 + F_8 + F_5 + F_2 = 610 + 144 + 21 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 60 (User); Chips: 780; Takeable: 2 
[Solve] Chips: 780 = F_15 + F_12 + F_8 + F_5 = 610 + 144 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 61 (Computer); Chips: 778; Takeable: 4 
[Solve] Chips: 778 = F_15 + F_12 + F_8 + F_4 = 610 + 144 + 21 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 62 (User); Chips: 775; Takeable: 6 
[Solve] Chips: 775 = F_15 + F_12 + F_8 = 610 + 144 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 63 (Computer); Chips: 769; Takeable: 12 
[Solve] Chips: 769 = F_15 + F_12 + F_7 + F_3 = 610 + 144 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 64 (User); Chips: 767; Takeable: 4 
[Solve] Chips: 767 = F_15 + F_12 + F_7 = 610 + 144 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 65 (Computer); Chips: 763; Takeable: 8 
[Solve] Chips: 763 = F_15 + F_12 + F_6 + F_2 = 610 + 144 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 66 (User); Chips: 762; Takeable: 2 
[Solve] Chips: 762 = F_15 + F_12 + F_6 = 610 + 144 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 67 (Computer); Chips: 760; Takeable: 4 
[Solve] Chips: 760 = F_15 + F_12 + F_5 + F_2 = 610 + 144 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 68 (User); Chips: 759; Takeable: 2 
[Solve] Chips: 759 = F_15 + F_12 + F_5 = 610 + 144 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 69 (Computer); Chips: 757; Takeable: 4 
[Solve] Chips: 757 = F_15 + F_12 + F_4 = 610 + 144 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 70 (User); Chips: 754; Takeable: 6 
[Solve] Chips: 754 = F_15 + F_12 = 610 + 144 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 71 (Computer); Chips: 748; Takeable: 12 
[Solve] Chips: 748 = F_15 + F_11 + F_9 + F_7 + F_3 = 610 + 89 + 34 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 72 (User); Chips: 746; Takeable: 4 
[Solve] Chips: 746 = F_15 + F_11 + F_9 + F_7 = 610 + 89 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 73 (Computer); Chips: 742; Takeable: 8 
[Solve] Chips: 742 = F_15 + F_11 + F_9 + F_6 + F_2 = 610 + 89 + 34 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 74 (User); Chips: 741; Takeable: 2 
[Solve] Chips: 741 = F_15 + F_11 + F_9 + F_6 = 610 + 89 + 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 75 (Computer); Chips: 739; Takeable: 4 
[Solve] Chips: 739 = F_15 + F_11 + F_9 + F_5 + F_2 = 610 + 89 + 34 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 76 (User); Chips: 738; Takeable: 2 
[Solve] Chips: 738 = F_15 + F_11 + F_9 + F_5 = 610 + 89 + 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 77 (Computer); Chips: 736; Takeable: 4 
[Solve] Chips: 736 = F_15 + F_11 + F_9 + F_4 = 610 + 89 + 34 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 78 (User); Chips: 733; Takeable: 6 
[Solve] Chips: 733 = F_15 + F_11 + F_9 = 610 + 89 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 79 (Computer); Chips: 727; Takeable: 12 
[Solve] Chips: 727 = F_15 + F_11 + F_8 + F_5 + F_3 = 610 + 89 + 21 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 80 (User); Chips: 725; Takeable: 4 
[Solve] Chips: 725 = F_15 + F_11 + F_8 + F_5 = 610 + 89 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 81 (Computer); Chips: 721; Takeable: 8 
[Solve] Chips: 721 = F_15 + F_11 + F_8 + F_2 = 610 + 89 + 21 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 82 (User); Chips: 720; Takeable: 2 
[Solve] Chips: 720 = F_15 + F_11 + F_8 = 610 + 89 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 83 (Computer); Chips: 718; Takeable: 4 
[Solve] Chips: 718 = F_15 + F_11 + F_7 + F_5 + F_2 = 610 + 89 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 84 (User); Chips: 717; Takeable: 2 
[Solve] Chips: 717 = F_15 + F_11 + F_7 + F_5 = 610 + 89 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 85 (Computer); Chips: 715; Takeable: 4 
[Solve] Chips: 715 = F_15 + F_11 + F_7 + F_4 = 610 + 89 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 86 (User); Chips: 712; Takeable: 6 
[Solve] Chips: 712 = F_15 + F_11 + F_7 = 610 + 89 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 87 (Computer); Chips: 706; Takeable: 12 
[Solve] Chips: 706 = F_15 + F_11 + F_5 + F_3 = 610 + 89 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 88 (User); Chips: 704; Takeable: 4 
[Solve] Chips: 704 = F_15 + F_11 + F_5 = 610 + 89 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 89 (Computer); Chips: 700; Takeable: 8 
[Solve] Chips: 700 = F_15 + F_11 + F_2 = 610 + 89 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 90 (User); Chips: 699; Takeable: 2 
[Solve] Chips: 699 = F_15 + F_11 = 610 + 89 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 91 (Computer); Chips: 697; Takeable: 4 
[Solve] Chips: 697 = F_15 + F_10 + F_8 + F_6 + F_4 = 610 + 55 + 21 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 92 (User); Chips: 694; Takeable: 6 
[Solve] Chips: 694 = F_15 + F_10 + F_8 + F_6 = 610 + 55 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 93 (Computer); Chips: 688; Takeable: 12 
[Solve] Chips: 688 = F_15 + F_10 + F_8 + F_3 = 610 + 55 + 21 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 94 (User); Chips: 686; Takeable: 4 
[Solve] Chips: 686 = F_15 + F_10 + F_8 = 610 + 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 95 (Computer); Chips: 682; Takeable: 8 
[Solve] Chips: 682 = F_15 + F_10 + F_7 + F_4 + F_2 = 610 + 55 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 96 (User); Chips: 681; Takeable: 2 
[Solve] Chips: 681 = F_15 + F_10 + F_7 + F_4 = 610 + 55 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 97 (Computer); Chips: 679; Takeable: 4 
[Solve] Chips: 679 = F_15 + F_10 + F_7 + F_2 = 610 + 55 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 98 (User); Chips: 678; Takeable: 2 
[Solve] Chips: 678 = F_15 + F_10 + F_7 = 610 + 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 99 (Computer); Chips: 676; Takeable: 4 
[Solve] Chips: 676 = F_15 + F_10 + F_6 + F_4 = 610 + 55 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 100 (User); Chips: 673; Takeable: 6 
[Solve] Chips: 673 = F_15 + F_10 + F_6 = 610 + 55 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 101 (Computer); Chips: 667; Takeable: 12 
[Solve] Chips: 667 = F_15 + F_10 + F_3 = 610 + 55 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 102 (User); Chips: 665; Takeable: 4 
[Solve] Chips: 665 = F_15 + F_10 = 610 + 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 103 (Computer); Chips: 661; Takeable: 8 
[Solve] Chips: 661 = F_15 + F_9 + F_7 + F_4 + F_2 = 610 + 34 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 104 (User); Chips: 660; Takeable: 2 
[Solve] Chips: 660 = F_15 + F_9 + F_7 + F_4 = 610 + 34 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 105 (Computer); Chips: 658; Takeable: 4 
[Solve] Chips: 658 = F_15 + F_9 + F_7 + F_2 = 610 + 34 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 106 (User); Chips: 657; Takeable: 2 
[Solve] Chips: 657 = F_15 + F_9 + F_7 = 610 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 107 (Computer); Chips: 655; Takeable: 4 
[Solve] Chips: 655 = F_15 + F_9 + F_6 + F_4 = 610 + 34 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 108 (User); Chips: 652; Takeable: 6 
[Solve] Chips: 652 = F_15 + F_9 + F_6 = 610 + 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 109 (Computer); Chips: 646; Takeable: 12 
[Solve] Chips: 646 = F_15 + F_9 + F_3 = 610 + 34 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 110 (User); Chips: 644; Takeable: 4 
[Solve] Chips: 644 = F_15 + F_9 = 610 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 111 (Computer); Chips: 640; Takeable: 8 
[Solve] Chips: 640 = F_15 + F_8 + F_6 + F_2 = 610 + 21 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 112 (User); Chips: 639; Takeable: 2 
[Solve] Chips: 639 = F_15 + F_8 + F_6 = 610 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 113 (Computer); Chips: 637; Takeable: 4 
[Solve] Chips: 637 = F_15 + F_8 + F_5 + F_2 = 610 + 21 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 114 (User); Chips: 636; Takeable: 2 
[Solve] Chips: 636 = F_15 + F_8 + F_5 = 610 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 115 (Computer); Chips: 634; Takeable: 4 
[Solve] Chips: 634 = F_15 + F_8 + F_4 = 610 + 21 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 116 (User); Chips: 631; Takeable: 6 
[Solve] Chips: 631 = F_15 + F_8 = 610 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 117 (Computer); Chips: 625; Takeable: 12 
[Solve] Chips: 625 = F_15 + F_7 + F_3 = 610 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 118 (User); Chips: 623; Takeable: 4 
[Solve] Chips: 623 = F_15 + F_7 = 610 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 119 (Computer); Chips: 619; Takeable: 8 
[Solve] Chips: 619 = F_15 + F_6 + F_2 = 610 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 120 (User); Chips: 618; Takeable: 2 
[Solve] Chips: 618 = F_15 + F_6 = 610 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 121 (Computer); Chips: 616; Takeable: 4 
[Solve] Chips: 616 = F_15 + F_5 + F_2 = 610 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 122 (User); Chips: 615; Takeable: 2 
[Solve] Chips: 615 = F_15 + F_5 = 610 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 123 (Computer); Chips: 613; Takeable: 4 
[Solve] Chips: 613 = F_15 + F_4 = 610 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 124 (User); Chips: 610; Takeable: 6 
[Solve] Chips: 610 = F_15 = 610 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 125 (Computer); Chips: 604; Takeable: 12 
[Solve] Chips: 604 = F_14 + F_12 + F_10 + F_8 + F_5 + F_3 = 377 + 144 + 55 + 21 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 126 (User); Chips: 602; Takeable: 4 
[Solve] Chips: 602 = F_14 + F_12 + F_10 + F_8 + F_5 = 377 + 144 + 55 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 127 (Computer); Chips: 598; Takeable: 8 
[Solve] Chips: 598 = F_14 + F_12 + F_10 + F_8 + F_2 = 377 + 144 + 55 + 21 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 128 (User); Chips: 597; Takeable: 2 
[Solve] Chips: 597 = F_14 + F_12 + F_10 + F_8 = 377 + 144 + 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 129 (Computer); Chips: 595; Takeable: 4 
[Solve] Chips: 595 = F_14 + F_12 + F_10 + F_7 + F_5 + F_2 = 377 + 144 + 55 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 130 (User); Chips: 594; Takeable: 2 
[Solve] Chips: 594 = F_14 + F_12 + F_10 + F_7 + F_5 = 377 + 144 + 55 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 131 (Computer); Chips: 592; Takeable: 4 
[Solve] Chips: 592 = F_14 + F_12 + F_10 + F_7 + F_4 = 377 + 144 + 55 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 132 (User); Chips: 589; Takeable: 6 
[Solve] Chips: 589 = F_14 + F_12 + F_10 + F_7 = 377 + 144 + 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 133 (Computer); Chips: 583; Takeable: 12 
[Solve] Chips: 583 = F_14 + F_12 + F_10 + F_5 + F_3 = 377 + 144 + 55 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 134 (User); Chips: 581; Takeable: 4 
[Solve] Chips: 581 = F_14 + F_12 + F_10 + F_5 = 377 + 144 + 55 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 135 (Computer); Chips: 577; Takeable: 8 
[Solve] Chips: 577 = F_14 + F_12 + F_10 + F_2 = 377 + 144 + 55 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 136 (User); Chips: 576; Takeable: 2 
[Solve] Chips: 576 = F_14 + F_12 + F_10 = 377 + 144 + 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 137 (Computer); Chips: 574; Takeable: 4 
[Solve] Chips: 574 = F_14 + F_12 + F_9 + F_7 + F_5 + F_2 = 377 + 144 + 34 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 138 (User); Chips: 573; Takeable: 2 
[Solve] Chips: 573 = F_14 + F_12 + F_9 + F_7 + F_5 = 377 + 144 + 34 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 139 (Computer); Chips: 571; Takeable: 4 
[Solve] Chips: 571 = F_14 + F_12 + F_9 + F_7 + F_4 = 377 + 144 + 34 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 140 (User); Chips: 568; Takeable: 6 
[Solve] Chips: 568 = F_14 + F_12 + F_9 + F_7 = 377 + 144 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 141 (Computer); Chips: 562; Takeable: 12 
[Solve] Chips: 562 = F_14 + F_12 + F_9 + F_5 + F_3 = 377 + 144 + 34 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 142 (User); Chips: 560; Takeable: 4 
[Solve] Chips: 560 = F_14 + F_12 + F_9 + F_5 = 377 + 144 + 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 143 (Computer); Chips: 556; Takeable: 8 
[Solve] Chips: 556 = F_14 + F_12 + F_9 + F_2 = 377 + 144 + 34 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 144 (User); Chips: 555; Takeable: 2 
[Solve] Chips: 555 = F_14 + F_12 + F_9 = 377 + 144 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 145 (Computer); Chips: 553; Takeable: 4 
[Solve] Chips: 553 = F_14 + F_12 + F_8 + F_6 + F_4 = 377 + 144 + 21 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 146 (User); Chips: 550; Takeable: 6 
[Solve] Chips: 550 = F_14 + F_12 + F_8 + F_6 = 377 + 144 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 147 (Computer); Chips: 544; Takeable: 12 
[Solve] Chips: 544 = F_14 + F_12 + F_8 + F_3 = 377 + 144 + 21 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 148 (User); Chips: 542; Takeable: 4 
[Solve] Chips: 542 = F_14 + F_12 + F_8 = 377 + 144 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 149 (Computer); Chips: 538; Takeable: 8 
[Solve] Chips: 538 = F_14 + F_12 + F_7 + F_4 + F_2 = 377 + 144 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 150 (User); Chips: 537; Takeable: 2 
[Solve] Chips: 537 = F_14 + F_12 + F_7 + F_4 = 377 + 144 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 151 (Computer); Chips: 535; Takeable: 4 
[Solve] Chips: 535 = F_14 + F_12 + F_7 + F_2 = 377 + 144 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 152 (User); Chips: 534; Takeable: 2 
[Solve] Chips: 534 = F_14 + F_12 + F_7 = 377 + 144 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 153 (Computer); Chips: 532; Takeable: 4 
[Solve] Chips: 532 = F_14 + F_12 + F_6 + F_4 = 377 + 144 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 154 (User); Chips: 529; Takeable: 6 
[Solve] Chips: 529 = F_14 + F_12 + F_6 = 377 + 144 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 155 (Computer); Chips: 523; Takeable: 12 
[Solve] Chips: 523 = F_14 + F_12 + F_3 = 377 + 144 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 156 (User); Chips: 521; Takeable: 4 
[Solve] Chips: 521 = F_14 + F_12 = 377 + 144 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 157 (Computer); Chips: 517; Takeable: 8 
[Solve] Chips: 517 = F_14 + F_11 + F_9 + F_7 + F_4 + F_2 = 377 + 89 + 34 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 158 (User); Chips: 516; Takeable: 2 
[Solve] Chips: 516 = F_14 + F_11 + F_9 + F_7 + F_4 = 377 + 89 + 34 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 159 (Computer); Chips: 514; Takeable: 4 
[Solve] Chips: 514 = F_14 + F_11 + F_9 + F_7 + F_2 = 377 + 89 + 34 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 160 (User); Chips: 513; Takeable: 2 
[Solve] Chips: 513 = F_14 + F_11 + F_9 + F_7 = 377 + 89 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 161 (Computer); Chips: 511; Takeable: 4 
[Solve] Chips: 511 = F_14 + F_11 + F_9 + F_6 + F_4 = 377 + 89 + 34 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 162 (User); Chips: 508; Takeable: 6 
[Solve] Chips: 508 = F_14 + F_11 + F_9 + F_6 = 377 + 89 + 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 163 (Computer); Chips: 502; Takeable: 12 
[Solve] Chips: 502 = F_14 + F_11 + F_9 + F_3 = 377 + 89 + 34 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 164 (User); Chips: 500; Takeable: 4 
[Solve] Chips: 500 = F_14 + F_11 + F_9 = 377 + 89 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 165 (Computer); Chips: 496; Takeable: 8 
[Solve] Chips: 496 = F_14 + F_11 + F_8 + F_6 + F_2 = 377 + 89 + 21 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 166 (User); Chips: 495; Takeable: 2 
[Solve] Chips: 495 = F_14 + F_11 + F_8 + F_6 = 377 + 89 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 167 (Computer); Chips: 493; Takeable: 4 
[Solve] Chips: 493 = F_14 + F_11 + F_8 + F_5 + F_2 = 377 + 89 + 21 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 168 (User); Chips: 492; Takeable: 2 
[Solve] Chips: 492 = F_14 + F_11 + F_8 + F_5 = 377 + 89 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 169 (Computer); Chips: 490; Takeable: 4 
[Solve] Chips: 490 = F_14 + F_11 + F_8 + F_4 = 377 + 89 + 21 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 170 (User); Chips: 487; Takeable: 6 
[Solve] Chips: 487 = F_14 + F_11 + F_8 = 377 + 89 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 171 (Computer); Chips: 481; Takeable: 12 
[Solve] Chips: 481 = F_14 + F_11 + F_7 + F_3 = 377 + 89 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 172 (User); Chips: 479; Takeable: 4 
[Solve] Chips: 479 = F_14 + F_11 + F_7 = 377 + 89 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 173 (Computer); Chips: 475; Takeable: 8 
[Solve] Chips: 475 = F_14 + F_11 + F_6 + F_2 = 377 + 89 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 174 (User); Chips: 474; Takeable: 2 
[Solve] Chips: 474 = F_14 + F_11 + F_6 = 377 + 89 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 175 (Computer); Chips: 472; Takeable: 4 
[Solve] Chips: 472 = F_14 + F_11 + F_5 + F_2 = 377 + 89 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 176 (User); Chips: 471; Takeable: 2 
[Solve] Chips: 471 = F_14 + F_11 + F_5 = 377 + 89 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 177 (Computer); Chips: 469; Takeable: 4 
[Solve] Chips: 469 = F_14 + F_11 + F_4 = 377 + 89 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 178 (User); Chips: 466; Takeable: 6 
[Solve] Chips: 466 = F_14 + F_11 = 377 + 89 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 179 (Computer); Chips: 460; Takeable: 12 
[Solve] Chips: 460 = F_14 + F_10 + F_8 + F_5 + F_3 = 377 + 55 + 21 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 180 (User); Chips: 458; Takeable: 4 
[Solve] Chips: 458 = F_14 + F_10 + F_8 + F_5 = 377 + 55 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 181 (Computer); Chips: 454; Takeable: 8 
[Solve] Chips: 454 = F_14 + F_10 + F_8 + F_2 = 377 + 55 + 21 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 182 (User); Chips: 453; Takeable: 2 
[Solve] Chips: 453 = F_14 + F_10 + F_8 = 377 + 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 183 (Computer); Chips: 451; Takeable: 4 
[Solve] Chips: 451 = F_14 + F_10 + F_7 + F_5 + F_2 = 377 + 55 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 184 (User); Chips: 450; Takeable: 2 
[Solve] Chips: 450 = F_14 + F_10 + F_7 + F_5 = 377 + 55 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 185 (Computer); Chips: 448; Takeable: 4 
[Solve] Chips: 448 = F_14 + F_10 + F_7 + F_4 = 377 + 55 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 186 (User); Chips: 445; Takeable: 6 
[Solve] Chips: 445 = F_14 + F_10 + F_7 = 377 + 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 187 (Computer); Chips: 439; Takeable: 12 
[Solve] Chips: 439 = F_14 + F_10 + F_5 + F_3 = 377 + 55 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 188 (User); Chips: 437; Takeable: 4 
[Solve] Chips: 437 = F_14 + F_10 + F_5 = 377 + 55 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 189 (Computer); Chips: 433; Takeable: 8 
[Solve] Chips: 433 = F_14 + F_10 + F_2 = 377 + 55 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 190 (User); Chips: 432; Takeable: 2 
[Solve] Chips: 432 = F_14 + F_10 = 377 + 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 191 (Computer); Chips: 430; Takeable: 4 
[Solve] Chips: 430 = F_14 + F_9 + F_7 + F_5 + F_2 = 377 + 34 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 192 (User); Chips: 429; Takeable: 2 
[Solve] Chips: 429 = F_14 + F_9 + F_7 + F_5 = 377 + 34 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 193 (Computer); Chips: 427; Takeable: 4 
[Solve] Chips: 427 = F_14 + F_9 + F_7 + F_4 = 377 + 34 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 194 (User); Chips: 424; Takeable: 6 
[Solve] Chips: 424 = F_14 + F_9 + F_7 = 377 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 195 (Computer); Chips: 418; Takeable: 12 
[Solve] Chips: 418 = F_14 + F_9 + F_5 + F_3 = 377 + 34 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 196 (User); Chips: 416; Takeable: 4 
[Solve] Chips: 416 = F_14 + F_9 + F_5 = 377 + 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 197 (Computer); Chips: 412; Takeable: 8 
[Solve] Chips: 412 = F_14 + F_9 + F_2 = 377 + 34 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 198 (User); Chips: 411; Takeable: 2 
[Solve] Chips: 411 = F_14 + F_9 = 377 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 199 (Computer); Chips: 409; Takeable: 4 
[Solve] Chips: 409 = F_14 + F_8 + F_6 + F_4 = 377 + 21 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 200 (User); Chips: 406; Takeable: 6 
[Solve] Chips: 406 = F_14 + F_8 + F_6 = 377 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 201 (Computer); Chips: 400; Takeable: 12 
[Solve] Chips: 400 = F_14 + F_8 + F_3 = 377 + 21 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 202 (User); Chips: 398; Takeable: 4 
[Solve] Chips: 398 = F_14 + F_8 = 377 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 203 (Computer); Chips: 394; Takeable: 8 
[Solve] Chips: 394 = F_14 + F_7 + F_4 + F_2 = 377 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 204 (User); Chips: 393; Takeable: 2 
[Solve] Chips: 393 = F_14 + F_7 + F_4 = 377 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 205 (Computer); Chips: 391; Takeable: 4 
[Solve] Chips: 391 = F_14 + F_7 + F_2 = 377 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 206 (User); Chips: 390; Takeable: 2 
[Solve] Chips: 390 = F_14 + F_7 = 377 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 207 (Computer); Chips: 388; Takeable: 4 
[Solve] Chips: 388 = F_14 + F_6 + F_4 = 377 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 208 (User); Chips: 385; Takeable: 6 
[Solve] Chips: 385 = F_14 + F_6 = 377 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 209 (Computer); Chips: 379; Takeable: 12 
[Solve] Chips: 379 = F_14 + F_3 = 377 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 210 (User); Chips: 377; Takeable: 4 
[Solve] Chips: 377 = F_14 = 377 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 211 (Computer); Chips: 373; Takeable: 8 
[Solve] Chips: 373 = F_13 + F_11 + F_9 + F_7 + F_4 + F_2 = 233 + 89 + 34 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 212 (User); Chips: 372; Takeable: 2 
[Solve] Chips: 372 = F_13 + F_11 + F_9 + F_7 + F_4 = 233 + 89 + 34 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 213 (Computer); Chips: 370; Takeable: 4 
[Solve] Chips: 370 = F_13 + F_11 + F_9 + F_7 + F_2 = 233 + 89 + 34 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 214 (User); Chips: 369; Takeable: 2 
[Solve] Chips: 369 = F_13 + F_11 + F_9 + F_7 = 233 + 89 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 215 (Computer); Chips: 367; Takeable: 4 
[Solve] Chips: 367 = F_13 + F_11 + F_9 + F_6 + F_4 = 233 + 89 + 34 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 216 (User); Chips: 364; Takeable: 6 
[Solve] Chips: 364 = F_13 + F_11 + F_9 + F_6 = 233 + 89 + 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 217 (Computer); Chips: 358; Takeable: 12 
[Solve] Chips: 358 = F_13 + F_11 + F_9 + F_3 = 233 + 89 + 34 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 218 (User); Chips: 356; Takeable: 4 
[Solve] Chips: 356 = F_13 + F_11 + F_9 = 233 + 89 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 219 (Computer); Chips: 352; Takeable: 8 
[Solve] Chips: 352 = F_13 + F_11 + F_8 + F_6 + F_2 = 233 + 89 + 21 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 220 (User); Chips: 351; Takeable: 2 
[Solve] Chips: 351 = F_13 + F_11 + F_8 + F_6 = 233 + 89 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 221 (Computer); Chips: 349; Takeable: 4 
[Solve] Chips: 349 = F_13 + F_11 + F_8 + F_5 + F_2 = 233 + 89 + 21 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 222 (User); Chips: 348; Takeable: 2 
[Solve] Chips: 348 = F_13 + F_11 + F_8 + F_5 = 233 + 89 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 223 (Computer); Chips: 346; Takeable: 4 
[Solve] Chips: 346 = F_13 + F_11 + F_8 + F_4 = 233 + 89 + 21 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 224 (User); Chips: 343; Takeable: 6 
[Solve] Chips: 343 = F_13 + F_11 + F_8 = 233 + 89 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 225 (Computer); Chips: 337; Takeable: 12 
[Solve] Chips: 337 = F_13 + F_11 + F_7 + F_3 = 233 + 89 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 226 (User); Chips: 335; Takeable: 4 
[Solve] Chips: 335 = F_13 + F_11 + F_7 = 233 + 89 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 227 (Computer); Chips: 331; Takeable: 8 
[Solve] Chips: 331 = F_13 + F_11 + F_6 + F_2 = 233 + 89 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 228 (User); Chips: 330; Takeable: 2 
[Solve] Chips: 330 = F_13 + F_11 + F_6 = 233 + 89 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 229 (Computer); Chips: 328; Takeable: 4 
[Solve] Chips: 328 = F_13 + F_11 + F_5 + F_2 = 233 + 89 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 230 (User); Chips: 327; Takeable: 2 
[Solve] Chips: 327 = F_13 + F_11 + F_5 = 233 + 89 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 231 (Computer); Chips: 325; Takeable: 4 
[Solve] Chips: 325 = F_13 + F_11 + F_4 = 233 + 89 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 232 (User); Chips: 322; Takeable: 6 
[Solve] Chips: 322 = F_13 + F_11 = 233 + 89 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 233 (Computer); Chips: 316; Takeable: 12 
[Solve] Chips: 316 = F_13 + F_10 + F_8 + F_5 + F_3 = 233 + 55 + 21 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 234 (User); Chips: 314; Takeable: 4 
[Solve] Chips: 314 = F_13 + F_10 + F_8 + F_5 = 233 + 55 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 235 (Computer); Chips: 310; Takeable: 8 
[Solve] Chips: 310 = F_13 + F_10 + F_8 + F_2 = 233 + 55 + 21 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 236 (User); Chips: 309; Takeable: 2 
[Solve] Chips: 309 = F_13 + F_10 + F_8 = 233 + 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 237 (Computer); Chips: 307; Takeable: 4 
[Solve] Chips: 307 = F_13 + F_10 + F_7 + F_5 + F_2 = 233 + 55 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 238 (User); Chips: 306; Takeable: 2 
[Solve] Chips: 306 = F_13 + F_10 + F_7 + F_5 = 233 + 55 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 239 (Computer); Chips: 304; Takeable: 4 
[Solve] Chips: 304 = F_13 + F_10 + F_7 + F_4 = 233 + 55 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 240 (User); Chips: 301; Takeable: 6 
[Solve] Chips: 301 = F_13 + F_10 + F_7 = 233 + 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 241 (Computer); Chips: 295; Takeable: 12 
[Solve] Chips: 295 = F_13 + F_10 + F_5 + F_3 = 233 + 55 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 242 (User); Chips: 293; Takeable: 4 
[Solve] Chips: 293 = F_13 + F_10 + F_5 = 233 + 55 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 243 (Computer); Chips: 289; Takeable: 8 
[Solve] Chips: 289 = F_13 + F_10 + F_2 = 233 + 55 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 244 (User); Chips: 288; Takeable: 2 
[Solve] Chips: 288 = F_13 + F_10 = 233 + 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 245 (Computer); Chips: 286; Takeable: 4 
[Solve] Chips: 286 = F_13 + F_9 + F_7 + F_5 + F_2 = 233 + 34 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 246 (User); Chips: 285; Takeable: 2 
[Solve] Chips: 285 = F_13 + F_9 + F_7 + F_5 = 233 + 34 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 247 (Computer); Chips: 283; Takeable: 4 
[Solve] Chips: 283 = F_13 + F_9 + F_7 + F_4 = 233 + 34 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 248 (User); Chips: 280; Takeable: 6 
[Solve] Chips: 280 = F_13 + F_9 + F_7 = 233 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 249 (Computer); Chips: 274; Takeable: 12 
[Solve] Chips: 274 = F_13 + F_9 + F_5 + F_3 = 233 + 34 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 250 (User); Chips: 272; Takeable: 4 
[Solve] Chips: 272 = F_13 + F_9 + F_5 = 233 + 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 251 (Computer); Chips: 268; Takeable: 8 
[Solve] Chips: 268 = F_13 + F_9 + F_2 = 233 + 34 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 252 (User); Chips: 267; Takeable: 2 
[Solve] Chips: 267 = F_13 + F_9 = 233 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 253 (Computer); Chips: 265; Takeable: 4 
[Solve] Chips: 265 = F_13 + F_8 + F_6 + F_4 = 233 + 21 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 254 (User); Chips: 262; Takeable: 6 
[Solve] Chips: 262 = F_13 + F_8 + F_6 = 233 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 255 (Computer); Chips: 256; Takeable: 12 
[Solve] Chips: 256 = F_13 + F_8 + F_3 = 233 + 21 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 256 (User); Chips: 254; Takeable: 4 
[Solve] Chips: 254 = F_13 + F_8 = 233 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 257 (Computer); Chips: 250; Takeable: 8 
[Solve] Chips: 250 = F_13 + F_7 + F_4 + F_2 = 233 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 258 (User); Chips: 249; Takeable: 2 
[Solve] Chips: 249 = F_13 + F_7 + F_4 = 233 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 259 (Computer); Chips: 247; Takeable: 4 
[Solve] Chips: 247 = F_13 + F_7 + F_2 = 233 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 260 (User); Chips: 246; Takeable: 2 
[Solve] Chips: 246 = F_13 + F_7 = 233 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 261 (Computer); Chips: 244; Takeable: 4 
[Solve] Chips: 244 = F_13 + F_6 + F_4 = 233 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 262 (User); Chips: 241; Takeable: 6 
[Solve] Chips: 241 = F_13 + F_6 = 233 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 263 (Computer); Chips: 235; Takeable: 12 
[Solve] Chips: 235 = F_13 + F_3 = 233 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 264 (User); Chips: 233; Takeable: 4 
[Solve] Chips: 233 = F_13 = 233 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 265 (Computer); Chips: 229; Takeable: 8 
[Solve] Chips: 229 = F_12 + F_10 + F_8 + F_6 + F_2 = 144 + 55 + 21 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 266 (User); Chips: 228; Takeable: 2 
[Solve] Chips: 228 = F_12 + F_10 + F_8 + F_6 = 144 + 55 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 267 (Computer); Chips: 226; Takeable: 4 
[Solve] Chips: 226 = F_12 + F_10 + F_8 + F_5 + F_2 = 144 + 55 + 21 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 268 (User); Chips: 225; Takeable: 2 
[Solve] Chips: 225 = F_12 + F_10 + F_8 + F_5 = 144 + 55 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 269 (Computer); Chips: 223; Takeable: 4 
[Solve] Chips: 223 = F_12 + F_10 + F_8 + F_4 = 144 + 55 + 21 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 270 (User); Chips: 220; Takeable: 6 
[Solve] Chips: 220 = F_12 + F_10 + F_8 = 144 + 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 271 (Computer); Chips: 214; Takeable: 12 
[Solve] Chips: 214 = F_12 + F_10 + F_7 + F_3 = 144 + 55 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 272 (User); Chips: 212; Takeable: 4 
[Solve] Chips: 212 = F_12 + F_10 + F_7 = 144 + 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 273 (Computer); Chips: 208; Takeable: 8 
[Solve] Chips: 208 = F_12 + F_10 + F_6 + F_2 = 144 + 55 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 274 (User); Chips: 207; Takeable: 2 
[Solve] Chips: 207 = F_12 + F_10 + F_6 = 144 + 55 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 275 (Computer); Chips: 205; Takeable: 4 
[Solve] Chips: 205 = F_12 + F_10 + F_5 + F_2 = 144 + 55 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 276 (User); Chips: 204; Takeable: 2 
[Solve] Chips: 204 = F_12 + F_10 + F_5 = 144 + 55 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 277 (Computer); Chips: 202; Takeable: 4 
[Solve] Chips: 202 = F_12 + F_10 + F_4 = 144 + 55 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 278 (User); Chips: 199; Takeable: 6 
[Solve] Chips: 199 = F_12 + F_10 = 144 + 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 279 (Computer); Chips: 193; Takeable: 12 
[Solve] Chips: 193 = F_12 + F_9 + F_7 + F_3 = 144 + 34 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 280 (User); Chips: 191; Takeable: 4 
[Solve] Chips: 191 = F_12 + F_9 + F_7 = 144 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 281 (Computer); Chips: 187; Takeable: 8 
[Solve] Chips: 187 = F_12 + F_9 + F_6 + F_2 = 144 + 34 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 282 (User); Chips: 186; Takeable: 2 
[Solve] Chips: 186 = F_12 + F_9 + F_6 = 144 + 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 283 (Computer); Chips: 184; Takeable: 4 
[Solve] Chips: 184 = F_12 + F_9 + F_5 + F_2 = 144 + 34 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 284 (User); Chips: 183; Takeable: 2 
[Solve] Chips: 183 = F_12 + F_9 + F_5 = 144 + 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 285 (Computer); Chips: 181; Takeable: 4 
[Solve] Chips: 181 = F_12 + F_9 + F_4 = 144 + 34 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 286 (User); Chips: 178; Takeable: 6 
[Solve] Chips: 178 = F_12 + F_9 = 144 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 287 (Computer); Chips: 172; Takeable: 12 
[Solve] Chips: 172 = F_12 + F_8 + F_5 + F_3 = 144 + 21 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 288 (User); Chips: 170; Takeable: 4 
[Solve] Chips: 170 = F_12 + F_8 + F_5 = 144 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 289 (Computer); Chips: 166; Takeable: 8 
[Solve] Chips: 166 = F_12 + F_8 + F_2 = 144 + 21 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 290 (User); Chips: 165; Takeable: 2 
[Solve] Chips: 165 = F_12 + F_8 = 144 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 291 (Computer); Chips: 163; Takeable: 4 
[Solve] Chips: 163 = F_12 + F_7 + F_5 + F_2 = 144 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 292 (User); Chips: 162; Takeable: 2 
[Solve] Chips: 162 = F_12 + F_7 + F_5 = 144 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 293 (Computer); Chips: 160; Takeable: 4 
[Solve] Chips: 160 = F_12 + F_7 + F_4 = 144 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 294 (User); Chips: 157; Takeable: 6 
[Solve] Chips: 157 = F_12 + F_7 = 144 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 295 (Computer); Chips: 151; Takeable: 12 
[Solve] Chips: 151 = F_12 + F_5 + F_3 = 144 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 296 (User); Chips: 149; Takeable: 4 
[Solve] Chips: 149 = F_12 + F_5 = 144 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 297 (Computer); Chips: 145; Takeable: 8 
[Solve] Chips: 145 = F_12 + F_2 = 144 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 298 (User); Chips: 144; Takeable: 2 
[Solve] Chips: 144 = F_12 = 144 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 299 (Computer); Chips: 142; Takeable: 4 
[Solve] Chips: 142 = F_11 + F_9 + F_7 + F_5 + F_2 = 89 + 34 + 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 300 (User); Chips: 141; Takeable: 2 
[Solve] Chips: 141 = F_11 + F_9 + F_7 + F_5 = 89 + 34 + 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 301 (Computer); Chips: 139; Takeable: 4 
[Solve] Chips: 139 = F_11 + F_9 + F_7 + F_4 = 89 + 34 + 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 302 (User); Chips: 136; Takeable: 6 
[Solve] Chips: 136 = F_11 + F_9 + F_7 = 89 + 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 303 (Computer); Chips: 130; Takeable: 12 
[Solve] Chips: 130 = F_11 + F_9 + F_5 + F_3 = 89 + 34 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 304 (User); Chips: 128; Takeable: 4 
[Solve] Chips: 128 = F_11 + F_9 + F_5 = 89 + 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 305 (Computer); Chips: 124; Takeable: 8 
[Solve] Chips: 124 = F_11 + F_9 + F_2 = 89 + 34 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 306 (User); Chips: 123; Takeable: 2 
[Solve] Chips: 123 = F_11 + F_9 = 89 + 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 307 (Computer); Chips: 121; Takeable: 4 
[Solve] Chips: 121 = F_11 + F_8 + F_6 + F_4 = 89 + 21 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 308 (User); Chips: 118; Takeable: 6 
[Solve] Chips: 118 = F_11 + F_8 + F_6 = 89 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 309 (Computer); Chips: 112; Takeable: 12 
[Solve] Chips: 112 = F_11 + F_8 + F_3 = 89 + 21 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 310 (User); Chips: 110; Takeable: 4 
[Solve] Chips: 110 = F_11 + F_8 = 89 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 311 (Computer); Chips: 106; Takeable: 8 
[Solve] Chips: 106 = F_11 + F_7 + F_4 + F_2 = 89 + 13 + 3 + 1 
[Solve] Optimal: 1; Possible: {1, 4} 
[Input] Computer Takes: 1 
[State] Turn: 312 (User); Chips: 105; Takeable: 2 
[Solve] Chips: 105 = F_11 + F_7 + F_4 = 89 + 13 + 3 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 313 (Computer); Chips: 103; Takeable: 4 
[Solve] Chips: 103 = F_11 + F_7 + F_2 = 89 + 13 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 314 (User); Chips: 102; Takeable: 2 
[Solve] Chips: 102 = F_11 + F_7 = 89 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 315 (Computer); Chips: 100; Takeable: 4 
[Solve] Chips: 100 = F_11 + F_6 + F_4 = 89 + 8 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 316 (User); Chips: 97; Takeable: 6 
[Solve] Chips: 97 = F_11 + F_6 = 89 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 317 (Computer); Chips: 91; Takeable: 12 
[Solve] Chips: 91 = F_11 + F_3 = 89 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 318 (User); Chips: 89; Takeable: 4 
[Solve] Chips: 89 = F_11 = 89 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 319 (Computer); Chips: 85; Takeable: 8 
[Solve] Chips: 85 = F_10 + F_8 + F_6 + F_2 = 55 + 21 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 320 (User); Chips: 84; Takeable: 2 
[Solve] Chips: 84 = F_10 + F_8 + F_6 = 55 + 21 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 321 (Computer); Chips: 82; Takeable: 4 
[Solve] Chips: 82 = F_10 + F_8 + F_5 + F_2 = 55 + 21 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 322 (User); Chips: 81; Takeable: 2 
[Solve] Chips: 81 = F_10 + F_8 + F_5 = 55 + 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 323 (Computer); Chips: 79; Takeable: 4 
[Solve] Chips: 79 = F_10 + F_8 + F_4 = 55 + 21 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 324 (User); Chips: 76; Takeable: 6 
[Solve] Chips: 76 = F_10 + F_8 = 55 + 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 325 (Computer); Chips: 70; Takeable: 12 
[Solve] Chips: 70 = F_10 + F_7 + F_3 = 55 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 326 (User); Chips: 68; Takeable: 4 
[Solve] Chips: 68 = F_10 + F_7 = 55 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 327 (Computer); Chips: 64; Takeable: 8 
[Solve] Chips: 64 = F_10 + F_6 + F_2 = 55 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 328 (User); Chips: 63; Takeable: 2 
[Solve] Chips: 63 = F_10 + F_6 = 55 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 329 (Computer); Chips: 61; Takeable: 4 
[Solve] Chips: 61 = F_10 + F_5 + F_2 = 55 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 330 (User); Chips: 60; Takeable: 2 
[Solve] Chips: 60 = F_10 + F_5 = 55 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 331 (Computer); Chips: 58; Takeable: 4 
[Solve] Chips: 58 = F_10 + F_4 = 55 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 332 (User); Chips: 55; Takeable: 6 
[Solve] Chips: 55 = F_10 = 55 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 333 (Computer); Chips: 49; Takeable: 12 
[Solve] Chips: 49 = F_9 + F_7 + F_3 = 34 + 13 + 2 
[Solve] Optimal: 2; Possible: {2} 
[Input] Computer Takes: 2 
[State] Turn: 334 (User); Chips: 47; Takeable: 4 
[Solve] Chips: 47 = F_9 + F_7 = 34 + 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 335 (Computer); Chips: 43; Takeable: 8 
[Solve] Chips: 43 = F_9 + F_6 + F_2 = 34 + 8 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 336 (User); Chips: 42; Takeable: 2 
[Solve] Chips: 42 = F_9 + F_6 = 34 + 8 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 337 (Computer); Chips: 40; Takeable: 4 
[Solve] Chips: 40 = F_9 + F_5 + F_2 = 34 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 338 (User); Chips: 39; Takeable: 2 
[Solve] Chips: 39 = F_9 + F_5 = 34 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 339 (Computer); Chips: 37; Takeable: 4 
[Solve] Chips: 37 = F_9 + F_4 = 34 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 340 (User); Chips: 34; Takeable: 6 
[Solve] Chips: 34 = F_9 = 34 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 341 (Computer); Chips: 28; Takeable: 12 
[Solve] Chips: 28 = F_8 + F_5 + F_3 = 21 + 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 342 (User); Chips: 26; Takeable: 4 
[Solve] Chips: 26 = F_8 + F_5 = 21 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 343 (Computer); Chips: 22; Takeable: 8 
[Solve] Chips: 22 = F_8 + F_2 = 21 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 344 (User); Chips: 21; Takeable: 2 
[Solve] Chips: 21 = F_8 = 21 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 345 (Computer); Chips: 19; Takeable: 4 
[Solve] Chips: 19 = F_7 + F_5 + F_2 = 13 + 5 + 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
[State] Turn: 346 (User); Chips: 18; Takeable: 2 
[Solve] Chips: 18 = F_7 + F_5 = 13 + 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 2 
[State] Turn: 347 (Computer); Chips: 16; Takeable: 4 
[Solve] Chips: 16 = F_7 + F_4 = 13 + 3 
[Solve] Optimal: 3; Possible: {3} 
[Input] Computer Takes: 3 
[State] Turn: 348 (User); Chips: 13; Takeable: 6 
[Solve] Chips: 13 = F_7 = 13 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 6 
[State] Turn: 349 (Computer); Chips: 7; Takeable: 12 
[Solve] Chips: 7 = F_5 + F_3 = 5 + 2 
[Solve] Optimal: 2; Possible: {2, 7} 
[Input] Computer Takes: 2 
[State] Turn: 350 (User); Chips: 5; Takeable: 4 
[Solve] Chips: 5 = F_5 = 5 
[Solve] Optimal: 1; Possible: {} 
[Input] User Takes: 4 
[State] Turn: 351 (Computer); Chips: 1; Takeable: 8 
[Solve] Chips: 1 = F_2 = 1 
[Solve] Optimal: 1; Possible: {1} 
[Input] Computer Takes: 1 
------ 
 Turns: 351 
Winner: Computer

39. [M24] Find a closed form expression for an, given that a0 = 0, a1 = 1, and an+2 = an+1 + 6an for n ≥ 0.

We may use the method of generating functions to find a closed form expression for an. Let

G(z) = ∑ k≥0akzk.

Then,

(1 − z − 6z2)G(z) = a 0z0 + (a 1 − a0)z1 + ∑ k≥2(ak − ak−1 − 6ak−2)zk = a0z0 + (a 1 − a0)z1 = 0 + (1 − 0)z = z,

or equivalently, using partial fractions,

G(z) = z 1 − z − 6z2 = z − (3z − 1)(2z + 1) = 1 5 − 1 − (3z − 1) + − 1 5 1 2z + 1 = 1 5 1 1 − 3z − 1 1 − (−2)z = 1 5 ∑ k≥03kzk −∑ k≥0(−2)kzk = ∑ k≥01 5 3k − (−2)k zk.

That is,

an = (3n − (−2)n)∕5.

40. [M25] Solve the recurrence

f(1) = 0;f(n) = min ⁡ 0<k<n max ⁡ (1 + f(k),2 + f(n − k)),for n > 1.

We have that

f(n) = m

for 0 ≤ Fm < n ≤ Fm+1, as shown below.

In the case that m = 0,

f(1) = 0,

and

F0 = 0 < 1 ≤ 1 = F1 = F0+1.

In the case that m = 1,

f(2) = min ⁡ 0<k<2 max ⁡ (1 + f(k),2 + f(2 − k)) = max ⁡ (1 + f(1),2 + f(2 − 1)) = max ⁡ (1,2) = 2,

and

F2 = 1 < 2 ≤ 2 = F3 = F2+1.

Then, assuming

f(n) = m

for Fm < n ≤ Fm+1, we must show that

f(n′) = m + 1

for Fm+1 < n′≤ Fm+2. Note that since f(n′) = min ⁡ 0<k<n′max ⁡ (1 + f(k),2 + f(n′− k)), we must have that f(n′) ≤ max ⁡ (1 + f(k),2 + f(n′− k)) for 0 < k < n′, including for k = Fm+1, since Fm+1 > 0 and Fm+1 < n′ by hypothesis. That is, since f(Fm+1) = m for Fm < Fm+1 ≤ Fm+1, and since f(n′− Fm+1) ≤ m − 1 for 0 < n′− Fm+1 ≤ Fm,

f(n′) ≤ max ⁡ (1 + f(F m+1),2 + f(n′− F m+1)) = max ⁡ (1 + m,2 + (m − 1)) = max ⁡ (m + 1,m + 1) = m + 1.

Then, to see why f(n′) ≮ m + 1, assume it is. Then there must exist some integer k < n′ such that f(k) < m, so that k ≤ Fm; and such that f(n′− k) < m − 1, so that n′− k ≤ Fm−1. Then k + n′− k = n′ < Fm + Fm−1 = Fm+1. But Fm+1 < n′ by the inductive hypothesis. That is, the assumption that f(n′) < m + 1 leads to a contradiction, allowing us to instead conclude that

f(n′) = m + 1,

as we needed to show.

________________________________________________________________________________

[section 6.2.1]

▸ 41. [M25] (Yuri Matiyasevich, 1990.) Let f(x) = ⌊x + ϕ−1⌋. Prove that if n = Fk1 + ⋯ + Fkr is the representation of n in the Fibonacci number system of exercise 34, then Fk1+1 + ⋯ + Fkr+1 = f(ϕn). Find a similar formula for Fk1−1 + ⋯ + Fkr−1.

We may prove the equality.

Proposition. ∑ ⁡ 1≤j≤rFkj+1 = ⌊ϕ−1 + ϕ∑ ⁡ 1≤j≤rFkj⌋ if kj > kj+1 + 1 for 1 ≤ j < r and kr > 1.

Proof. Let

n = ∑ 1≤j≤rFkj

be the unique Fibonacci representation of n, kj > kj+1 + 1 for 1 ≤ j < r and kr > 1. We must show that

∑ 1≤j≤rFkj+1 = ⌊ϕ−1 + ϕ∑ 1≤j≤rFkj⌋ = ⌊ϕn + ϕ−1⌋.

From exercise 11,

ϕ̂kj+1 = F kj+1ϕ̂ + Fkj ⇔Fkj+1ϕ̂ = ϕ̂kj+1 − F kj ⇔Fkj+1 = ϕ̂kj −ϕ̂−1F kj ⇔Fkj+1 = ϕ̂kj + ϕFkj.

Then

∑ 1≤j≤rFkj+1 = ∑ 1≤j≤r ϕ̂kj + ϕFkj = ∑ 1≤j≤rϕ̂kj + ∑ 1≤j≤rϕFkj = ∑ 1≤j≤rϕ̂kj + ϕ∑ 1≤j≤rFkj = ∑ 1≤j≤rϕ̂kj + ϕn = ϕn + ∑ 1≤j≤rϕ̂kj .

But ϕ̂ < 0, so if kj > 1 is even, ϕ̂kj > 0; or if kj > 1 is odd, ϕ̂kj < 0. This determines the upper and lower bounds of the sum of ϕ̂kj as

∑ 3≤k k odd ϕ̂k < ∑ 1≤j≤rϕ̂kj ≤∑ 2≤k k even ϕ̂k,

since ∑ ⁡ 3≤k k odd ϕ̂k is strictly less than ∑ ⁡ 1≤j≤rϕ̂kj given an infinite number of terms. But

∑ 3≤k k odd ϕ̂k = ∑ 3≤k k odd ϕ̂k+1 −ϕ̂k−1 = −ϕ̂3−1 = −ϕ̂2 = −ϕ̂1 + ϕ̂0 = −ϕ̂1 − 1 = ϕ−1 − 1

and

∑ 2≤k k even ϕ̂k = ∑ 2≤k k even ϕ̂k+1 −ϕ̂k−1 = −ϕ̂2−1 = −ϕ̂1 = ϕ−1.

so that

ϕ−1 − 1 < ∑ 1≤j≤rϕ̂kj ≤ ϕ−1.

That is,

ϕ−1 − 1 < ∑ 1≤j≤rϕ̂kj ≤ ϕ−1 ⇔ϕn + ϕ−1 − 1 < ϕn + ∑ 1≤j≤rϕ̂kj ≤ ϕn + ϕ−1 ⇔ϕn + ϕ−1 − 1 < ∑ 1≤j≤rFkj+1 ≤ ϕn + ϕ−1 ⇔∑ 1≤j≤rFkj+1 = ⌊ϕn + ϕ−1⌋

as we needed to show. □

The formula for ∑ ⁡ 1≤j≤rFkj−1 is similar,

∑ 1≤j≤rFkj−1 = ⌊ϕ−1 + ϕ−1 ∑ 1≤j≤rFkj⌋,

as shown below.

Proposition. ∑ ⁡ 1≤j≤rFkj−1 = ⌊ϕ−1 + ϕ−1 ∑ ⁡ 1≤j≤rFkj⌋ if kj > kj+1 + 1 for 1 ≤ j < r and kr > 1.

Proof. Let

n = ∑ 1≤j≤rFkj

be the unique Fibonacci representation of n, kj > kj+1 + 1 for 1 ≤ j < r and kr > 1. We must show that

∑ 1≤j≤rFkj−1 = ⌊ϕ−1 + ϕ−1 ∑ 1≤j≤rFkj⌋ = ⌊ϕ−1n + ϕ−1⌋.

From exercise 11,

ϕ̂kj = Fkjϕ̂ + Fkj−1 ⇔Fkj−1 = ϕ̂kj − Fkjϕ̂ ⇔Fkj−1 = ϕ̂kj −ϕ̂Fkj ⇔Fkj−1 = ϕ̂kj + ϕ−1F kj.

Then

∑ 1≤j≤rFkj−1 = ∑ 1≤j≤r ϕ̂kj + ϕ−1F kj = ∑ 1≤j≤rϕ̂kj + ∑ 1≤j≤rϕ−1F kj = ∑ 1≤j≤rϕ̂kj + ϕ−1 ∑ 1≤j≤rFkj = ∑ 1≤j≤rϕ̂kj + ϕ−1n = ϕ−1n + ∑ 1≤j≤rϕ̂kj .

But ϕ̂ < 0, so if kj > 1 is even, ϕ̂kj > 0; or if kj > 1 is odd, ϕ̂kj < 0. This determines the upper and lower bounds of the sum of ϕ̂kj as

∑ 3≤k k odd ϕ̂k < ∑ 1≤j≤rϕ̂kj ≤∑ 2≤k k even ϕ̂k,

since ∑ ⁡ 3≤k k odd ϕ̂k is strictly less than ∑ ⁡ 1≤j≤rϕ̂kj given an infinite number of terms. But

∑ 3≤k k odd ϕ̂k = ∑ 3≤k k odd ϕ̂k+1 −ϕ̂k−1 = −ϕ̂3−1 = −ϕ̂2 = −ϕ̂1 + ϕ̂0 = −ϕ̂1 − 1 = ϕ−1 − 1

and

∑ 2≤k k even ϕ̂k = ∑ 2≤k k even ϕ̂k+1 −ϕ̂k−1 = −ϕ̂2−1 = −ϕ̂1 = ϕ−1.

so that

ϕ−1 − 1 < ∑ 1≤j≤rϕ̂kj ≤ ϕ−1.

That is,

ϕ−1 − 1 < ∑ 1≤j≤rϕ̂kj ≤ ϕ−1 ⇔ϕ−1n + ϕ−1 − 1 < ϕ−1n + ∑ 1≤j≤rϕ̂kj ≤ ϕ−1n + ϕ−1 ⇔ϕ−1n + ϕ−1 − 1 < ∑ 1≤j≤rFkj−1 ≤ ϕ−1n + ϕ−1 ⇔∑ 1≤j≤rFkj+1 = ⌊ϕ−1n + ϕ−1⌋

as we needed to show. □

______________________________________________________________________________________________________________________________

[CMath, §6.6]

42. [M26] (D. A. Klarner.) Show that if m and n are nonnegative integers, there is a unique sequence of indices k1 ≫ k2 ≫⋯ ≫ kr such that

m = Fk1 + Fk2 + ⋯ + Fkr,n = Fk1+1 + Fk2+1 + ⋯ + Fkr+1.

(See exercise 34. The k’s may be negative, and r may be zero.)

We may prove the existence of such a sequence.

Proposition. There exists a unique sequence of indices kj, where kj > kj+1 + 1 for 1 ≤ j < r, r ≥ 0, such that m = ∑ ⁡ 1≤j≤rFkj and n = ∑ ⁡ 1≤j≤rFkj+1 if m,n ≥ 0.

Proof. Let m and n be nonnegative integers. We must show that there exists a unique sequence of indices kj, where kj > kj+1 + 1 for 1 ≤ j < r, r ≥ 0, such that

m = ∑ 1≤j≤rFkj, n = ∑ 1≤j≤rFkj+1.

If such a sequence exists, we must have for all integers N,

mFN−1 + nFN = ∑ 1≤j≤rFkjFN−1 + ∑ 1≤j≤rFkj+1FN = ∑ 1≤j≤r(FkjFN−1 + Fkj+1FN) = ∑ 1≤j≤rFkj+N by Eq. (6).

In the trivial case that r = 0, the representation is unique: in particular, the empty one. Otherwise, in the case that r > 0, let N = −kr + 2 and kj′ = kj + N for 1 ≤ j ≤ r, so that

kj′ = k j + N = kj − kr + 2,

and since kj ≥ kr, so that

kj′ > 1.

Then, by exercise 34, the representation

∑ 1≤j≤rFkj′

must be unique. Now let N be large enough so that

mϕ̂N−1 + nϕ̂N < ϕ−2.

Since ϕ2 = ϕ + 1,

ϕ2 ≥ ϕ + 1 ⇔ϕ ≥ ϕ−1 + 1 ⇔ϕ − 1 ≥ ϕ−1 ⇔1 − ϕ ≤−ϕ−1 ⇔ϕ−1 − 1 ≤−ϕ−2;

and since ϕ > 1,

ϕ ≥ 1 ⇔ϕ ≤ ϕ2 ⇔ϕ−2 ≤ ϕ−1;

we have that

mϕ̂N−1 + nϕ̂N < ϕ−2 ⇔ − ϕ−2 < mϕ̂N−1 + nϕ̂N < ϕ−2 ⇔ϕ−1 − 1 < mϕ̂N−1 + nϕ̂N < ϕ−2 ⇒ϕ−1 − 1 < mϕ̂N−1 + nϕ̂N ≤ ϕ−1 ⇒ϕ mFN−1 + nFN + ϕ−1 − 1 < ϕ mFN−1 + nFN + mϕ̂N−1 + nϕ̂N ≤ ϕ mFN−1 + nFN + ϕ−1 ⇒ϕ mFN−1 + nFN + mϕ̂N−1 + nϕ̂N = ⌊ϕ mF N−1 + nFN + ϕ−1⌋.

Then

mFN + nFN+1 = m ϕFN−1 + ϕ̂N−1 + n ϕF N + ϕ̂N by exercise 21 = mϕFN−1 + mϕ̂N−1 + nϕF N + nϕ̂N = ϕ mFN−1 + nFN + mϕ̂N−1 + nϕ̂N = ⌊ϕ mFN−1 + nFN + ϕ−1⌋ = ∑ 1≤j≤rFkj+N+1. by exercise 41

Finally, setting N = −1 yields

mF−1 + nF−1+1 = m + nF0 = m + 0 = m = ∑ 1≤j≤rFkj−1+1 = ∑ 1≤j≤rFkj,

and setting N = 0 yields

mF0 + nF0+1 = 0 + nF1 = n = ∑ 1≤j≤rFkj+0+1 = ∑ 1≤j≤rFkj+1,

concluding our proof that there exists a unique sequence of indices kj, where kj > kj+1 + 1 for 1 ≤ j < r, r ≥ 0, such that

m = ∑ 1≤j≤rFkj, n = ∑ 1≤j≤rFkj+1,

as we needed to show. □

______________________________________________________________________________________________________________________________

[D. A. Klarner, Fibonacci Quarterly 6 (1968), 235–244]