Next: Generalized a,b-Fibonacci numbers (this
Up: k-Fibonacci-q numbers and new
Previous: Definitions
  Contents
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.
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.
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.
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.
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