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

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

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

**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 , then . Since and (by definition of ), then . Now, by Theorem 7, (since ). Also, by Theorem 3. So, we can substitute to say that , so , which is what we wanted to show.

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

by definition of , so by Theorem 5.

Let , so (by definition). By Theorem 4, , so for some , so by Theorem 7, . Therefore, exists, so exists. Now, if we find that the first directly before a is in position number , then , since and . So, we must examine position numbers , since all zeroes are in position numbers (by Theorem 5). Now, by Theorem 7, (since by definition of ). So, we are looking for the first such that . By definition, this is . So, , or .

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

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