Mathematical induction and its consequences - Part 3

In part 3 here we try to provide more examples and to conclude methods of M.I. So that in the Finale we could apply M.I. to wider cases.

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