Proof by mathematical induction Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What are the four parts of an induction proof?
- Basis (), assumption (), inductive step () and conclusion.
- What do you assume in the inductive step?
- That the statement is true for .
- What must you prove in the inductive step?
- That the statement is true for .
- Write a full conclusion for an induction proof.
- True for , and if true for then true for , so true for all positive integers by mathematical induction.
- First move in the inductive step for ?
- , then substitute the assumed formula.
- How do you prove is divisible by ?
- Show is divisible by , then show (or in terms of ) is a multiple of .
- For , what is in terms of ?
- How do you prove a formula for given ?
- Check , assume equals the formula, and substitute it into .
- How do you prove a formula for ?
- Show , assume for , then multiply .
- Why is the basis case essential?
- It starts the chain; without it the step proves nothing about any actual case.
- Why is the inductive step essential?
- It links each case to the next, so the truth of passes to every .
- Where do you write the target of the proof?
- At the start of the step, as with replaced by , so you know what to reach.