Next: k-Fibonacci numbers (this year) Up: Fibonacci Numbers (last year) Previous: Definitions   Contents

## Theorems

Theorem 1   The Fibonacci sequence is periodic in any modulo.

Consider the Fibonacci sequence in mod : . Now, consider the pairs of consecutive Fibonacci numbers (for example , , etc.). Since we are in mod , there are only possible distinct such pairs (since there are choices for the first number in a pair and choices for the second number in a pair). If is one such pair, then the whole sequence must be in mod , which contradicts the initial conditions of the sequence, so there are only possible distinct pairs. Since the Fibonacci sequence is infinite, there are an infinite number of pairs, so by the Pigeonhole Principle, at least one of these pairs must repeat. Suppose that the pairs and are the same (that is, and ). WLOG (without loss of generality), let . Then, we know that and , so . We can continue this until we find that and , so . So, we can continue this in the other direction and find that the Fibonacci sequence is periodic.

Theorem 2   , for all .

Done by weak mathematical induction on .

Base Case: Want To Show(WTS): .

Since , so .

Induction Step: Assume , .

WTS: .

By the definition of the Fibonacci sequence, we know that . So, . Then, . Also, . Notice that the coefficients of and are being generated recursively with the same formula as the Fibonacci numbers, so we can say that if . So, we can substitute for to say that . Now, since we know that (by hypothesis), then for some . So, we can substitute to get . Now, we can factor out an to say . So, by definition of divides, , and since , then , which is what we wanted to show.

Theorem 3   If , then .

Done by strong mathematical induction on .

Base Case: or . WTS: .

For , we want to show that . Since we know that and (by definition), so , and . For , we want to show that . By the definition of the Fibonacci sequence, , so . Since , then . Since , we can multiply to get that , which is what we wanted to show.

Induction Step: Assume , such that .

WTS: .

Since and , we can say that and . We can add these equations together to say that . Factoring, we get that . Since and , we can substitute to say that , which is what we wanted to show.

Theorem 4   .

We will prove this by weak mathematical induction on .

Base Case: . WTS: .

Since and and , then , which is what we wanted to show.

Induction Step: Assume .

WTS: .

Since , by Fact 10, . So, by the definition of the Fibonacci sequence, , which is what we wanted to show.

Theorem 5   If , then .

Let . Divide by (by Fact 4) to get , where . So, . Since , then . Since (by definition of , then , and since (by Theorem 2), then , so . So we can apply Theorem 3 to say that . Since , so . By Theorem 4, . Since , then by Fact 7, . Since , then by definition of , it follows that . So, by Fact 7, . Now, since , then by Fact 14, . So, if , then satisfies the definition of and is less than , which is a contradiction. So, must be equal to , so , so , so .

Theorem 6   If , then .

To show this we are going to show that satisfies the definition of .

Part 1: WTS: .

Let and and . Since , then and , where (by definition of LCM). So, and . Also, and by definition of and , so and . So, by Theorem 2, and . Since , by Fact 8, , so , so , which is what we wanted to show.

Part 2: WTS: If , then .

Let and and . Since , then and , where (by definition of LCM). Since , then , so and . So, and . Now, by Theorem 5, and . So, by definition of LCM, , so (by Theorem 3). So, , which is what we wanted to show, so we are done.

Theorem 7   If , then , .

Done by weak mathematical induction on .

Base Case: . WTS: .

Since , then , which is what we wanted to show.

Induction Step: Assume .

WTS: .

Note that . Now, since , we can apply Theorem 3 to say that . By hypothesis, , so we can substitute to get , which means that , which is what we wanted to show.

Theorem 8

Since , then . Since and (by definition of ), then . Now, by Theorem 7, (since ). Also, by Theorem 3. So, we can substitute to say that , so , which is what we wanted to show.

Theorem 9   If and , then .

Let . Divide by to get , where and . Since , then , so (by Theorem 8). Since , then , so (by Theorem 8). If , then satisfies the definition of , but is smaller than (since ), which is a contradiction. So, , and , so .

Theorem 10   If and and , then .

and , so and for some . So, and , and since , then (by Fact 8). So, . Now, since and , then and for some . So, and , and since , then (by Fact 8). So, . By Theorem 9, .

Theorem 11   If , then .

We will show this by showing that and . and (by definition of LCM), and since , then (by Theorem 10). and , so and by Fact 16, so by Theorem 9, . Since and , so and by Fact 16, so by Theorem 9, . So, by definition of LCM, . Since and , by Fact 15, .

by definition of , so by Theorem 5.

Let , so (by definition). By Theorem 4, , so for some , so by Theorem 7, . Therefore, exists, so exists. Now, if we find that the first directly before a is in position number , then , since and . So, we must examine position numbers , since all zeroes are in position numbers (by Theorem 5). Now, by Theorem 7, (since by definition of ). So, we are looking for the first such that . By definition, this is . So, , or .

Theorem 14   for all .

Done by weak mathematical induction on .

Base Case: . WTS:

Since , , , , and , and , we conclude that the theorem is true for .

Induction Step: Assume .

WTS: .

We can rearrange our assumption to say that , which is the same thing as . We can add to both sides to get and factor to get and simplify to say that , which is what we wanted to show.

Theorem 15   for all .

Done by weak mathematical induction on .

Base Case: . WTS: .

Since , , , and , and , we conclude that the theorem is true for .

Induction Step: Assume .

WTS: .

We can add to both sides to find that , or , which is the same as . By Theorem 14, this reduces to , which is the same as , which is what we wanted to show.

Theorem 16   , for all .

First, by Theorem 4, so exists. By Theorem 15, , so . If is even, then , so . If is odd, then , so , so .

Theorem 17   , for all .

First, we notice that , since and all Fibonacci numbers before this are less than , so they cannot be congruent to . So, . Now, since (by Theorem 16), then we can apply Theorem 13 to say that .

Next: k-Fibonacci numbers (this year) Up: Fibonacci Numbers (last year) Previous: Definitions   Contents
Gregory Stoll 2000-04-08