** Next:** About this document ...
** Up:** Generalized a,b-Fibonacci numbers (this
** Previous:** Definitions
** Contents**

**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.

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.

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.

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 .

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.

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.

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.

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.

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
.

** Next:** About this document ...
** Up:** Generalized a,b-Fibonacci numbers (this
** Previous:** Definitions
** Contents**
Gregory Stoll
2000-04-08