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:

- 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 - Expand successively T.(
`n`+12), applying the recursive definition and simplifying - 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, thereisan 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 thatm<nwithm≡n(mod 2); then T.m= T.n∧ T.(m+1) = T.(n+1) ⇒ T.(m+k) = T.(n+k), fork≥ 0. A simple expansion of the recurrence on both sides of the equality shows that, if bothmandnhave 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

isperiodic; what I proved originally gives me the terms ofallsuch sequences obtained by freely choosing the original termsA,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)^{n} (and note that `s`^{2} = 1). Then:

- T.(
`n`+2) = (-1)^{n+2}T.(`n`+1) + T.`n`=`s`·`B`+`A`, by definition - T.(
`n`+3) = -`s`·T.(`n`+2) + T.(`n`+1) = -`s`·`A`This establishes the first lemma needed to prove the theorem.

- T.(
`n`+4) =`s`·T.(`n`+3) + T.(`n`+2) =`s`·`B` - T.(
`n`+5) = -`s`·T.(`n`+4) + T.(`n`+3) = -`s`·`A`-`B` - 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:

- T.(
`n`+7) = -`B` - T.(
`n`+8) = -`s`·`B`-`A` - T.(
`n`+9) =`s`·`A` - T.(
`n`+10) = -`s`·`B` - T.(
`n`+11) =`s`·`A`+`B` - 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.kU.(2·k) = U.(2·k-1) + (-1)2·kU.(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.

## 5 comments:

ROFLMAO :)

1) T.n = T.m && T.(n + 1) = T.(m + 1) => T.(n + k) = T.(m + k) -- by induction

2) T.0 = T.12 && T.1 = T.13 -- by inspection

(1), (2) =>

3) T.(0 + k) = T.(12 + k)

QED

Oops...forgot to mention: in 1), we must also have m = n (mod 2), but that's true as well: 0 = 12 (mod 2)

You mean (1) of any recurrence

Twhatsoever, or of the specificTbeing discussed? If the latter, the induction step has as many base cases as the difference betweenmandn, which is precisely the point of the article...Nope.

The recurrent formula only looks back two values into the history, so you only have 2 base cases .I took the liberty of omitting the induction argument, as it was pretty straightforward and mostly obvious.

Thus, 1) is motivated by the observation that any such sequence is uniquely determined by its first two members, and extends this to sub-sequences, with the correction I posted later.

You are right, of course. I needed pen and paper to see it but it is ROFLMAO plain.

Post a Comment