5. Matrix and more examples
Example 12 (HKALE Pure 93 I 10) Let M be the set of 3x3 real matrices. For $A,B\in M$, a relation ~ is set if there exist a non-singular $P\in M$ so that $A=PBP^{-1}$, then $A\sim B$.
a) Show that ~ is an equivalence relation.
b) Show if $A\sim B$ then $A^n\sim B^n$
Not a really "MI" question but this is a rare question involving MI because proves on matrices rarely depends on integers and their proves would be extremely difficult.
Definition. A equivalence relation A~B is set if and only if:
1) A~A (Reflxivity)
2) A~B implies B~A (symmetry)
3) A~B, B~C implies A~C (Transitivity).
Example 13. Defind a~b if $a-b=c\in Q$, this ia an equivalence relation because:
1) $x-x=0\in Q$, therefore $x\sim x$.
2) $a-b=c\in Q$ implies $b-a=-c\in Q$ so it's symmetrical.
3) $a-b,b-c\in Q$ implies $a-c\in Q$ since rational number performs closure in addition.
Now back to the original problem:
1) $A=IAI^{-1}$, therefore A~A.
2) $A=PBP^{-1}$, then $B=(P^{-1})A(P^{-1})^{-1}$, so it's symmetrical.
3) If $A=PBP^{-1}$ where P, Q are non-singular by determinant. For part (b) we have $A^n=(PBP^{-1})^n=PB^nP^{-1}$ so that $A^n\sim B^n$. How can we do this through MI?
A~B is the case n=1 which is given. Assume $A^n\sim B^n$ by $A^n=PB^nP^{-1}$, then $A^{n+1}=(PB^nP^{-1})(PBP^{-1})=PB^{n+1}P^{-1}$ and the same result is given, though this is quite stupid.
Readers can try to prove the following:
1) If C~0, then C is zero matrix.
2) AB ~ BA may not be true.
Example 14. (HKALE Pure 1992 I 5 Given that $u_1=0$, $u_{n+1}=2n-u_n$, show that $u_n=n+\frac{-1+(-1)^n}{2}$.
Approach 1: induction through odd and even separately.
We have $u_{n+2}=2+u_n$ so that it's true by summing up from the first term ($u_1$ for odd terms and $u_2$ for even terms).
Approach 2: induction through all integers.
Assume $u_n=n+\frac{-1+(-1)^n}{2}$, then $u_{n+1}=2n-u_n=n-\frac{-1+(-1)^n}{2}=(n+1)+\frac{-1+(-1)^{n+1}}{2}$ so that the induction is complete.
Example 15. (HKALE Puer 1989 I 11a) Prove the existance and uniqueness of $a_n,b_n$ so that $(1+\sqrt{2})^n=a_n+b_n\sqrt{2}$ and also:
i) $a_n\equiv 1\mod 2$ for all n.
ii) $b_n\equiv 1\mod 2$ for odd n.
Existance is trivial as the multiplication of $Z[\sqrt{2}]$ (lattice point in forms of $a+b\sqrt{2}$ that a,b are integers) performs closure, and there's at least one solution $(a_n,b_n)$ for every n. This is unique because $\sqrt{2}$ is irrational so that $a\sqrt{2}=b$ don't give rational solution.
For n=1, a=b=1.
Part I: Assume $a_n$ is odd for n = k. For n = k+1,
$(a_n+b_n\sqrt{2})(1+\sqrt{2})=(a_n+2b_n)+(a_n+b_n)\sqrt{2}=a_{n+1}+b_{n+1}\sqrt{2}$ so that $a_{n+1}=a_n+2b_n\equiv 1\mod 2$.
Part II:Notice that $(1+\sqrt{2})^2=3+2\sqrt{2}$, tweet the proposition that for $(1+\sqrt{2})(3+2\sqrt{2})^{n-1}=c_n+d_n\sqrt{2}$, $d_n\equiv 1\mod 2$. Assume that n = k is true, then for n = k+1,
$(c_n+d_n\sqrt{2})(3+2\sqrt{2})=(3c_n+4d_n)+(3d_n+2c_n)\sqrt{2}$ so that $d_{n+1}$ is also odd.
To end this one we would introduce a special case of M.I.
Theorem. (M.I. from the middle) The proposition is true for all n if:
a) P(k) is true, k is not necessarily 1.
b) Assuming P(x) is true, then P(x+1) and P(x-1) is true.
If P(x-1) is not necessarily true, then there exist $n_0\leq k$ that for all $n\geq n_0$, P(n) is true.
Somehow we don't have many elemental case for this because most proofs involving M.I., is true from n=1. Such bounding occurs more frequently in inequality and bounding case which could be much difficult. There's a modified question at the bottom (Q1) concerning this M.I. method.
To conclude, the followings are usual techniques for M.I.:
1) Expressing the case n = k+1 in terms of n = k, including their difference.
2) Seperate odd and even case especially in sequence.
3) Artificially make up expression, like $\frac{(n+2)(n+3)}{2}=\frac{((n+1)+1)((n+1)+2)}{2}$ as to show the case n = k+1
4) For M.I. in inequality, usually they behaves monotonically as power increases, so observing pattern is important.
Problems from HK A-Level Examinations:
1) (HKALE 1993 Pure I 2 modified)
$u_8=47,u_{11}=199$ and $u_{n+2}=u_{n+1}+u_n$ for all natrual n. Show that $u_n=\alpha^n+\beta^n$ where $\alpha, \beta$ are roots of $x^2-x-1=0$ by:
a) Finding $u_1,u_2$ and induction through natrual n.
b) By M.I. from the middle.
2) (HKALE 1996 Pure II 7b)
Show that $\sum_{r=0}^n \frac{x^r}{r!}+\frac{ex^{n+1}}{(n+1)!} > e^x > \sum_{r=0}^n \frac{x^r}{r!}$, hence show that $\sum_{r=0}^n \frac{x^r}{r!}$ tends to $e^x$ the constant.
(Note: in a more rigorous setting presumably it should be stated to be true for each bounded range but oh well this is merely matriculation level problems)
3) (HKALE 1991 Pure I 11)
a) Prove the existance and uniqueness that $(\sqrt{3}+\sqrt{2})^{2n}=p_n+q_n\sqrt{6}$ for natrual $n,p_n,q_n$. Also show that $(\sqrt{3}-\sqrt{2})^{2n}=p_n-q_n\sqrt{6}$. Hence deduce that $2p_n-1$ < $(\sqrt{3}+\sqrt{2})^{2n}$ < $2p_n$.
b) Show that the followings are multiples of 10:
i) $2^{5n}-2^n$
ii) $3^{4n}-1$
iii) $2p_{2n}-(2^{3n+1})(3^n)$.
c) By (a),(b) or otherwise, find the unit digit of $[(\sqrt{3}+\sqrt{2})^{100}]$ when it's expressed in decimal form. Note that [] is the integer (floor) function.
Read the rest of this passage:
Part I
Part II
Part IV
3) (HKALE 1991 Pure I 11)
a) Prove the existance and uniqueness that $(\sqrt{3}+\sqrt{2})^{2n}=p_n+q_n\sqrt{6}$ for natrual $n,p_n,q_n$. Also show that $(\sqrt{3}-\sqrt{2})^{2n}=p_n-q_n\sqrt{6}$. Hence deduce that $2p_n-1$ < $(\sqrt{3}+\sqrt{2})^{2n}$ < $2p_n$.
b) Show that the followings are multiples of 10:
i) $2^{5n}-2^n$
ii) $3^{4n}-1$
iii) $2p_{2n}-(2^{3n+1})(3^n)$.
c) By (a),(b) or otherwise, find the unit digit of $[(\sqrt{3}+\sqrt{2})^{100}]$ when it's expressed in decimal form. Note that [] is the integer (floor) function.
Read the rest of this passage:
Part I
Part II
Part IV
No comments:
Post a Comment