Proof by mathematical induction

Proof by mathematical induction Flashcards

Spec 8.1 · Edexcel International A Level Further Maths: 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 (n=1n=1), assumption (n=kn=k), inductive step (n=k+1n=k+1) and conclusion.
What do you assume in the inductive step?
That the statement is true for n=kn=k.
What must you prove in the inductive step?
That the statement is true for n=k+1n=k+1.
Write a full conclusion for an induction proof.
True for n=1n=1, and if true for n=kn=k then true for n=k+1n=k+1, so true for all positive integers nn by mathematical induction.
First move in the inductive step for ∑r=1nf(r)\sum_{r=1}^{n}f(r)?
∑r=1k+1f(r)=∑r=1kf(r)+f(k+1)\sum_{r=1}^{k+1}f(r)=\sum_{r=1}^{k}f(r)+f(k+1), then substitute the assumed formula.
How do you prove f(n)f(n) is divisible by mm?
Show f(1)f(1) is divisible by mm, then show f(k+1)−a f(k)f(k+1)-a\,f(k) (or f(k+1)f(k+1) in terms of f(k)f(k)) is a multiple of mm.
For f(n)=7n−1f(n)=7^n-1, what is f(k+1)f(k+1) in terms of f(k)f(k)?
f(k+1)=7f(k)+6f(k+1)=7f(k)+6
How do you prove a formula for unu_n given un+1=g(un)u_{n+1}=g(u_n)?
Check n=1n=1, assume uku_k equals the formula, and substitute it into uk+1=g(uk)u_{k+1}=g(u_k).
How do you prove a formula for An\mathbf{A}^n?
Show n=1n=1, assume for n=kn=k, then multiply Ak+1=AkA\mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A}.
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 n=1n=1 passes to every nn.
Where do you write the target of the proof?
At the start of the step, as P(k+1)P(k+1) with nn replaced by k+1k+1, so you know what to reach.

Flashcards