---
tags: mth225, 225-spr22, aep
---

# AEP 6: Mathematical induction

## Overview

This AEP is focused on giving you the opportunity to demonstrate skill not only with setting up a framework for a proof by mathematical induction, but also (if you choose) to try writing an actual proof.

## Special features of AEP 6

Since we are so close to the end of the course and have limited opportunities for timed quizzing, this AEP is going to serve two purposes. First, it is a regular AEP that can be completed for credit in terms of your course grade. But second: **earning a mark of "M" or "E" on this AEP will count as a "successful demonstration of skill" on Learning Target 21.** That is, earning M or E on this assignment counts like a successful quiz problem on Learning Target 21 in addition to counting toward the AEP requirement for a B or A in the course.

## Tasks for this AEP

Below, there are four statements that can be proven using mathematical induction. Choose one of the following two options for how to proceed with this assignment:

**Option 1:** Choose **one** (1) of these statements and give a complete, clearly-stated framework for the proof, **then write out a completed proof for it.** If you choose this option, you'll need to do the following:
- Write up the framework and the proof in different sections of your writeup, to keep them separated.
- The framework needs to follow the specifications stated below in Option 2 for frameworks.
- Your proof needs to be clearly written, mathematically correct, and neatly written up (excessively messy or disorganized writing will need to be revised even if the math and logic are correct!), and your proof must follow the framework you set up. (I.e. you should just be filling in the details of your framework and then making it all look nice in a narrative format.)

**Option 2:** Choose **two** (2) of the statements and **give a complete, clearly-stated framework of an induction proof for each statement you chose**. A completed proof is not necessary; just two well-constructed frameworks. Satisfactory work on a framework for an induction proof means:
- The base case is correct, clearly stated, and proven. (In other words you *do* need to actually prove the base case.)
- The induction hypothesis is clearly stated in specific terms, using the predicate in the statement. It should begin with "Assume that..." and then state clearly and specifically what needs to be assumed.
- The framework clearly states what needs to be proven once the induction hypothesis is stated. This should begin with "We want to prove that..." and then state clearly and specifically what needs to be proven next. Then, to finish, give an outline of how the proof might proceed. Again you do *not* need to give a completed proof (if you think you can do a completed proof, you should consider Option 1!) but you do need to state in specific terms what you might do in a completed proof.

For examples of good frameworks and completed proofs, you can consult our class work from Week 6, particularly the Miro boards and Perusall activities. You should particularly work together on the Perusall activities to construct good examples of completed frameworks and proofs --- the more effort you give there, the better examples everyone has.

### Statement 1

For every integer greater than $6$, $3^n < n!$.

### Statement 2

For every natural number $n$, $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n} = 2^n$.

### Statement 3

Suppose $n$ is a positive integer and $A_1, A_2, A_3,
\dots, A_n$ and $B$ are sets. Then
$$(A_1 \cap A_2 \cap A_3 \cap \dots \cap A_n) \cup B = (A_1 \cup B) \cap (A_2 \cup B) \cap (A_3 \cup B) \cap \dots \cap (A_n \cup B)$$

### Statement 4

Denote the $i$th Fibonacci number by $F_i$ with $i = 1, 2, ...$ so that $F_1 = 1, F_2 =1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8,$ and so on. Remember these are defined by the recurrence relation $F_1 = 1, F_2 = 1$ and for $n > 2$ we have $F_n = F_{n-1} + F_{n-2}$.

Claim: For all integers $n \geq 2$, $F_{2n} = \left( F_{n+1} \right)^2 - \left( F_{n-1} \right)^2$

## Expectations and Grading Criteria

AEPs are graded using the "EMRN" rubric found in the syllabus. Make sure you review the [Standards for Assessments in MTH 225](/KoT83ezHRYO3DqPyXMMMag) document before you submit any work, so you're fully aware of the expectations for the different marks. In particular:

- All work needs to be shown *and* your thought processes clearly expressed in all of the tasks of the assignment. The results also need to be correct. You are not just doing math; you are explaining things to a reader, so a mix of math and English is needed.
- All the information needed for an "outsider" to understand your work needs to be self-contained within the work. **The reader should not have to do any work to fill in gaps.**

Please note, it is the case with all AEP's that **your grade is primarily based on your explanations and writing, and only secondarily on the precision and correctness of your computations.** Correct computations with insufficient explanation will need to be revised and may receive an "N" grade.

A grade of "E" is given if all of the above expectations are met, and the work is of superior quality in terms of the clarity of explanations and work, appearance of the writeup, and precision of the mathematics.

## Submitting your work

**AEP submissions must be typewritten and saved as either a PDF or MS Word file. No part of your submission may involve handwriting; work that is submitted that contains handwriting will be graded N and returned without feedback.** This includes electronic handwritten docments, for example using a stylus and a note-taking app. To type up your work, you can use MS Word or Google Docs (both of which have equation editors for mathematical notation) or any other computer-based math typesetting tool. Just make sure you save your work as a Word document or PDF (no `.odt`, `.rtf`, or other file extensions are allowed).

When you have your work typed up, double-check it for neatness, correctness, and clarity. Then simply submit your document on Blackboard, in the **AEP** area, in the **AEP 6** assignment.

## Getting Help

You **may** ask me (Talbert) for help on this assignment in the form of **specific mathematical or technical questions, or clarifying questions about the instructions**. If I cannot answer a question because it would give too much away, I'll tell you so. However please note: **I will not "look over your work" before you submit it to give you feedback on the overall submission**. I have made the expectations clear, so just follow those directions and submit your best work, and you'll be allowed to revise it if needed.

For AEPs, the syllabus policy on collaboration is:

>**No collaboration is allowed at all** — with other people, or with print or electronic sources other than your textbook, the video playlist, or your notes.

**You can ask technology related questions to anyone at any time**. For example if you need help figuring out how to type up your work, there are no restrictions on that.