Induction for divisibility and matrix powers

Induction for divisibility and matrix powers Flashcards

Spec A1 · AQA 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
How do you write the inductive hypothesis for divisibility by dd?
f(k)=dmf(k)=dm for some integer mm.
What must the final line of the inductive step show?
f(k+1)=d×(an integer expression)f(k+1)=d\times(\text{an integer expression}).
What are the two usual methods for the step?
Show f(k+1)−f(k)f(k+1)-f(k) is a multiple of dd, or substitute the hypothesis into f(k+1)f(k+1).
Simplify 5k+1−5k5^{k+1}-5^k.
4×5k4\times5^k
Simplify 7k+1−7k7^{k+1}-7^k.
6×7k6\times7^k
Why is k(k+1)k(k+1) always even?
One of two consecutive integers is even.
Find g(k+1)−g(k)g(k+1)-g(k) for g(n)=n3+11ng(n)=n^3+11n.
3k2+3k+123k^2+3k+12
How do you obtain Mk+1\mathbf{M}^{k+1} in an inductive proof?
Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}, with Mk\mathbf{M}^k replaced by the assumed formula.
M=(1101)\mathbf{M}=\begin{pmatrix}1&1\\ 0&1\end{pmatrix}: what is Mn\mathbf{M}^n?
(1n01)\begin{pmatrix}1&n\\ 0&1\end{pmatrix}
(2003)n=\begin{pmatrix}2&0\\ 0&3\end{pmatrix}^n=?
(2n003n)\begin{pmatrix}2^n&0\\ 0&3^n\end{pmatrix}
Why calculate M2\mathbf{M}^2 and M3\mathbf{M}^3 before proving?
To spot the pattern or check the given formula for small nn.
Write a full conclusion for a divisibility proof.
True for n=1n=1; if true for n=kn=k then true for n=k+1n=k+1; so true for all positive integers nn by induction.

Flashcards