## Theorems

Crucial Note: In this section, we will only consider such that and - otherwise, and are not guaranteed to exist.

Theorem 41   The generalized -Fibonacci numbers are periodic in any modulo.

Consider the generalized -Fibonacci sequence in mod : . Now, consider the pairs of consecutive generalized -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 since , has a unique solution) and (and since , has a unique solution), so . We can continue this until we find that and , so . So, we can continue this in the other direction and find that the generalized -Fibonacci sequence is periodic.

Theorem 42   If , then .

Done by strong mathematical induction on .

Base Case: . WTS: .

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 multiply the first by and the second by to 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 43   If , then .

Let be the integer such that (this is guaranteed to exist by the definition of divides). Now we will use weak mathematical induction on .

Base Case: . WTS: .

This follows from the definition of .

Induction Step: Assume .

WTS: .

Since (given), we can apply Theorem 42 to say that . Since (by the definition of , we can say that . Simplifying, we get that , which is what we wanted to show.

Theorem 44   If , then .

Let . Divide by to get , where . So, . Since , then . By Theorem 43, . So we can apply Theorem 42 to say that . Now, since , we can say that . Since , by Fact 14 we know that . Now, assume for the sake of contradiction that , where and . So, and . Now, since (by Theorem 43), then , and since , then . Now, we notice that divides 2 consecutive terms of the generalized -Fibonacci sequence, and since this sequence is determined by 2 consecutive terms, all terms past these 2 in the sequence must be divisible by . Now, consider the th term, where . So, by the previous argument, . So, , since is a common factor, and since , then , or . Now, we can take the contrapositive of Fact 6 to say that if does not divide , then there do not exist integers and such that , so we know that there do not exist integers and such that , so is not congruent to . Now we have shown this for all such that - but this is a contradiction to the fact that the generalized -Fibonacci sequence is periodic! So, we reject our hypothesis, and conclude that . Then, by Fact 14, . Now, we know that . If , then we have a contradiction to the definition of (since , but satisfies the definition of ). Thus, we reject that case, and conclude that . Thus, , which means that , or .

Theorem 45   If , then , .

Done by weak mathematical induction on .

Base Case: . WTS: .

Since , then since , we know that , or , which is what we wanted to show.

Induction Step: Assume .

WTS: .

Note that . Now, since , we know by Theorem 42 that . Now, by the given, , so we can substitute to get . We can simplify this to say that , which is what we wanted to show.

Theorem 46

Since , then . If we let be an integer such that ( exists by the fact that and Fact 13), then we can say that . Since (by definition of we can simplify this to . We know that by the definition of , so we can substitute to say that . Now, by Theorem 45, (since ), which means that , or . Now, we can work backwards using the ideas from the preceding steps to determine that . Also, by Theorem 42. So, we can substitute to say that , and since we defined such that , we conclude that , which is what we wanted to show.

Theorem 47   If and , then .

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

Theorem 48   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 47, , which is what we wanted to show.

Theorem 49   If , then .

and (by definition of LCM), and since , then (by Theorem 48). and , so and by Fact 16, so by Theorem 47, . Since and , so and by Fact 16, so by Theorem 47, . So, by definition of LCM, . Since and , by Fact 15 .