Next: Fibonacci-q numbers and new Up: k-Fibonacci numbers (this year) Previous: Definitions   Contents

## Theorems

Theorem 18   The -Fibonacci sequence is periodic in any modulo for all .

Consider the -Fibonacci sequence in mod : . Now, consider the groups of consecutive Fibonacci numbers at a time (for example , , etc.). Since we are in mod , there are only possible distinct such pairs (since there are choices for each number, and there are numbers to choose). 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 , etc.). WLOG (without loss of generality), let . Then, we know that and , so . We can continue this until we find that and , etc., so . So, we can continue this in the other direction and find that the -Fibonacci sequence is periodic.

Theorem 19   If such that for all such that , it follows that , then for all .

Done by strong mathematical induction on .

Base Case: . WTS: .

By definition, , and since for all such that , it follows that , then , which is what we wanted to show.

Induction Step: Assume for all such that .

WTS: .

By definition, . By hypothesis, . By definition of the -Fibonacci sequence, .

Theorem 20   If, for all between and , inclusive, then , 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 for all such that , it follows that , we can apply Theorem 19 to say that . Now, , so we can substitute to get . By hypothesis, , so we can substitute to get , which means that , which is what we wanted to show.

Theorem 21   .

Done by strong mathematical induction on .

Base Case: . WTS: .

By definition of , this is true.

Induction Step: Assume for all such that .

WTS: .

Since we know the induction step is true for all such that , we can take the sum of each side as goes from to to say that , which is the same as saying (by definition of the -Fibonacci sequence), which is what we wanted to show.

Theorem 22   If , then .

Done by weak mathematical induction on .

Base Case: . WTS: .

By Theorem 21, this is true.

Induction Step: Assume .

WTS: .

(by arithmetic). So, by assumption, , and by transitivity, . Now, by Theorem 21, , so by transitivity, , which is what we wanted to show.

Note that from this theorem, the corollary that if , then follows trivially.

Theorem 23   If for all between and , inclusive, it follows that , then .

First, divide by to get , where and . Now, for the sake of contradiction, assume that . So, . Now, for all , then (by Theorem 19). Now, for each such that , then for some such that (since ). So, . Also, (by assumption). So, by definition of , it follows that . But we already know that , so this is a contradiction. So, we reject our hypothesis and conclude that , so , so .

Theorem 24   If for all such that it follows that and also , then .

First, divide by to get , where and . Now, for the sake of contradiction, assume that . So, . Now, for all , then (by Theorem 22). Now, for each such that , then for some such that (since ). So, . Also, , and (by assumption). So, since satisfies the definition of , it follows that . But we already know that , so this is a contradiction. So, we reject our hypothesis and conclude that , so , so .

Theorem 25   If and and , then .

and , so and for some . So, and , and since , then (by Fact 8). So, . We can make this same argument to show that for all such that , then . Now, since and , then and for some . So, and , and since , then (by Fact 8). So, . Thus, by Theorem 24, .

Theorem 26   If , then .

We will prove this by showing that satisfies the definition of .

Part 1: WTS: .

By the definition of LCM, .

Part 2: WTS: For all such that , it follows that .

Let , so WTS that for all such that , it follows that . Now, since , we know that and for some . Since and and are positive, we also know that and , so . So, by Theorem 22, we can say that for all , . Similarly, for all , . Thus, for all , , and for all , . Now, if we let and take on all integral values between and (inclusive), we find that for all such that , , and . Now, since and are between and , and by Part 2 of the definition of , we can conclude that, for all such that , then and . Thus, by Theorem 25, for all such that , then .

Part 3: WTS: .

Since , then it follows that . Similarly, . So, by the corollary to Theorem 22, and . Thus, and , so and . Since (which was given), we can use Fact 8 to say that . So, , and thus , which is what we wanted to show.

Part 4: WTS: If there exists an such that for all such that , it follows that , and , then .

Since for all such that , it follows that , then we can say that for all such that , it follows that (by Fact 16. Also, since , then (by Fact 16). Thus, by Theorem 24, . Similarly, . So, by the definition of LCM, , and by Fact 3, , which is what we wanted to show.

Let , so (by definition). Since for all between and , inclusive, (by definition of ), we know that . Now, if we find that the first directly after s is in position number , then , since and there are s preceding that term, which satisfies the definition of . So, we must examine position numbers , since all sequences of s end in position numbers (by Theorem 23). Now, by Theorem 20, . So, we are looking for the first such that . By definition, this is . So, , or .

Next: Fibonacci-q numbers and new Up: k-Fibonacci numbers (this year) Previous: Definitions   Contents
Gregory Stoll 2000-04-08