Next: Generalized a,b-Fibonacci numbers (this Up: k-Fibonacci-q numbers and new Previous: Definitions   Contents

## Theorems

Theorem 35   For all , .

Done by strong mathematical induction on .

Base Case: . WTS: .

If , then and . Otherwise, , so and , so all cases are true.

Induction Step: Assume for all , that .

WTS: .

We can add the given from to to get that , or that . By the definition of the sequences, these collapse to , which is what we wanted to show.

Theorem 36   If and , then for all .

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

Part 1: WTS: .

This is a property included in the definition of .

Part 2: WTS: For all between and , inclusive, .

Let be between and , inclusive. By the definition of , . Thus, by Theorem 35, (since by definition of ), which is what we wanted to show.

Part 3: WTS: .

By the definition of , . Thus, by Theorem 35, , which is what we wanted to show.

Part 4: WTS: If and and for all such that , it follows that and also , then .

First, note that since , then by Fact 5, there exists integers and such that , so , so (by the definition of mod). Now, let , so by Theorem 28, , so, multiplying both sides by , we find that , or . Now, since , then , or . Similarly, , and . Now by Theorem 24, , so by Fact 3, , which is what we wanted to show.

Theorem 37   If , then iff .

Part 1: WTS: If and , then .

By Theorem 35, , so . Since , then , or , which is what we wanted to show.

Part 2: WTS: If and , then .

By Theorem 35, , so . Since , then . Since , by Fact 14 , which is what we wanted to show.

Theorem 38   If , then .

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

Part 1: WTS: .

This is a property in the definition of .

Part 2: WTS: For all between and , inclusive, .

Let be between and , inclusive. We know that , since this is a property in the definition of . So, since , by Theorem 37, , which is what we wanted to show.

Part 3: WTS: If, for all between and , inclusive, it follows that and , then .

Let be between and , inclusive. Since , by Theorem 37, . So, this is true for all between and , so by the definition of , it follows that , which is what we wanted to show.

Theorem 39   If , then .

By Theorem 36, . By Theorem 37, the positions of the zeros in the -Fibonacci sequence and the -Fibonacci- sequence are exactly the same, so by the definition of , it follows that .

This will be proven by a construction. First, write down all -Fibonacci- sequences from the 1st term to the term modulo such that and . Note that the number of such sequences is just . Now, by Theorem 36, each of these sequences is the same length, and by Theorem 37, all positions that have consecutive s will start at the same position in every sequence. Now, consider terms whose position is of the form , where or . These terms will be denoted by " terms". By Theorem 38, these will all be after the only places that have consecutive s in their sequences, and by Theorem 39, there will be the same number of terms in each sequence. Now, we start with the first sequence and look at all terms in that sequence. Then, we will search for a sequence in which any term is equal to any term in the first sequence. Now, assume there is a term in the th line that is equal to some term in the th line. Since all -Fibonacci- sequences are determined by consecutive terms (like the -Fibonacci sequence), and all terms are preceded by s, we can say that these two sequences are in fact the same sequence shifted by terms, where is some integer. So, all terms in the sequences will be the same. Therefore, we can eliminate or cross out one of these sequences, while still keeping all numbers that were terms. Continue this until there are no more duplicate terms left. Now, we will show that all terms in all -Fibonacci- sequences (where ) are relatively prime to . First, looking back at the proof of Theorem 27, we established that (since exists). Now, Theorem 20 states that if, for all between and , inclusive, it follows that , then . We can plug in for in this formula to say that . Now, since we know that , by Fact 12 we can say that for all . We can reduce this to say that for all , which says that every term in the -Fibonacci sequence is relatively prime to . Now, since we are considering every -Fibonacci- sequence such that , by Fact 11 we can say that . By Theorem 35, these are just the terms in all of the -Fibonacci- sequences, so all terms in every sequence listed are relatively prime to . Notice that every sequence starts with a term, and since the first term of every -Fibonacci- sequence is just , we have started with all relatively prime numbers less than . Every time we eliminate a sequence, there is still at least 1 copy left of every number relatively prime to and less than , since there are 2 copies of the same term in each sequence, and only 1 is removed. If there is more than 1 copy left, we eliminate one of the sequences, so after we are finished there is exactly 1 and only 1 copy of every number less than and relatively prime to . Now, we will count the number of terms left in 2 different ways. By the definition of , there are exactly terms left. Also, since every sequence of consecutive s in each sequence corresponds to a term (the s ending in the position correspond to the term in the first position), and there are sequences of consecutive s in every sequence, we can say that there are terms, where is the number of sequences left. So, , or by the definition of divides.

Next: Generalized a,b-Fibonacci numbers (this Up: k-Fibonacci-q numbers and new Previous: Definitions   Contents
Gregory Stoll 2000-04-08