Proof by mathematical induction

Proof by mathematical induction Flashcards

Spec 1.1 · Edexcel 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 case, assumption for n=kn=k, inductive step to n=k+1n=k+1, conclusion.
Inductive step for a sum ∑r=1nur\sum_{r=1}^{n}u_r?
Add the (k+1)(k+1)th term uk+1u_{k+1} to the assumed sum, then factorise.
Write a full induction conclusion.
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 induction.
Base case for ∑r=1nr3=14n2(n+1)2\sum_{r=1}^{n}r^3=\frac14n^2(n+1)^2?
n=1n=1: LHS =1=1, RHS =14×1×4=1=\frac14\times1\times4=1.
Add and factorise: 14k2(k+1)2+(k+1)3\frac14k^2(k+1)^2+(k+1)^3?
14(k+1)2[k2+4(k+1)]=14(k+1)2(k+2)2\frac14(k+1)^2\left[k^2+4(k+1)\right]=\frac14(k+1)^2(k+2)^2
How do you show f(k+1)\mathrm{f}(k+1) is divisible by dd?
Write f(k+1)−a f(k)\mathrm{f}(k+1)-a\,\mathrm{f}(k) as a multiple of dd, or substitute the assumed form and factor out dd.
f(n)=32n+11\mathrm{f}(n)=3^{2n}+11: find f(k+1)−f(k)\mathrm{f}(k+1)-\mathrm{f}(k).
32k+2−32k=8×32k3^{2k+2}-3^{2k}=8\times3^{2k}, a multiple of 4.
If 7k=6m−57^k=6m-5, write 7k+1+57^{k+1}+5 as a multiple of 6.
7(6m−5)+5=42m−30=6(7m−5)7(6m-5)+5=42m-30=6(7m-5)
How do you set up the inductive step for Mn\mathbf{M}^n?
Assume Mk\mathbf{M}^k equals the formula, then calculate Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}.
Why must the basis case be shown?
Without a first true statement, the chain P(k)⇒P(k+1)P(k)\Rightarrow P(k+1) has nothing to start from.
What must you check in a matrix inductive step?
All four entries equal the formula with nn replaced by k+1k+1.
Common mistake in the inductive step?
Assuming P(k+1)P(k+1) at the start instead of deriving it from P(k)P(k).

Flashcards