*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-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 PQ is non-singular by determinants. 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.

<i>Example 14. (HKALE Pure 1992 I 5</i> 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.

<i>Example 15. (HKALE Puer 1989 I 11a)</i> 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=5+2\sqrt{2}$, tweet the proposition that for $(1+\sqrt{2})(5+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})(5+2\sqrt{2})=(5c_n+4d_n)+(5d_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.

<i>Theorem. (M.I. from the middle)</i> 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.

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