Done by weak mathematical induction on
Base Case: Want To Show(WTS): .
Since , so
.
Induction Step: Assume ,
.
WTS:
.
By the definition of the Fibonacci sequence, we know that
. So,
.
Then,
. Also,
. Notice that the coefficients of
and
are being generated recursively with the same formula as the Fibonacci numbers,
so we can say that
if
. So,
we can substitute
for
to say that
. Now, since we know that
(by hypothesis), then
for some
. So, we
can substitute to get
. Now, we can
factor out an
to say
. So, by
definition of divides,
, and since
, then
, which is what we wanted to show.
Done by strong mathematical induction on
Base Case: or
. WTS:
.
For , we want to show that
.
Since we know that
and
(by definition), so
, and
. For
,
we want to show that
. 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 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.
We will prove this by weak mathematical induction on
Base Case: . WTS:
.
Since and
and
, then
, which is
what we wanted to show.
Induction Step: Assume
.
WTS:
.
Since
, by Fact 10,
. So, by the definition of the Fibonacci sequence,
, which is what we wanted to show.
Let
To show this we are going to show that
Part 1: WTS:
.
Let and
and
. Since
, then
and
, where
(by definition of LCM). So,
and
. Also,
and
by
definition of
and
, so
and
. So, by Theorem
2,
and
. Since
, by Fact 8,
, so
, so
,
which is what we wanted to show.
Part 2: WTS: If
, then
.
Let and
and
. Since
, then
and
, where
(by definition of LCM). Since
, then
, so
and
. So,
and
. Now, by Theorem
5,
and
. So, by definition of LCM,
, so
(by Theorem 3). So,
, which is what we wanted to show, so we are done.
Done by weak mathematical induction on
Base Case: . WTS:
.
Since
, then
, which is what we wanted to show.
Induction Step: Assume
.
WTS:
.
Note that
. Now, since
, we can apply Theorem 3 to say that
. By hypothesis,
, so we can substitute to get
, which means that
, which is what we wanted to show.
Since
Let
We will show this by showing that
and
.
and
(by definition of LCM), and since
, then
(by Theorem 10).
and
, so
and
by Fact
16, so by Theorem 9,
. Since
and
, so
and
by Fact
16, so by Theorem 9,
. So, by
definition of LCM,
. Since
and
,
by Fact 15,
.
Let
Done by weak mathematical induction on
Base Case: . WTS:
Since ,
,
,
, and
, and
, we conclude that the theorem is true for
.
Induction Step: Assume
.
WTS:
.
We can rearrange our assumption to say that
, which is the same thing as
. We can add
to
both sides to get
and factor to get
and
simplify to say that
, which is what
we wanted to show.
Done by weak mathematical induction on
Base Case: . WTS:
.
Since ,
,
, and
, and
,
we conclude that the theorem is true for
.
Induction Step: Assume
.
WTS:
.
We can add
to both sides to find that
,
or
, which is
the same as
. By Theorem
14, this reduces to
, which is the same as
, which is what we wanted to show.
First,
First, we notice that