Next: k-Fibonacci-q numbers and new Up: Fibonacci-q numbers and new Previous: Definitions   Contents

## Theorems

Theorem 28   For all , .

Done by strong mathematical induction on .

Base Case: and . WTS: and .

Since and and , both of these are true.

Induction Step: Assume and .

WTS: .

We can add the two equations that we know together to get , or . Since and , we can substitute to get , which is what we wanted to show.

Theorem 29   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: .

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

Part 3: WTS: .

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

Part 4: WTS: If and and and , then .

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

Theorem 30   If , then iff .

Part 1: WTS: If and , then .

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

Part 2: WTS: If and , then .

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

Theorem 31   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: .

We know that , since this is a property in the definition of . So, since , by Theorem 30, , which is what we wanted to show.

Part 3: WTS: If and , then .

Since , by Theorem 30, . So, by the definition of , , which is what we wanted to show.

Theorem 32   .

First, note that exists by Theorem 12. Now, since , then for some . Now, let . By Theorem 2, , or . So, , and by Fact 16, . Thus, every position in the Fibonacci sequence of the form is congruent to . Also, by Theorem 5, if , where , then , which means that can be represented in the form . Thus, these positions in the Fibonacci sequence are the only ones that are congruent to . So, now we must count the number between and . Since they occur every places, and since (by Theorem 12), we conclude that there are such places in the Fibonacci sequence between and . Thus, .

Note that this implies that by Theorem 13.

Theorem 33   If , then .

By Theorem 29, . By Theorem 30, 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 29, each of these sequences is the same length, and by Theorem 30, all terms of value will be 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 31, these will all be after the only s in their sequences, and by Theorem 33, there will be the same number of them 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 2 consecutive terms (like the Fibonacci sequence), and all terms are preceded by a , 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 2 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 13, we established that . Since , we can say that . Now, Theorem 7 states that if , then . We can plug in for in this formula and notice that 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 28, these are just the terms in all of the Fibonacci- sequences, so all 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 in each sequence corresponds to a term (the in the position corresponds to the term in the first position), and there are 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: k-Fibonacci-q numbers and new Up: Fibonacci-q numbers and new Previous: Definitions   Contents
Gregory Stoll 2000-04-08