Negabonacci Numbers

Reading an old Brian Hayes' column got me thinking: what happens to the Fibonacci recurrence

F.0 = F.1 = 1
F.n = F.(n-1) + F.(n-2)

when some of the terms are subtracted instead of added? If every term is subtracted we get something not very exciting, namely, the negative Fibonacci numbers. If, however, some terms are added while some others are subtracted, I thought, maybe the result would be more interesting. I settled on two possibilities:

T.0 = T.1 = 1
T.n = (-1)n·T.(n-1) + T.(n-2)

and

U.0 = U.1 = 1
U.n = U.(n-1) + (-1)n·U.(n-2)

Generating some of the terms readily revealed some patterns:

n	F.n	T.n	U.n	(-1)n
0	1	1	1	+
1	1	1	1	-
2	2	2	2	+
3	3	-1	1	-
4	5	1	3	+
5	8	-2	2	-
6	13	-1	5	+
7	21	-1	3	-
8	34	-2	8	+
9	55	1	5	-
10	89	-1	13	+
11	144	2	8	-
12	233	1	21	+
13	377	1	13	-
14	610	2	34	+
15	987	-1	21	-

The first striking thing is that T.n seems to take only a limited number of values. Indeed, a simple computer experiment shows that:

tau[0] = 1; tau[1] = 1;
tau[n_Integer] := tau[n] = (-1)^n tau[n - 1] + tau[n - 2]

Table[tau[i], {i, 0, 20}]
  {1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2, 1, 1, 2, -1, 1, -2, -1, -1, -2}

and the hypothesis is that T.n has period 12: T.(n+12) = T.n. There are essentially three strategies to prove this:

1. Show that |T.(n+3)| = |T.n| and that sgn.(T.(n+6)) = -sgn.(T.n), that is, the sequence of absolute values has period 3 while the signs alternate every 6 terms. Then, the overall period of the sequence must be 12
2. Expand successively T.(n+12), applying the recursive definition and simplifying
3. Calculate successively T.(n+2), T.(n+3), … T.(n+12) and show that the last is indeed T.n

Addendum: As an anonymous commenter remarks, there is an obvious (that is, if you wouldn't let yourself get sidetracked by pretty patterns as I apparently was) strategy: use induction. You can read all of it in the comments, but the insight that a finitely-generated recurrence needs as many base cases for induction as there are in the recurrence is all that it is needed: Assume that m < n with m ≡ n (mod 2); then T.m = T.n ∧ T.(m+1) = T.(n+1) ⇒ T.(m+k) = T.(n+k), for k ≥ 0. A simple expansion of the recurrence on both sides of the equality shows that, if both m and n have the same parity, the signs of the first terms are the same and hence, by an appeal to induction, the equality stands.

While I concede that this proof could hardly be simpler, I derive no great insight from it other than, indeed, the recurrence is periodic; what I proved originally gives me the terms of all such sequences obtained by freely choosing the original terms A, B.

Proving (1) is no easier than proving (2) or (3). Setting myself to prove (2), I quickly realized that the process would be exceedingly tedious. I used Mathematica to assist me:

taurule = tau[n_ + i_Integer] :>
  (-1)^(n + i) tau[n + (i - 1)] + tau[n + (i - 2)] /; i ≥ 2;

FullSimplify[tau[n + 12] //. taurule, n ∈ Integers && n ≥ 2]

where //. (or ReplaceRepeated) repeatedly applies the reduction rule until the expression doesn't change anymore. After a while, Mathematica computes the result tau[n], proving the theorem mechanically.

After some thought, I realized that even if the top-down approach is tedious to perform by hand, a bottom-up calculation can be done in at most twelve steps since the theorem is indeed true. Call A = T.n, B = T.(n+1), s = (-1)ⁿ (and note that s² = 1). Then:

1. T.(n+2) = (-1)ⁿ⁺² T.(n+1) + T.n = s·B + A, by definition
2. T.(n+3) = -s·T.(n+2) + T.(n+1) = -s·A

   This establishes the first lemma needed to prove the theorem.

3. T.(n+4) = s·T.(n+3) + T.(n+2) = s·B
4. T.(n+5) = -s·T.(n+4) + T.(n+3) = -s·A - B
5. T.(n+6) = s·T.(n+5) + T.(n+4) = -A

   This establishes the second lemma needed to prove the theorem. There is no need to proceed further, but for completeness, these are the next steps:

6. T.(n+7) = -B
7. T.(n+8) = -s·B - A
8. T.(n+9) = s·A
9. T.(n+10) = -s·B
10. T.(n+11) = s·A + B
11. T.(n+12) = A

Hence, at any point, the sequence has the shape:

…A, B, s·B + A, -s·A, s·B, -s·A - B, -A, -B, -s·B - A, s·A, -s·B, s·A + B, A…

where s is +1 or -1, depending on where the subsequence starts.

What about U.n? Well, it seems that it is just two interleaved copies of F.n. Indeed:

U.(2·k)     = F.(k+1)
U.(2·k+1) = F. k

And this is quite simple to prove by induction. First, note that U.0 = 1 = F.1 and U.1 = 1 = F.0, establishing the base case. For the inductive step:

U.(2·k+1) = U.(2·k) + (-1)2·k+1 U.(2·k-1)
             = F.(k+1) - F.(k - 1)
             = F.k + F.(k - 1) - F.(k - 1)
             = F.k
U.(2·k)     = U.(2·k-1) + (-1)2·k U.(2·k-2)
             = F.(k-1) + F.(k)
             = F.(k+1)

where the second step for each case is justified inductively by an appeal to the opposite case.