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 = ϕn5 rounded to the nearest integer,

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

F1000 eln (ϕ10005) = e1000 ln ϕ1 2 ln 5 = e1000 ln ϕ1 2 ln 5 = e1000 ln ϕ1 2 (ln 10ln 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 Fn1 > 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 + Fn1 > 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 Fn1 > 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 + Fn1 > 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 Fn1 ) = ( 11 1 0 )n.

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

(Fn+1 Fn Fn Fn1 ) = (11 1 0 )n.

In the case that n = 1,

(F1+1 F1 F1 F11 ) = (F2F1 F1F0 ) = (11 1 0 ) = (11 1 0 )1;

and in the case that n = 2,

(F2+1 F2 F2 F21 ) = (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 Fn1 ) = (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 + Fn1 Fn+1 Fn ) = (1 Fn+1 + 1 Fn1 Fn + 1 Fn1 1 Fn+1 + 0 Fn1 Fn + 0 Fn1 ) = (11 1 0 ) (Fn+1 Fn Fn Fn1 ) = (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 F1? What is F2? Can Fn be expressed in a simple way in terms of Fn?

Allowing n to range over all integers, we require

F1 = F0 + F1,

or equivalently,

F1 = F1 F0 = 1 0 = 1.

Similarly,

F2 = F0 F1 = 0 1 = 1,

and in general for nonegative n,

Fn = (1)n+1F n,

as is shown below.

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

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

Fn = Fn+2 Fn+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,

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

Then, assuming

Fn = Fn+2 Fn+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 = Fn+1 Fn = (1)(n1)+1F n1 (1)n+1F n = (1)nF n1 (1)n+1F n = (1)nF n1 + (1)nF n = (1)n (F n1 + 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+1Fn1 Fn2 = (1)n for negative n.

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

Fn+1Fn1 Fn2 = (1)n.

In the case that n = 1,

F0F2 F12 = 1 = (1)1;

and in the case that n = 2,

F1F3 F22 = 2 1 = 1 = (1)2.

Then, assuming

Fn+1Fn1 Fn2 = (1)n,

we must show that

FnFn2 Fn12 = (1)n1.

But

FnFn2 Fn12 = (F n+1 Fn1)(Fn Fn1) Fn12 = Fn+1Fn Fn1Fn Fn+1Fn1 + Fn12 F n12 = Fn+1Fn Fn1Fn Fn+1Fn1 = Fn(Fn+1 Fn1) Fn+1Fn1 = FnFn Fn+1Fn1 = Fn2 F n+1Fn1 = (1)(Fn+1Fn1 Fn2) = (1)(1)n = (1)n1

as we needed to show. □

Proposition. Fn+m = FmFn+1 + Fm1Fn 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 + Fm1Fn.

In the case that n = 1,

F1+m = Fm1 = FmF0 + Fm1F1;

and in the case that n = 2,

F2+m = Fm Fm1 = FmF1 + Fm1F2.

Then, assuming

Fn+m = FmFn+1 + Fm1Fn

we must show that

Fn+m1 = FmFn + Fm1Fn1.

But

Fn+m1 = Fn+m+1 Fn+m = FmFn+2 + Fm1Fn+1 FmFn+1 Fm1Fn = Fm(Fn+2 Fn+1) + Fm1(Fn+1 Fn) = FmFn + Fm1Fn1

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,

F1 = 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,

F2 = 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 + 5)2 4 (1 5)2 ) = 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

Fn1 = 1 5 (ϕn1 ϕ^n1) .

But

Fn1 = 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 ϕ)ϕn1 (ϕ^2 ϕ^)ϕ^n1) = 1 5 (ϕ (1 + 5 2 1)ϕn1 (ϕ^2 ϕ^)ϕ^n1) = 1 5 (ϕ ( 1 + 5 2 )ϕn1 (ϕ^2 ϕ^)ϕ^n1) = 1 5 (1 + 5 2 1 + 5 2 ϕn1 (ϕ^2 ϕ^)ϕ^n1) = 1 5 ( 1 + 52 4 ϕn1 (ϕ^2 ϕ^)ϕ^n1) = 1 5 (4 4ϕn1 (ϕ^2 ϕ^)ϕ^n1) = 1 5 (ϕn1 (ϕ^2 ϕ^)ϕ^n1) = 1 5 (ϕn1 ϕ^ (1 5 2 1)ϕ^n1) = 1 5 (ϕn1 ϕ^ ( 1 5 2 )ϕ^n1) = 1 5 (ϕn1 1 5 2 1 5 2 ϕ^n1) = 1 5 (ϕn1 1 + 52 4 ϕ^n1) = 1 5 (ϕn1 4 4ϕ^n1) = 1 5 (ϕn1 ϕ^n1)

as we needed to show. □

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

Proof. Consider n = 1. Then F1 = 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 ϕn5 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ϕ + Fn1 and ϕ^n = Fnϕ^ + Fn1, for all integers n.

We show both identities.

Proposition. ϕn = Fnϕ + Fn1.

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

ϕn = F nϕ + Fn1.

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ϕ + F1;

and if n = 1,

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

Then, assuming

ϕn = F nϕ + Fn1

we must show that

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

But

ϕn+1 = ϕϕn = ϕ (Fnϕ + Fn1) = Fnϕ2 + F n1ϕ = Fn (ϕ + 1) + Fn1ϕ = Fnϕ + Fn1ϕ + Fn = (Fn + Fn1) ϕ + Fn = Fn+1ϕ + Fn.

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

ϕ0 = 1 = 0 + 1 = F 0ϕ + F1;

and if n = 1,

ϕ1 = ϕ 1 = F 1ϕ + F2.

Then, assuming

ϕn = F nϕ + Fn1

we must show that

ϕn1 = F n1ϕ + Fn2.

But

ϕn1 = ϕ1ϕn = ϕ1 (F nϕ + Fn1) = Fn + Fn1ϕ1 = Fn1ϕ1 + F n = Fn1 (ϕ 1) + Fn = Fn1ϕ + Fn Fn1 = Fn1ϕ + Fn2.

Therefore,

ϕn = F nϕ + Fn1

for all integers n as we needed to show. □

Proposition. ϕ^n = Fnϕ^ + Fn1.

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

ϕ^n = F nϕ^ + Fn1.

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ϕ^ + F1;

and if n = 1,

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

Then, assuming

ϕ^n = F nϕ^ + Fn1

we must show that

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

But

ϕ^n+1 = ϕ^ϕ^n = ϕ^ (Fnϕ^ + Fn1) = Fnϕ^2 + F n1ϕ^ = Fn (ϕ^ + 1) + Fn1ϕ^ = Fnϕ^ + Fn1ϕ^ + Fn = (Fn + Fn1) ϕ^ + Fn = Fn+1ϕ^ + Fn.

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

ϕ^0 = 1 = 0 + 1 = F 0ϕ^ + F1;

and if n = 1,

ϕ^1 = ϕ^ 1 = F 1ϕ^ + F2.

Then, assuming

ϕ^n = F nϕ^ + Fn1

we must show that

ϕ^n1 = F n1ϕ^ + Fn2.

But

ϕ^n1 = ϕ^1ϕ^n = ϕ^1 (F nϕ^ + Fn1) = Fn + Fn1ϕ^1 = Fn1ϕ^1 + F n = Fn1 (ϕ^ 1) + Fn = Fn1ϕ^ + Fn Fn1 = Fn1ϕ^ + Fn2.

Therefore,

ϕ^n = F nϕ^ + Fn1

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 + n2(n n1 n2)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 1)Fn + 2 5nFn1) zn = Fn+1zn+1 + (1 2 (n 1)Fn + 2 5nFn1) zn+1 = (Fn+1 + 1 2 (n 1)Fn + 2 5nFn1) zn+1 = (Fn + 1 2 (n 2)Fn1 + 2 5(n 1)Fn2) zn.

But

Fn + 1 2 (n 2)Fn1 + 2 5(n 1)Fn2 = Fn1 + Fn2 + n 2 5 Fn1 + 2n 2 5 Fn2 = n + 3 5 Fn1 + 2n + 3 5 Fn2 = 2n + 3 5 Fn1 + 2n + 3 5 Fn2 n 5 Fn1 = 2n + 3 5 Fn n 5 Fn1 = 3n + 3 5 Fn n 5 Fn n 5 Fn1 = 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 F1 = 1, we can express an in terms of the Fibonacci numbers as
a0 = r = sF0 + rF1 a1 = s = sF1 + rF0 a2 = a1 + a0 = sF1 + rF0 + sF0 + rF1 = sF2 + rF1

and in general for n 0 as

an = sFn + rFn1.

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

an+1 = an + an1 = sFn + rFn1 + sFn1 + rFn2 = s (Fn + Fn1) + r (Fn1 + Fn2) = 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 + cFn1

if and only if

bn = (1 + c)Fn + cFn1 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 = 0kn1 k n k 1, (14.1)

which may be shown using induction, since

F0 = 0 = 0k1 k k 1

and

F1 = 1 = 0k0 k k;

and assuming

Fn = 0kn1 k n k 1

implies

Fn+1 = Fn + Fn1 = 0kn1 k n k 1 + 0kn2 k n k 2 = n 1 0 + 0kn2 k n k 1 + 0kn2 k n k 2 = 1 + 0kn2 k n k 1 + 0kn2 k n k 2 = 1 + 0kn2 k + 1 n k 1 = 1 + 1kn1 k n k = 1 + 0kn1 k n k 0 n = 1 + 0kn1 k n k = 1 + 0kn k n k n 0 = 1 + 0kn k n k 1 = 0kn k n k = 0kn1+1 k n + 1 k 1.

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

0km ( 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

0km ( n + k m k n + k + 1 m k 1 ) = n m,

including the induction basis n1 nm2 = n1 n1(m+1) = n1 m+1, implies

0km+1 ( n + k m + 1 k n + k + 1 m + 1 k 1 ) = 0km+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) ) + 0km ( n + k m k + 1 n + k + 1 m k ) = (n + m + 1 0 n + m + 2 1 ) + 0km ( n + k m k + 1 n + k + 1 m k ) = (1 0) + 0km ( n + k m k + 1 n + k + 1 m k ) = (n + m 0 n + m + 1 1 ) + 0km ( n + k m k + 1 n + k + 1 m k ) = ( n 1 + (m + 1) m + 1 (m + 1) n + (m + 1) m (m + 1) ) + 0km ( n 1 + k m + 1 k n + k m k + n 1 + k m k n + k m k 1 ) = 0km+1 ( n 1 + k m + 1 k n + k m k ) + 0km (n 1 + k m k n + k m k 1 ) = 0km+1 ( n 1 + k m + 1 k n 1 + k + 1 m + 1 k 1 ) + 0km (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 0km n + k m k.

In the case that n = 0,

a0 = 0 = Fm+1 0km+11 k m + 1 k 1 from (14.1) = Fm+1 0km k m k = Fm+1 + 0 0km 0 + k m k = Fm+1 + F0 0km 0 + k m k;

and in the case that n = 1,

a1 = 1 = F1 = F1 + 0 = F1 + Fm+2 01+km+21 1 + k m + 2 (1 + k) 1 from (14.1) = Fm+2 + F1 1km 1 + k m k = Fm+2 + F1 0km 1 + k m k 0 m + 1 = Fm+2 + F1 0km 1 + k m k 0 = Fm+2 + F1 0km 1 + k m k.

Then, assuming

an = Fm+n+1 + Fn 0km n + k m k,

we must show that

an+1 = Fm+n+2 + Fn+1 0kmn + k + 1 m k .

But

an+1 = an + an1 + n 1 m = Fm+n+1 + Fn 0km n + k m k + Fm+n + Fn1 0kmn + k 1 m k + n 1 m = Fm+n+2 + Fn+1 0km n + k m k 0kmn + k 1 m k + n 1 m = Fm+n+2 + Fn+1 0km ( n + k m k + n + k 1 m k ) + 0km (n 1 + k m k n 1 + k + 1 m k 1 ) from (14.2) = Fm+n+2 + Fn+1 + 0km (n + k 1 m k n + k m k n + k 1 m k n + k m k 1 ) = Fm+n+2 + Fn+1 0km ( n + k m k + n + k m k 1 ) = Fm+n+2 + Fn+1 0kmn + 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 + 1kn1Fkf(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 + 1kn1Fkf(n k 1). (15.1)

In the case that n = 0,

a0 = 0 = F0 + 1k1Fkf(n k 1);

and in the case that n = 1,

a1 = 1 = F1 + 1k0Fkf(n k 1).

Then, assuming

an = Fn + 1kn1Fkf(n k 1)

we must show that

an+1 = Fn+1 + 1knFkf(n k).

But

an+1 = an + an1 + f(n 1) = Fn + 1kn1Fkf(n k 1) + Fn1 + 1kn2Fkf(n k 2) + f(n 1) = Fn + Fn1 + f(n 1) + 1kn1Fkf(n k 1) + 1kn2Fkf(n k 2) = Fn+1 + f(n 1) + 1kn1Fkf(n k 1) + 1kn2Fkf(n k 2) = Fn+1 + f(n 1) + 2knFk1f(n k) + 3knFk2f(n k) = Fn+1 + f(n 1) + 2knFk1f(n k) + 2knFk2f(n k) = Fn+1 + f(n 1) + 2kn (Fk1 + Fk2) f(n k) = Fn+1 + f(n 1) + 2knFkf(n k) = Fn+1 + 1knFkf(n k)

and hence the result. □

Proposition. cn = Fn + x 1kn1Fkf(n k 1) + y 1kn1Fkg(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 1kn1Fkf(n k 1) + y 1kn1Fkg(n k 1). (15.2)

In the case that n = 0,

c0 = 0 = F0 + x 1k1Fkf(n k 1) + y 1k1Fkg(n k 1);

and in the case that n = 1,

c1 = 1 = F1 + x 1k0Fkf(n k 1) + y 1k0Fkf(n k 1).

Then, assuming

cn = Fn + x 1kn1Fkf(n k 1) + y 1kn1Fkg(n k 1)

we must show that

cn+1 = Fn+1 + x 1knFkf(n k) + y 1knFkg(n k).

But

cn+1 = cn + cn1 + xf(n 1) + yg(n 1) = Fn + x 1kn1Fkf(n k 1) + y 1kn1Fkg(n k 1) + Fn1 + x 1kn2Fkf(n k 2) + y 1kn2Fkg(n k 2) + xf(n 1) + yg(n 1) = Fn+1 + xf(n 1) + yg(n 1) + x 1kn1Fkf(n k 1) + y 1kn1Fkg(n k 1) + x 1kn2Fkf(n k 2) + y 1kn2Fkg(n k 2) = Fn+1 + xf(n 1) + yg(n 1) + x 2knFk1f(n k) + y 2knFk1g(n k) + x 3knFk2f(n k) + y 3knFk2g(n k) = Fn+1 + xf(n 1) + yg(n 1) + x 2knFk1f(n k) + y 2knFk1g(n k) + x 2knFk2f(n k) + y 2knFk2g(n k) = Fn+1 + xf(n 1) + yg(n 1) + x 2kn (Fk1 + Fk2) f(n k) + y 2kn (Fk1 + Fk2) g(n k) = Fn+1 + xf(n 1) + yg(n 1) + x 2knFkf(n k) + y 2knFkg(n k) = Fn+1 + x 1knFkf(n k) + y 1knFkg(n k)

and hence the result. □

We then solve for cn as

cn = Fn + x 1kn1Fkf(n k 1) + y 1kn1Fkg(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. 0knnk k = Fn+1.

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

0knn k k = Fn+1.

In the case that n = 0,

0k0k k = 0 0 = 1 = F1;

and in the case that n = 1,

0k11 k k = 1 0 + 0 1 = 1 + 0 = F2.

Then, assuming

0knn k k = Fn+1,

we must show that

0kn+1n + 1 k k = Fn+2.

But

0kn+1n + 1 k k = 0 n + 1 + 0knn + 1 k k = 0knn + 1 k k = 0kn (n k k + n k k 1 ) = 0knn k k + 0kn(n 1) (k 1) k 1 = Fn+1 + 0kn(n 1) (k 1) k 1 = Fn+1 + 1kn1n 1 k k = Fn+1 + n 1 + 0kn1n 1 k k = Fn+1 + 0kn1n 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+kFmk FnFm = (1)nFmnkFk.

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

Proposition. (xn+k yn+k)(xmk ymk) (xn yn)(xm ym) = (xy)n(xmnk ymnk)(xk yk).

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

(xn+k yn+k)(xmk ymk) (xn yn)(xm ym) = (xy)n(xmnk ymnk)(xk yk).

But

(xn+k yn+k)(xmk ymk) (xn yn)(xm ym) = (xy)n((xkyn xnyk)(xmnkyn xnymnk) (yn xn)(xmnyn xnymn)) = xmkyn+k xn+kymk + xmyn + xnym = (xy)n(xmnkyk xkymnk + xmn + ymn) = (xy)n(xmnk ymnk)(xk yk)

and hence the result. □

Finally, the proof.

Proposition. Fn+kFmk FnFm = (1)nFmnkFk.

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

Fn+kFmk FnFm = (1)nF mnkFk.

But since ϕn = (1 ϕ^)n = ϕ^n,

Fn+kFmk FnFm = 1 5 (ϕn+k ϕ^n+k) 1 5 (ϕmk ϕ^mk) 1 5 (ϕn ϕ^n) 1 5 (ϕm ϕ^m) = 1 52 ( (ϕn+k ϕ^n+k) (ϕmk ϕ^mk) (ϕn ϕ^n) (ϕm ϕ^m)) = 1 52 (ϕϕ^)n (ϕmnk ϕ^mnk) (ϕk ϕ^k) from (17.1) = (ϕϕ^)n 1 5 (ϕmnk ϕ^mnk) 1 5 (ϕk ϕ^k) = (ϕϕ^)nF mnkFk = (1 2(1 + 5)1 2(1 5))nF mnkFk = (1 4(1 + 5 5 52))nF mnkFk = ( 4 4 )nF mnkFk = (1)nF mnkFk

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 + Fn1) 2 + (F n+1 + Fn) 2 = Fn2 + 2F nFn1 + Fn12 + F n+12 + 2F n+1Fn + Fn2 = Fn12 + F n2 + F n2 + F n+12 + 2F nFn1 + 2Fn+1Fn = F2n1 + F2n+1 + 2FnFn1 + 2Fn+1Fn = F2n1 + F2n+1 + 2FnFn1 + 2(Fn+n Fn1Fn) from Eq. (6) = F2n1 + F2n+1 + 2FnFn1 + 2F2n 2Fn1Fn = F2n1 + 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 nx x2+x1 if x2 + x1 n+1xnF n+1 2x+1 otherwise

as shown here. First we consider the case that x2 + x1. 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+1Fn1 = 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 t1nkF m+k is always a Fibonacci number.

First, a corollary.

Proposition. Fnϕ + Fn1 = ϕn and Fnϕ^ + Fn1 = ϕ^n.

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

Fnϕ + Fn1 = ϕn (23.1)

and

Fnϕ^ + Fn1 = ϕ^n. (23.2)

In the case that n = 1,

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

and in the case that n = 2,

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

Then, assuming

Fnϕ + Fn1 = ϕn

we must show that

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

But

Fn+1ϕ + Fn = (Fn + Fn1) ϕ + Fn1 + Fn2 = Fnϕ + Fn1 + Fn1ϕ + Fn2 = ϕn + ϕn1 = ϕn+1

and hence the result for ϕ. The result for ϕ^ follows similarly as F1ϕ^ + F11 = F1ϕ^ + F0 = ϕ^ + 0 = ϕ^ = ϕ^1, F2ϕ^ + F21 = F2ϕ^ + F1 = ϕ^ + 1 = ϕ^2, and Fnϕ^ + Fn1 = ϕ^nFn+1ϕ^ + Fn = ϕ^n+1 since

Fn+1ϕ^ + Fn = (Fn + Fn1) ϕ^ + Fn1 + Fn2 = Fnϕ^ + Fn1 + Fn1ϕ^ + Fn2 = ϕ^n + ϕ^n1 = ϕ^n+1,

as we needed to show. □

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

kn kFtkF t1nkF m+k = kn kFtkF t1nk 1 5 (ϕm+k ϕ^m+k) = 1 5 kn kFtkF t1nk (ϕmϕk ϕ^mϕ^k) = 1 5 (ϕm kn kϕkF tkF t1nk ϕ^m kn kϕ^kF tkF t1nk) = 1 5 (ϕm kn k (ϕFt) kF t1nk ϕ^m kn k (ϕ^Ft) kF t1nk) = 1 5 (ϕm (F tϕ + Ft1) n ϕ^m (F tϕ^ + Ft1) 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

(11 0 0 00 0 1 1 1 0 0 0 0 0 1 1 100 0 0 0 0 0 111 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 = [11 1 1 ] = 11(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 = 1jn+1a1j cofactor (a1j) = a11 cofactor (a11) + a12 cofactor (a12) + 3jn+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 i2 j1 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 = 1inai1 cofactor (a i1) = a11 cofactor (a 11) + 2inai1 cofactor (a i1) = a11 cofactor (a11) + 0 = cofactor (a11) = (1)1+1 det minor ([a] n,1,1) = det [a]n1;

that is, that

det minor ([a]n+1,1,2) = det [a]n1. (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]n1 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(k1)2.

Proposition. 2nFn = 2 k oddn k 5(k1)2.

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

2nF n = 2 k oddn k 5(k1)2.

But

Fn = 1 5 (ϕn ϕ^n) 5Fn = (1 + 5 2 )n (1 5 2 )n 2n5F n = (1 + 5)n (1 5)n 2nF n = 1 5 ( (1 + 5)n (1 5)n) .

Therefore

2nF n = 1 5 ( (1 + 5)n (1 5)n) = 1 5 ( kn k 5k2 kn k (1)k5k2) = kn k 5(k1)2 kn k (1)k5(k1)2 = k evenn k 5(k1)2 + k oddn k 5(k1)2 k evenn k (1)k5(k1)2 k oddn k (1)k5(k1)2 = k evenn k 5(k1)2 + k oddn k 5(k1)2 k evenn k 5(k1)2 + k oddn k 5(k1)2 = k oddn k 5(k1)2 + k oddn k 5(k1)2 = 2 k oddn k 5(k1)2

as we needed to show. □

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

Proposition. Fp 5(p1)2(modp) if p is an odd prime.

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

Fp 5(p1)2(modp).

By Fermat’s theorem, Theorem 1.2.4-F,

2p 2(modp)1 2p1(modp).

Then, by exercise 25,

2pF p = 2 k oddp k5(k1)2.

And so

2pF p 2p12 k oddp k5(k1)2(modp) 2pF p 2p k oddp k5(k1)2(modp) Fp k oddp k5(k1)2(modp).

Then

Fp k oddp k5(k1)2 p p5(p1)2 + 1kp1 k odd p k5(k1)2 5(p1)2 + 1kp1 k odd p k5(k1)2 5(p1)2 + 0 by exercise 1.2.6-10(b) 5(p1)2(modp)

as we needed to show. □

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

Proposition. If p is a prime different from 5, then either pFp1 or pFp+1 (exclusively).

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

pFp1orpFp+1

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

2F2+1and2 F21

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

Fp+1Fp1 Fp2 = (1)p Fp+1Fp1 Fp2 = 1 Fp+1Fp1 = Fp2 1 Fp+1Fp1 Fp2 1(modp).

From the previous exercise,

Fp 5(p1)2(modp) Fp2 5p1(modp) Fp2 1 5p1 1(modp);

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

5p 5(modp) 5p1 1(modp) 5p1 1 0(modp).

And so,

Fp+1Fp1 Fp2 1 5p1 1 0(modp).

That is, that

pFp1orpFp+1.

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

Fp+1 = Fp + Fp1 = Fp + mp = np,

then pFp. But by Fermat’s theorem, again,

5p 5(modp) 5p1 1(modp) 5(p1)2 1(modp),

and from the previous exercise

Fp 5(p1)2 1(modp),

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

Fp1 = Fp + Fp+1 = Fp + mp = np,

then pFp. But as with the previous case,

Fp 1(modp)

contradicting the assumption Fp1 = mp, so that p Fp1 if pFp+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 = FnFn1Fnk+1 FkFk1F1 = j=1k (Fnk+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 = Fk1n 1 k + Fnk+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 = 1j0Fn0+j Fj = 1, n 1 = 1j1Fn1+j Fj = Fn F1 = Fn, n 2 = 1j2Fn2+j Fj = Fn1 F1 Fn F2 = Fn1Fn, n 3 = 1j3Fn3+j Fj = Fn2 F1 Fn1 F2 Fn F3 = 1 2Fn2Fn1Fn, n 4 = 1j4Fn4+j Fj = Fn3 F1 Fn2 F2 Fn1 F3 Fn F4 = 1 6Fn3Fn2Fn1Fn, n 5 = 1j5Fn5+j Fj = Fn4 F1 Fn3 F2 Fn2 F3 Fn1 F4 Fn F5 = 1 30Fn4Fn3Fn2Fn1Fn, and n 6 = 1j6Fn6+j Fj = Fn5 F1 Fn4 F2 Fn3 F3 Fn2 F4 Fn1 F5 Fn F6 = 1 240Fn5Fn4Fn3Fn2Fn1Fn.
b)
We may show that n k is always an integer by proving the recursive relation below.

Proposition. n k = Fk1n1 k + Fnk+1n1 k1 .

Proof. We must show that

n k = Fk1n 1 k + Fnk+1n 1 k 1

for 1 k n. But

n k = 1jkFnk+j Fj = FkFnk+1 + Fk1Fnk Fnk+k 1jkFnk+j Fj by Eq. (6) = FnkFk1 + Fnk+1Fk Fn 1jkFnk+j Fj = FnkFk1 Fn 1jkFnk+j Fj + Fnk+1Fk Fn 1jkFnk+j Fj = FnkFk1 Fn 1jkFnk+j Fj + Fnk+1 Fk Fn 1jkFnk+j Fj = FnkFk1 Fn 2jk+1Fnk+j1 Fj1 + Fnk+1 1jk1Fnk+j Fj = FnkFk1 Fn Fn 2jkFnk+j1 1jkFj + Fnk+1 1jk1Fnk+j Fj = FnkFk1 2jkFnk+j1 1jkFj + Fnk+1 1jk1Fnk+j Fj = Fk1Fnk+11 2jkFnk+j1 1jkFj + Fnk+1 1jk1Fnk+j Fj = Fk1 1jkFnk+j1 1jkFj + Fnk+1 1jk1Fnk+j Fj = Fk1 1jkFnk+j1 Fj + Fnk+1 1jk1Fnk+j Fj = Fk1 1jkFn1k+j Fj + Fnk+1 1jk1Fn1(k1)+j Fj = Fk1n 1 k + Fnk+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)(mk)2F n+km1 = 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)(mk)2F n+km1 = 0 if m > 0.

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

km k (1)(mk)2F n+km1 = 0,

or equivalently for n = n + m that

km k (1)(mk)2F n+km1 = 0 0kmm k (1)(mk)2F n+km1 = 0 0km m m k(1)(mk)2F n(mk)m1 = 0 0mkm m m k(1)(mk)2F n(mk)m1 = 0 0kmm k (1)k2F nkm1 = 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 = 0kn k n k. (30.2)

In the case that n = 0,

F1 = 1 = 1 = 0 0 = 0k0 k 0 k;

and in the case that n = 1,

F2 = 1 = 0 + 1 = 0 1 + 1 1 = 0k1 k 1 k;

Then assuming

Fn+1 = 0kn k n k,

we must show

Fn+2 = 0kn+1 k n k + 1.

But

Fn+2 = Fn+1 + Fn = 0kn k n k + 0kn1 k n k 1 = n 0 + 0kn1 k n k + 0kn1 k n k 1 = 1 + 0kn1 ( k n k + k n k 1 ) = 1 + 0kn1 k + 1 n k = 1 + 1kn k n k + 1 = n + 1 0 + 1kn k n k + 1 = n + 1 n (n + 1) + 1 + 1kn k n k + 1 = 1kn+1 k n k + 1 = 0 + 1kn+1 k n k + 1 = 0 n 0 + 1 + 1kn+1 k n k + 1 = 0kn+1 k n k + 1

and hence the result.

Preliminary result 30.3. We have that

Fn + Fn2 = ϕn1 + ϕ^n1 (30.3)

since by definition and (30.1)

Fn + Fn2 = Fn + Fn Fn1 = 2Fn Fn1 = 2ϕn ϕ^n ϕ ϕ^ ϕn1 ϕ^n1 ϕ ϕ^ = 2ϕn 2ϕ^n ϕn1 + ϕ^n1 ϕ ϕ^ = 2ϕn ϕn1 + ϕ^n1 2ϕ^n ϕ ϕ^ = 2ϕϕn1 ϕn1 + ϕ^n1 2ϕ^ϕ^n1 ϕ ϕ^ = (2ϕ 1)ϕn1 + (1 2ϕ^)ϕ^n1 ϕ ϕ^ = (2ϕ 1)ϕn1 + (2ϕ 1)ϕ^n1 ϕ ϕ^ = (2ϕ 1) (ϕn1 + ϕ^n1) ϕ ϕ^ = (ϕ ϕ^) (ϕn1 + ϕ^n1) ϕ ϕ^ = ϕn1 + ϕ^n1.

Preliminary result 30.4. We have that

FnFn2 Fn12 = ϕn1ϕ^n1 (30.4)

since by definition and (30.1)

FnFn2 Fn12 = F n (Fn Fn1) Fn12 = Fn2 F nFn1 Fn12 = Fn2 F n1 (Fn + Fn1) = Fn2 F n1Fn+1 = (ϕn ϕ^n ϕ ϕ^ )2 ϕn1 ϕ^n1 ϕ ϕ^ ϕn+1 ϕ^n+1 ϕ ϕ^ = ϕ2n 2ϕnϕ^n + ϕ^2n ϕ2n + ϕn+1ϕ^n1 + ϕn1ϕ^n+1 ϕ^2n (ϕ ϕ^)2 = ϕn+1ϕ^n1 2ϕnϕ^n + ϕn1ϕ^n+1 (ϕ ϕ^)2 = (ϕn1ϕ^n1) (ϕ2 2ϕϕ^ + ϕ^2) (ϕ ϕ^)2 = (ϕn1ϕ^n1) (ϕ ϕ^)2 (ϕ ϕ^)2 = ϕn1ϕ^n1.

Preliminary result 30.5. We may show that

(Fkx + Fk1) r (F k+1x + Fk) nr = s1,,skn r s1 n s1 s2 n sk1 sk xnsk (30.5)

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

(F1x + F11) r (F 1+1x + F1) nr = xr (x + 1)nr = xr (1 + x)nr = xr 0s1nrn r s1 xs1 = 0nrs1nr n r n r s1xnrs1 xr = 0s1nrn r s1 xns1 = s1 n r s1 xns1 .

Then, assuming

(Fkx + Fk1) r (F k+1x + Fk) nr = s1,,skn r s1 n s1 s2 n sk1 sk xnsk ,

we must show that

(Fk+1x + Fk) r (F k+2x + Fk+1) nr = s1,,sk+1 n r s1 n s1 s2 n sk sk+1 xnsk+1 .

But for x = 1 + x1,

(Fk+1x + Fk) r (F k+2x + Fk+1) nr = xr (F k+1 + Fkx1) rxnr (F k+2 + Fk+1x1) nr = xn (F k + Fk1 + Fkx1) r (F k+1 + Fk + Fk+1x1) nr = xn (F k + Fkx1 + F k1) r (F k+1 + Fk+1x1 + F k) nr = xn (F k (1 + x1) + F k1) r (F k+1 (1 + x1) + F k) nr = xn (F kx + F k1) r (F k+1x + F k) nr = xn s1,,skn r s1 n s1 s2 n sk1 sk xnsk = s1,,skn r s1 n s1 s2 n sk1 sk (1 + x1) nsk xn = s1,,skn r s1 n s1 s2 n sk1 sk (x + 1)nsk xsk = s1,,skn r s1 n s1 s2 n sk1 sk sk+1 n sk sk+1 xnsksk+1 xsk = s1,,sk+1 n r s1 n s1 s2 n sk sk+1 xnsk+1

and hence the result.

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

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

Preliminary Result 30.7. Define

An+1 = [aij]n+1 = [ i n j ]n+1 = [ 0 n 0 n1 0 0 1 n 1 n1 1 0 n n n n1n 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) = 0inbij.

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

(Fkx + Fk1) r (F k+1x + Fk) nr = s1,,skn r s1 n s1 s2 n sk1 sk xnsk (Fkx + Fk1) r (F k+1x + Fk) nrxr = s1,,skn r s1 n s1 s2 n sk1 sk xn+rsk 0rn (Fkx + Fk1) r (F k+1x + Fk) nrxr = 0rn s1,,skn r s1 n s1 s2 n sk1 sk xn+rsk n0 0rn (Fkx + Fk1) r (F k+1x + Fk) nrxr = n0 0rn s1,,skn r s1 n s1 s2 n sk1 sk xrsk xn

and since

tr (An+1k) = 0in s1,s2,,sk i=s1=s2==sk i n s1 s1 n s2 sk1 n sk = 0nin ns1,ns2,,nsk ni=ns1=ns2==nsk i n s1 s1 n s2 sk1 n sk = 0rn s1,s2,,sk i=s1=s2==sk n r s1 n s1 s2 n sk1 sk = 0rn s1,s2,,sk i=s1=s2==sk n r s1 n s1 s2 n sk1 sk x0 = 0rn s1,s2,,sk i=s1=s2==sk n r s1 n s1 s2 n sk1 sk xrsk

we have that

n0 0rn s1,,skn r s1 n s1 s2 n sk1 sk xrsk xn = n0 tr (An+1k) xn = n0 0rn (Fkx + Fk1) r (F k+1x + Fk) nrxr.

But

0rn (Fkx + Fk1) r (F k+1x + Fk) nrxr = 0rn 0srr s (Fkx)sF k1rs 0tnrn r t (Fk+1x)tF knrtxr = 0rn 0sr 0tnrr s n r t Fk+1tF ksF knrtF k1rsxsxtxr = 0rn 0sr 0tnrr s n r t Fk+1tF knr+stF k1rsxr+s+t = n=r+s+tr s n r t Fk+1tF knr+stF k1rsxn = n=r+s+tr s n r n r sFk+1nrsF k2sF k1rsxn = nr+sr s n r s Fk+1nrsF k2sF k1rsxn = r,s0r sFk1rsF k2sxr+s nr+sn r s (Fk+1x)nrs = r,s0r sFk1rsF k2sxr+s nr+sn r s Fk+1nrsxnrs = r,s0r sFk1rsF k2sxr+s snr(1)nrs s 1 n r s (Fk+1x)nrs by (30.6) = r,s0r sFk1rsF k2sxr+s 0nrs s 1 n r s (Fk+1x)nrs = r,s0r sFk1rsF k2sxr+s (1 F k+1x)s1 = s0Fk2sx2s (1 F k+1x)s1 r0r sFk1rsxrs = s0Fk2sx2s (1 F k+1x)s1 srr sFk1rsxrs = s0Fk2sx2s (1 F k+1x)s1 srr s (Fk1x)rs = s0Fk2sx2s (1 F k+1x)s1 sr(1)rss 1 r s (Fk1x)rs by (30.6) = s0Fk2sx2s (1 F k+1x)s1 0rss 1 r s (Fk1x)rs = s0Fk2sx2s (1 F k+1x)s1 (1 F k1x)s1 = 1 (1 Fk+1x) (1 Fk1x) s0 ( Fk2x2 (1 Fk+1x) (1 Fk1x) )s.

Then

1 (1 Fk+1x) (1 Fk1x) s0 ( Fk2x2 (1 Fk+1x) (1 Fk1x) )s = 1 (1 Fk+1x) (1 Fk1x) 1 1 Fk2x2 (1Fk+1x) (1Fk1x) = 1 (1 Fk+1x) (1 Fk1x) (1 Fk+1x) (1 Fk1x) (1 Fk+1x) (1 Fk1x) Fk2x2 = 1 (1 Fk+1x) (1 Fk1x) Fk2x2 = 1 1 Fk+1x Fk1x + Fk+1Fk1x2 Fk2x2 = 1 1 (Fk+1 + Fk1) x + (Fk+1Fk1 Fk2) x2 = 1 1 (ϕk + ϕ^k) x + (Fk+1Fk1 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 n0 (ϕkx)n ϕ^k n0 (ϕ^kx)n) = 1 ϕk ϕ^k (ϕk n0 (ϕk) nxn ϕ^k n0 (ϕ^k) nxn) = 1 ϕk ϕ^k ( n0ϕkn+kxn n0ϕ^kn+kxn) = 1 ϕk ϕ^k n0 (ϕkn+k ϕ^kn+k) xn = n0ϕkn+k ϕ^kn+k ϕk ϕ^k xn = n0ϕkn+k ϕ^kn+k ϕ ϕ^ ϕ ϕ^ ϕk ϕ^kxn = n0Fkn+k Fk xn.

And so,

n0 tr (An+1k) xn = n0Fkn+k Fk xn,

hence the result.

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

λj = ϕjϕ^nj (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) = 0jnpAn+1(λj) pAn+1(λj) 1 x λj = 0jn 1 x λj = 0jn1 x x x λj = 0jn 1x 1 λjx = 0jn k0 1 x (λj x )k = 0jn k0 λjk xk+1 = 0jn k0λjkxk1 = k0xk1 0jnλjk = k0xk1 tr (A n+1k) = k0xk1Fkn+k Fk by (30.7) = k0xk1ϕkn+k ϕ^kn+k ϕ ϕ^ ϕ ϕ^ ϕk ϕ^k by (30.1) = k0xk1ϕkn+k ϕ^kn+k ϕk ϕ^k = k0xk1 (ϕ^k) n1 (ϕkϕ^k) n+1 1 ϕkϕ^k = k0xk1 0jn (ϕ^k) n ( ϕk ϕ^k ) j = k0xk1 0jnϕjkϕ^(nj)k = 0jn k0 1 x (ϕjϕ^nj x )k = 0jn1 x 1 1 ϕjϕ^njx = 0jn 1 x ϕjϕ^nj

so that

0jn 1 x λj = 0jn 1 x ϕjϕ^nj λj = ϕjϕ^nj

and

pAn+1(x) = 0jn (x λj) = 0jn (x ϕjϕ^nj) ,

hence the result.

Preliminary Result 30.9. We may show that

(1)k(k+1)2 = (1)k2. (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)2m2 = (1)k2;

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)2m2 = (1)k2;

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+12 = (1)(2m+1)2 = (1)k2;

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+12 = (1)(2m+1)2 = (1)k2;

hence the result.

Preliminary Result 30.10. We may show that

0jn (x ϕjϕ^nj) = 0kn+1(1)k2n + 1 k xn+1k. (30.10)

By the q-nomial theorem2 ,

0kn1 (1 qkx) = 0kn(1)kn kqqk(k1)2xk,

where

n kq = 1jk1 qnk+j 1 qj ,

for q = ϕ^ϕ,

n kϕ^ϕ = 1jk1 (ϕ^ϕ)nk+j 1 (ϕ^ϕ)j = 1jk (ϕnk+j ϕ^nk+j) ϕj (ϕj ϕ^j) ϕnk+j = 1jkϕj ϕ^nk+jϕkn ϕj ϕ^j = 1jkϕj ϕ^nk+jϕ^nk ϕj ϕ^j = 1jkϕj ϕ^2n2k+j ϕj ϕ^j = 1jkϕj ϕ^nkϕ^nk+j ϕj ϕ^j = 1jkϕknϕnk+j ϕknϕ^nk+j ϕj ϕ^j = 1jkϕkn (ϕnk+j ϕ^nk+j) ϕj ϕ^j = (ϕkn) k 1jkϕnk+j ϕ^nk+j ϕj ϕ^j = ϕk2nk 1jkϕnk+j ϕ^nk+j ϕj ϕ^j = ϕk2nk 1jkϕnk+j ϕ^nk+j ϕ ϕ^ ϕ ϕ^ ϕj ϕ^j = ϕk2nk 1jkFnk+j Fj by (30.1) = ϕk2nk n k.

And so,

0kn1 (1 (ϕ^ϕ)kx) = 0kn1 (1 ϕkϕ^kx) = 0kn(1)kn kϕ^ϕ(ϕ^ϕ)k(k1)2xk = 0kn(1)kϕk2nk n k(ϕ^ϕ)k(k1)2xk = 0kn(1)kϕk(k+1)2nkϕ^k(k1)2n kxk.

Substituting ϕn1x for x yields

0kn1 (1 ϕkϕ^kϕn1x) = 0kn1 (1 ϕnk1ϕ^kx) = 0kn(1)kϕk(k+1)2nkϕ^k(k1)2n k(ϕn1x)k = 0kn(1)kϕk(k+1)2nkϕ^k(k1)2n kϕknkxk = 0kn(1)kϕk(k+1)2kϕ^k(k1)2n kxk = 0kn(1)kϕk(k1)2ϕ^k(k1)2n kxk = 0kn(1)k(ϕϕ^)k(k1)2n kxk = 0kn(1)k(1)k(k1)2n kxk = 0kn(1)k(k+1)2n kxk.

Substituting 1x for x yields

0kn1 (1 ϕnk1ϕ^kx) = 0kn1x ϕnk1ϕ^k x = 1 xn 0kn1 (x ϕnk1ϕ^k) = 0kn(1)k(k+1)2n k(1x)k = 0kn(1)k(k+1)2n k 1 xk = 0kn(1)k2n k 1 xk by (30.9)

if and only if

0kn1 (x ϕnk1ϕ^k) = 0kn(1)k2n kxnk,

or equivalently,

0jn (x ϕjϕ^nj) = 0kn+1(1)k2n + 1 k xn+1k,

and hence the result.

Preliminary Result 30.11. We may show that

[An+1k] n,j = n j Fk+1jF knj. (30.11)

In the case that k = 0,

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

Then, assuming

[An+1k] n,j = n j Fk+1jF knj,

we must show that

[An+1k+1] n,j = n j Fk+2jF k+1nj.

But

[An+1k+1] n,j = [An+1k A n+1] n,j = 0mn [An+1k] n,m [An+1] m,j = 0mn n mFk+1mF knm [A n+1] m,j = 0mn n mFk+1mF knm m n j = 0mn n n j n (n j) m (n j)Fk+1mF knm by Eq. (1.2.6-2) = 0mn n n j j j + m nFk+1mF knm = 0mn n n jFk+1nj j j + m nFk+1j+mnF knm = n j Fk+1nj 0mj j mFk+1mF kjm = n j Fk+1nj (F k+1 + Fk) j = n j Fk+2jF k+1nj

and hence the result.

Conclusion. We will now show that

0kmm k (1)k2F nkm1 = 0.

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

pAn+1(x) = 0jn (x ϕjϕ^nj) = 0kn+1(1)k2n + 1 k xn+1k.

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

0kn+1(1)k2n + 1 k An+1n1k = 𝒪

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+1n1k ] n,n = n nFn1k+1nF n1knn = F nkn.

And so,

0kn+1(1)k2n + 1 k Fnkn = 0,

or equivalently,

0kmm k (1)k2F nkm1 = 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 = ϕ2n1.

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

1F2nϕ (1 ϕ2n).

But clearly, 1F2n+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ϕ + F2nϕ + F(2n+1) 1 by exercise 8 = F2nϕ 1 + F2nϕ + F2n1 = F2nϕ 1 + ϕ2n by exercise 11 = F2nϕ (1 ϕ2n).

That is,

1F2nϕ (1 ϕ2n)

as we needed to show. □

Proposition. F2n+1ϕ mod 1 = ϕ2n1.

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

F2n+1ϕ mod 1 = ϕ2n1,

or equivalently that

1F2n+1ϕ ϕ2n1.

But clearly, 1F2n+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ϕ (F2n1ϕ + F2n2) = F2n+1ϕ ϕ2n1. by exercise 11

That is,

1F2n+1ϕ ϕ2n1

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+1Fnr, if m mod 4 = 1; (1)nFr, if m mod 4 = 2; (1)r+1+nFnr,if m mod 4 = 3.

Proposition. Fmn+r {Fr if m mod 4 = 0 (1)r+1Fnr if m mod 4 = 1 (1)nFr if m mod 4 = 2 (1)r+1+nFnrif m mod 4 = 3 (modFn).

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+1Fnr if m mod 4 = 1 (1)nFr if m mod 4 = 2 (1)r+1+nFnrif m mod 4 = 3 (modFn).

As preliminaries, note that since

Fn 0(modFn),

by repeated applications of Law 1.2.4-A,

aFn 0(modFn),

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

Fn 0 Fn Fn+1 Fn1(modFn)

if and only if

Fn+1 Fn1(modFn). (32.1)

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

Fr Fr Fn+10F r Fn+1mmod4F r(modFn).

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

(1)r+1F nr (1)r+1F nrF1 (1)r+1F nr(1)2F 1 (1)r+1F nr(1)1+1F 1 (1)r+1F nrF1 by exercise 8 (1)r+1F n(r+1)(1)F1 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(modFn).

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 nn1F1Fr (Fn+1Fn1 FnFn)Fr by exercise 17 Fn+1Fn1Fr Fn2F r Fn+1Fn1Fr by Law 1.2.4-A* Fn+1Fn+1Fr by (32.1) Fn+12F r Fn+1mmod4F r(modFn).

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

(1)r+1+nF nr (1)n(1)r+1F nr (1)n(1)r+1F nrF1 (1)n(1)r+1F nr(1)2F 1 (1)n(1)r+1F nr(1)1+1F 1 (1)n(1)r+1F nrF1 by exercise 8 (1)n(1)r+1F n(r+1)(1)F1 (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 nn1F1FrFn+1 (Fn+1Fn1 FnFn)FrFn+1 by exercise 17 Fn+12F n1Fr Fn2F rFn+1 Fn+12F n1Fr by Law 1.2.4-A* Fn+12F n+1Fr by (32.1) Fn+13F r Fn+1mmod4F r(modFn).

That is, we must show that

Fmn+r Fn+1mmod4F r(modFn).

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

Fmn+r F00+0 F0 F10F 0 F0+10F 0 Fn+1mmod4F r(modFn).

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

Fmn+r F1n+r Fn+r FrFn+1 + Fr1Fn by Eq. (4) FrFn+1 by Law 1.2.4-A* Fn+11F r Fn+1mmod4F r(modFn).

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

Fmn+r F2n+r Fn+n+r Fn+rFn+1 + Fn+r1Fn by Eq. (4) Fn+rFn+1 by Law 1.2.4-A* (FrFn+1 + Fr1Fn)Fn+1 by Eq. (4) FrFn+12 + F r1Fn+1Fn FrFn+12 by Law 1.2.4-A* Fn+12F r Fn+1mmod4F r(modFn).

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

Fmn+r F3n+r Fn+2n+r F2n+rFn+1 + F2n+r1Fn by Eq. (4) F2n+rFn+1 by Law 1.2.4-A* Fn+n+rFn+1 (Fn+rFn+1 + Fn+r1Fn)Fn+1 by Eq. (4) Fn+rFn+12 + F n+r1Fn+1Fn Fn+rFn+12 by Law 1.2.4-A* (FrFn+1 + Fr1Fn)Fn+12 by Eq. (4) FrFn+13 + F r1Fn+12F n FrFn+13 by Law 1.2.4-A* Fn+13F r Fn+1mmod4F r(modFn).

Then, assuming

Fmn+r Fn+1mmod4F r(modFn),

we must show that

F(m+1)n+r Fn+1(m+1)mod4F r(modFn).

But

F(m+1)n+r Fmn+n+r Fn+mn+r Fmn+rFn+1 + Fmn+r1Fn by Eq. (4) Fmn+rFn+1 by Law 1.2.4-A* Fn+1mmod4F rFn+1 Fn+1mmod4+1F r(modFn).

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(modFn).

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(modFn).

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(modFn).

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+1Fn1) 2F r by (32.1) (Fn+1Fn1) 2F r + FnFr (2FnFn+1Fn1 + Fn3) by Law 1.2.4-A* ( (Fn+1Fn1) 2 + F n (2FnFn+1Fn1 + Fn3)) F r ( (Fn+1Fn1) 2 2F n2F n+1Fn1 + (Fn2) 2) F r (Fn+1Fn1 Fn2) 2F r (Fn+1Fn1 FnFn) 2F r ((1)nF nn1F1) 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(modFn).

And so,

F(m+1)n+r Fn+1mmod4+1F r Fn+1(m+1)mod4F r(modFn)

as we needed to show. □

33. [HM24] Given that z = π2 + iln ϕ, show that sin nzsin z = i1nFn.

Proposition. sin (nz)sin (z) = i1nFn if z = π2 + iln ϕ.

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

sin (nz)sin (z) = i1nF n.

As preliminaries, note that

cos (z) = 1 2(eiz + eiz) = 1 2(ei(π2+i ln ϕ) + ei(π2+i ln ϕ)) = 1 2(eiπ2+i2 ln ϕ + e(iπ2+i2 ln ϕ )) = 1 2(eiπ2ln ϕ + eiπ2+ln ϕ) = 1 2(eiπ2e ln ϕ + eiπ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)22i(1 + 5) + (1 + 5)22i(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) = 12i = i2

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 = i1nF 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) = 2i22 = i2 = (1) = 1 = i0 = i11F 1 = i1nF n.

Then, assuming that

sin (nz)sin (z) = i1nF 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) = i1 sin (nz)sin (z) sin ((n 1)z)sin (z) = i1i1nF n i1(n1)F n1 = i1(n+1)F n i1n+1F n1 = i1(n+1)F n + i1n1F n1 = i1(n+1)F n + i1(n+1)F n1 = i1(n+1)(F n + Fn1) = 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. 1jrFkj < 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

1jrFkj < Fk1+1 (34.1)

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

1j1Fkj = Fk1 = F2 = 1 < 2 = F3 = F2+1 = Fk1+1

where k1 = 2 > 1. Then, assuming

1jrFkj < Fk1+1

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

1jrFkj < 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 Fk11

then

1jrFkj = Fk1 + 2jrFkj < Fk1 + Fk2+1 Fk1 + Fk11 = Fk1+1

as we needed to show. □

Then, we proceed with the requested proof.

Proposition. Every positive integer n has a unique representation n = 1jrFkj, 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 = 1jrFkj

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

Existence. If n = 1,

1 = 1j1Fkj = Fk1 = F2

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

2 = 1j1Fkj = Fk1 = F3

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

3 = 1j1Fkj = Fk1 = F4

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

4 = 1j2Fkj = Fk1 + Fk2 = F4 + F2 = 3 + 1

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

n = 1jrFkj,

we must show that there exists a representation

n + 1 = 1jrFkj.

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

n + 1 = 1j1Fkj = 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 = 1jrFkj.

But

n + 1 < Fj+1 m + Fj < Fj+1 m < Fj+1 Fj m < Fj1.

That is, m does not contain Fj1, and so

n + 1 = 1jrFkj = Fj + m = Fj + 1jrFkj

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

Uniqueness. Let n have the two representations

n = 1jrFkj

and

n = 1jrFkj;

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 sSs = sSs, we also have that tTt = tTt. We will assume that SS, so that neither T nor T is empty. Select the largest element of each, and let these be Ft and Ft, respectively. Note that FtFt. Without loss of generaltiy, assume Ft < Ft. Then, by (34.1),

tTt < Ft+1 Ft tTt.

But tTt = tTt, 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 = ϕk1 + ϕk2,

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 ϕk1 + ϕk2 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 ϕk1 + ϕk2, 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)ϕ1kϕ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)ϕ11 ϕ1 = 2 ϕ11 ϕ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)ϕ11 ϕ1 = 2 ϕ11 ϕ1 = 1 0 = 1;

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

(2 + 1)ϕ12 ϕ1 = 3 ϕ12 ϕ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) = α(SnSn1,k).

In the case that 1 k Fn, then α(SnSn1,k) = α(Sn,k), and α holds by the inductive hypothesis. Otherwise, in the case that Fn + 1 k Fn+1, then α(SnSn1,k) = α(Sn1,k Fn) = α(Sn1,k) for 1 k = k Fn Fn1, and α holds again by the inductive hypothesis, and hence the result.

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

β(Sn) = { (Fn + 1)ϕ1if 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) + β(Sn1).

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κ = 1jrκ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 j1jrκFkκ,j qκ |j1 = 1 Fkκ,j 11 > 2 j1jrκ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μ ( 1jrκ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 = μ ( 1jrκ1Fkκ,j) = μ ( 1jrκFkκ,j Fkκ,rκ) = μ ( 1jrκFkκ,j μ ( 1jrκ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 = Fj1 + Fj2 and Fj2 Fj1, we have that

Fj Fj1 + Fj1 = 2Fj1

or equivalently that

Fj 2Fj1 2Fj1 Fj Fj1 1 2Fj Fj1 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+(k1j)mod2iuF2i1+kmod2 = Fk Fj1+(k1j)mod2.

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

v+(k1j)mod2iuF2i1+kmod2 = v+1iuF2i1+kmod2 = v+1iuF2i = uiuF2i = F2u = F2u+1 F2u1 = Fk F2(v+1)1 = Fk F2v+21 = Fk F2v+1 = Fk Fj = Fk Fj1+1 = Fk Fj1+1 = Fk Fj1+(k1j)mod2.

Assuming

v+(k1j)mod2iuF2i1+kmod2 = Fk Fj1+(k1j)mod2,

we must show that

v+(k+21j)mod2iu+1F2i1+(k+2)mod2 = Fk+2 Fj1+(k+21j)mod2.

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

v+(k+21j)mod2iu+1F2i1+(k+2)mod2 = v+1iu+1F2i1+(k+2)mod2 = v+1iu+1F2i = F2(u+1) + v+1iuF2i = F2(u+1) + v+1iuF2i1+kmod2 = F2(u+1) + Fk Fj1+(k1j)mod2 = F2u+2 + Fk Fj1+(k1j)mod2 = Fk+1 + Fk Fj1+(k1j)mod2 = Fk+2 Fj1+(k1j)mod2 = Fk+2 Fj1+(k+21j)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+(k1j)mod2iuF2i1+kmod2 = Fk Fj1+(k1j)mod2.

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

v+(k1j)mod2iuF2i1+kmod2 = v+1iuF2i1+kmod2 = v+1iuF2i1 = uiuF2i1 = F2u1 = F2u F2u2 = Fk F2(v+1)2 = Fk F2v+22 = Fk F2v = Fk Fj = Fk Fj1+1 = Fk Fj1+1 = Fk Fj1+(k1j)mod2.

Assuming

v+(k1j)mod2iuF2i1+kmod2 = Fk Fj1+(k1j)mod2,

we must show that

v+(k+21j)mod2iu+1F2i1+(k+2)mod2 = Fk+2 Fj1+(k+21j)mod2.

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

v+(k+21j)mod2iu+1F2i1+(k+2)mod2 = v+1iu+1F2i1+(k+2)mod2 = v+1iu+1F2i1 = F2(u+1)1 + v+1iuF2i1 = F2(u+1)1 + v+1iuF2i1+kmod2 = F2(u+1)1 + Fk Fj1+(k1j)mod2 = F2u+21 + Fk Fj1+(k1j)mod2 = F2u+1 + Fk Fj1+(k1j)mod2 = Fk+1 + Fk Fj1+(k1j)mod2 = Fk+2 Fj1+(k1j)mod2 = Fk+2 Fj1+(k+21j)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+(k1j)mod2iuF2i+1+kmod2 = Fk Fj1+(k1j)mod2.

If u = vk = j + 1,

v+(k1j)mod2iuF2i1+kmod2 = v+0iuF2i1+kmod2 = viuF2i = uiuF2i = F2u = F2u+1 F2u1 = Fk F2u1 = Fk F2v1 = Fk Fj1 = Fk Fj1+0 = Fk Fj1+(k1j)mod2.

Assuming

v+(k1j)mod2iuF2i1+kmod2 = Fk Fj1+(k1j)mod2,

we must show that

v+(k+21j)mod2iu+1F2i1+(k+2)mod2 = Fk+2 Fj1+(k+21j)mod2.

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

v+(k1j)mod2iu+1F2i1+(k+2)mod2 = v+0iu+1F2i1+(k+2)mod2 = viu+1F2i = F2(u+1) + viuF2i = F2u+2 + v+(k1j)mod2iuF2i1+kmod2 = F2u+2 + Fk Fj1+(k1j)mod2 = Fk+1 + Fk Fj1+(k1j)mod2 = Fk+2 Fj1+(k1j)mod2 = Fk+2 Fj1+(k+21j)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+(k1j)mod2iuF2i+1+kmod2 = Fk Fj1+(k1j)mod2.

If u = vk = j + 1,

v+(k1j)mod2iuF2i1+kmod2 = v+0iuF2i1+kmod2 = viuF2i1 = uiuF2i1 = F2u1 = F2u F2u2 = Fk F2v2 = Fk Fj1 = Fk Fj1+0 = Fk Fj1+(k1j)mod2.

Assuming

v+(k1j)mod2iuF2i1+kmod2 = Fk Fj1+(k1j)mod2,

we must show that

v+(k+21j)mod2iu+1F2i1+(k+2)mod2 = Fk+2 Fj1+(k+21j)mod2.

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

v+(k1j)mod2iu+1F2i1+(k+2)mod2 = v+0iu+1F2i1+(k+2)mod2 = viu+1F2i1 = F2(u+1)1 + viuF2i1 = F2u+21 + v+(k1j)mod2iuF2i1+kmod2 = F2u+1 + Fk Fj1+(k1j)mod2 = Fk+1 + Fk Fj1+(k1j)mod2 = Fk+2 Fj1+(k1j)mod2 = Fk+2 Fj1+(k+21j)mod2

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

Hence, in any and all cases

v+(k1j)mod2iuF2i+1+kmod2 = j2+(k1j)mod2ik2F2i+1+kmod2 = 2j2+2((k1j)mod2)+1+kmod2i2k2+1+kmod2Fi = Fk Fj1+(k1j)mod2.

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

Fk = F2u = 0iu1F2i+1 = 1iuF2i1 = 1iu (F2i+1 F2i) = 1iuF2i+1 1iuF2i = 1iuF2i+1 0iu1F2i+2 1iuF2i+1 1iu1F2i+1 1iuF2i+1 1iv+(k1j)mod21F2i+1 = v+(k1j)mod2iuF2i+1 = v+(k1j)mod2iuF2i+1+kmod2, ,

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

Fk = F2u+1 = 1 + 1iuF2i = 1 + 1iu (F2i+1 F2i1) = 1 + 1iuF2i+1 1iuF2i1 = 1 + 1iuF2i+1 0iu1F2i+1 = 1iuF2i+1 1iu1F2i+1 1iuF2i+1 1iv+(k1j)mod21F2i+1 = v+(k1j)mod2iuF2i+1 v+(k1j)mod2iuF2i+1+kmod2, ,

so that in either case,

Fk v+(k1j)mod2iuF2i+1+kmod2 = 2j2+2((k1j)mod2)+1+kmod2i2k2+1+kmod2Fi.

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

m < Fk 2j2+2((k1j)mod2)+1+kmod2i2k2+1+kmod2Fi = Fj1+(k1j)mod2 + Fk

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

Fj1+(k1j)mod2 = Fj1+0 = Fj1 1 2Fj;

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

Fj1+(k1j)mod2 = Fj1+1 = Fj 1 2Fj+1 1 2Fj.

And so, in either case,

Fj1+(k1j)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) = μ ( 1jrκ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 j1jrκ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 j1jrκFkκ,j qκ

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

2 j1jrκ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,21 = Fk1,r 11 > 2 r1jr1Fk1,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( 
                        "numberofchipsnmustben>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( 
               "numberofchipstakentmustbe1<=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("NumberofChips:%d%n", numberOfChips); 
      out.printf("GoesFirst:%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]UserTakes:"); 
      numberOfChipsTaken = options.readNumberOfChipsTaken(System.in, state.getNumberOfChipsTakeable()); 
   } else { 
      System.out.printf("[Input]ComputerTakes:"); 
      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) = k0akzk.

Then,

(1 z 6z2)G(z) = a 0z0 + (a 1 a0)z1 + k2(ak ak1 6ak2)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 ( k03kzk k0(2)kzk) = k01 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<nmax (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 Fm1. Then k + n k = n < Fm + Fm1 = 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 Fk11 + + Fkr1.

We may prove the equality.

Proposition. 1jrFkj+1 = ϕ1 + ϕ 1jrFkj if kj > kj+1 + 1 for 1 j < r and kr > 1.

Proof. Let

n = 1jrFkj

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

1jrFkj+1 = ϕ1 + ϕ 1jrFkj = ϕ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

1jrFkj+1 = 1jr (ϕ^kj + ϕFkj) = 1jrϕ^kj + 1jrϕFkj = 1jrϕ^kj + ϕ 1jrFkj = 1jrϕ^kj + ϕn = ϕn + 1jrϕ^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

3k k odd ϕ^k < 1jrϕ^kj 2k k even ϕ^k,

since 3k k odd ϕ^k is strictly less than 1jrϕ^kj given an infinite number of terms. But

3k k odd ϕ^k = 3k k odd (ϕ^k+1 ϕ^k1) = ϕ^31 = ϕ^2 = (ϕ^1 + ϕ^0) = ϕ^1 1 = ϕ1 1

and

2k k even ϕ^k = 2k k even (ϕ^k+1 ϕ^k1) = ϕ^21 = ϕ^1 = ϕ1.

so that

ϕ1 1 < 1jrϕ^kj ϕ1.

That is,

ϕ1 1 < 1jrϕ^kj ϕ1 ϕn + ϕ1 1 < ϕn + 1jrϕ^kj ϕn + ϕ1 ϕn + ϕ1 1 < 1jrFkj+1 ϕn + ϕ1 1jrFkj+1 = ϕn + ϕ1

as we needed to show. □

The formula for 1jrFkj1 is similar,

1jrFkj1 = ϕ1 + ϕ1 1jrFkj,

as shown below.

Proposition. 1jrFkj1 = ϕ1 + ϕ1 1jrFkj if kj > kj+1 + 1 for 1 j < r and kr > 1.

Proof. Let

n = 1jrFkj

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

1jrFkj1 = ϕ1 + ϕ1 1jrFkj = ϕ1n + ϕ1.

From exercise 11,

ϕ^kj = Fkjϕ^ + Fkj1 Fkj1 = ϕ^kj Fkjϕ^ Fkj1 = ϕ^kj ϕ^Fkj Fkj1 = ϕ^kj + ϕ1F kj.

Then

1jrFkj1 = 1jr (ϕ^kj + ϕ1F kj) = 1jrϕ^kj + 1jrϕ1F kj = 1jrϕ^kj + ϕ1 1jrFkj = 1jrϕ^kj + ϕ1n = ϕ1n + 1jrϕ^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

3k k odd ϕ^k < 1jrϕ^kj 2k k even ϕ^k,

since 3k k odd ϕ^k is strictly less than 1jrϕ^kj given an infinite number of terms. But

3k k odd ϕ^k = 3k k odd (ϕ^k+1 ϕ^k1) = ϕ^31 = ϕ^2 = (ϕ^1 + ϕ^0) = ϕ^1 1 = ϕ1 1

and

2k k even ϕ^k = 2k k even (ϕ^k+1 ϕ^k1) = ϕ^21 = ϕ^1 = ϕ1.

so that

ϕ1 1 < 1jrϕ^kj ϕ1.

That is,

ϕ1 1 < 1jrϕ^kj ϕ1 ϕ1n + ϕ1 1 < ϕ1n + 1jrϕ^kj ϕ1n + ϕ1 ϕ1n + ϕ1 1 < 1jrFkj1 ϕ1n + ϕ1 1jrFkj+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 = 1jrFkj and n = 1jrFkj+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 = 1jrFkjn = 1jrFkj+1.

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

mFN1 + nFN = 1jrFkjFN1 + 1jrFkj+1FN = 1jr(FkjFN1 + Fkj+1FN) = 1jrFkj+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

1jrFkj

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

|mϕ^N1 + 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ϕ^N1 + nϕ^N| < ϕ2 ϕ2 < mϕ^N1 + nϕ^N < ϕ2 ϕ1 1 < mϕ^N1 + nϕ^N < ϕ2 ϕ1 1 < mϕ^N1 + nϕ^N ϕ1 ϕ (mFN1 + nFN) + ϕ1 1 < ϕ (mFN1 + nFN) + (mϕ^N1 + nϕ^N) ϕ (mFN1 + nFN) + ϕ1 ϕ (mFN1 + nFN) + (mϕ^N1 + nϕ^N) = ϕ (mF N1 + nFN) + ϕ1.

Then

mFN + nFN+1 = m (ϕFN1 + ϕ^N1) + n (ϕF N + ϕ^N) by exercise 21 = mϕFN1 + mϕ^N1 + nϕF N + nϕ^N = ϕ (mFN1 + nFN) + (mϕ^N1 + nϕ^N) = ϕ (mFN1 + nFN) + ϕ1 = 1jrFkj+N+1. by exercise 41

Finally, setting N = 1 yields

mF1 + nF1+1 = m + nF0 = m + 0 = m = 1jrFkj1+1 = 1jrFkj,

and setting N = 0 yields

mF0 + nF0+1 = 0 + nF1 = n = 1jrFkj+0+1 = 1jrFkj+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 = 1jrFkjn = 1jrFkj+1,

as we needed to show. □

______________________________________________________________________________________________________________________________

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