Mathematical Induction and its consequences -- Finale

P.S. In before this starts. I decided to insert the method of induction into my summarizing work, Basic Albegraic Skills.

"Numbers" in history have different meanings. In the past there'are only natrual numbers by counting, next there was negative numbers due to the concept of debt. Rational numbers seems to fill up the real continum but Pythagoreans has found irrational numbers. Finally the concept of real number continum is developed by Cantor and complex numbers appeared as powerful calculation tool.

Mathematical induction, processing natrual numbers, seems too "old fashioned" because there're far many problems concerning somewhere beyond natrual numbers, and we need different approaches. If MI can be extended over the reals, it's just fantastic. We will illustrate this by two examples: function equation and bionomial theorem over the reals. Before that, we will look at more different MI problems on A-level exam past papers.

Theorem. (Generalization of M.I.)
If (a) P(a) and P(b) is true implies that P(a+b), P(|a-b|) is true,
b) Exist least positive r that P(r) is true,
then P(k) is true is equivalent to k is a multiple of r.

6. N, Z, Q, R --- extented conclusion derived from MI

Example 16. f(x) is a everywhere continuous and differentiable function satisfying:
1) $f(x)f(\frac{1}{x})=1$ for non-zero x;
2) Additive, i.e., $f(a)+f(b)=f(a+b)$;
3) f(1)=1.
Show that $f(x)=x$.

Step 1: N
For the proprosition $f(n)=n$: assume n=k is true, and for $f(n+1)=f(n)+f(1)=n+1$ is also true.

Step 2: Z
$f(0)+f(1)=f(1)$, therefore $f(0)=0$.
Next $f(1)+f(-1)=f(0)$, therefore $f(-1)=-1$.
Now set the proposition "f(-n)=-n" and finish the induction.

Another approach is that $f(x)+f(-x)=f(0)=0$, therefore f is odd and it's true over integers.

Step 3: Q
We use a double MI:
Theorem. The proposition P(a,b) is true for all a,b if:
1) P(1,1) is true.
2) If P(a,b) is true, then P(a,b+1) is true.
3) If P(a,b) is true, then P(a+1,b) is true.
This is quite powerful for rational numbers.
Here we use another approach of double MI that "For every b, P(a,b) implies P(a+1,b) is true".
For any given n, $f(\frac{1}{n})=\frac{1}{n}$ by property 1, and do induction so that "$f(\frac{a}{b})=\frac{a}{b}$ for every b. The method is similar as step 1 and 2. This is true for all rational numbers.

Step 4: R
We know that irrational numbers can always be traced by a series of rational numbers.
Lemma. Every irrational numbers can be written in forms of series limit of rational numbers.
For any real $x$, choose rational numbers $q_n$ with $q_n\to x$. Since $f(q_n)=q_n$ and $f$ is continuous, $f(x)=\lim_{n\to\infty}f(q_n)=\lim_{n\to\infty}q_n=x$.

P.S. Yet there's a simple method to do this question. Since the function is additive, we can show that the function has a constant slope, i.e., y' = m, so y = mx+c. Considering f(0)=0 and f(1)=1, we have f(x)=x.
Example 17. Extension of the binomial theorem.

Lemma. Vandermonde's Theorem:
$C^{m+n}_{r}=\sum^{r}_{i=0}C^{m}_{i}C^{n}_{r-i}$ for non-negative integers $m,n,r$, taking $C^m_i=0$ when $i>m$.
The proof is trivial when you expand $(1+x)^m(1+x)^n\equiv (1+x)^{m+n}$ and compare the coefficients of $x^r$. For fixed $r$, both sides are polynomials in $m,n$, using $C^t_0=1$ and $C^t_i=t(t-1)\cdots(t-i+1)/i!$ for $i\geq1$. Since the identity holds for all non-negative integers $m,n$, the polynomial identity also holds for real $m,n$.

Fix a real $x$ with $|x|<1$, and consider the function $f(m)=\sum^{\infty}_{r=0}C^m_rx^r$ for real $m$. This series converges absolutely. Vandermonde's identity and the Cauchy product give $f(m)f(n)=\sum^{\infty}_{r=0}C^{m+n}_{r}x^r=f(m+n)$.
In particular, $f(0)=1$, $f(1)=1+x$, and $f(m)f(-m)=1$. Also $f(m)=f(m/2)^2>0$.

For non-negative integers $q$, induction gives $f(q)=(1+x)^q$. For positive integers $p$ and non-negative integers $q$, $f(q/p)^p=f(q)=(1+x)^q$, so $f(q/p)=(1+x)^{q/p}$ because $f(q/p)>0$.

For negative rational numbers, write the exponent as $-t$ with $t>0$ rational. Since $f(-t)f(t)=f(0)=1$, $f(-t)=1/f(t)=(1+x)^{-t}$.

For real exponents, the series defining $f(m)$ converges uniformly when $m$ ranges over any bounded closed interval, with the fixed $|x|<1$. Indeed, for $|m|\leq M$ with $M\geq1$, $|C^m_r|\leq M(M+1)\cdots(M+r-1)/r!$, and the resulting majorant series converges by the ratio test. Since each coefficient $C^m_r$ is continuous in $m$, $f$ is continuous in its exponent on the real line. Choose rational numbers $q_n\to m$. Then $f(m)=\lim_{n\to\infty}f(q_n)=\lim_{n\to\infty}(1+x)^{q_n}=(1+x)^m$.

By comparing the coefficients we have the binomial coefficients over real numbers:

$C^r_i=\frac{r(r-1)(r-2)...(r-i+1)}{i!}$ and $(1+x)^r=\sum^{\infty}_{i=0}C^r_ix^i$. For a non-negative integer $r$, $C^r_n=0$ when $n>r$, so that the sum is finite. For other real $r$, the expansion above is used with $|x|<1$. These two results are quite powerful and the following problems can be solved. Exercise.
1) Show that $C^x_0=1$ for all real x.
2) For real $x>0$, show that $\sum^{\infty}_{r=0}C^x_r=2^x$. The series is absolutely convergent at this boundary; justify taking the limit as the series variable tends to 1 from below. Then use:
a) binomial substitution
b) the NZQR approach.
c) Compute $\sum^{m}_{r=0}r^xC^m_r$ where $m$ and $x$ are positive integers.
3) Show the following identities:
a) $(1-x)^{\frac{-1}{2}}=1+\frac{x}{2}+\frac{(1)(3)x^2}{(2)(4)}+...$ for $|x|<1$
b) $(a-b)^{-2}=\frac{1}{a^2}\sum^{\infty}_{r=0}(r+1)b^ra^{-r}$ where $a,b$ are real, $a\neq0$, and $|b|<|a|$. Is the series still convergent when $|a|=|b|$ and $a\neq0$?
4) (2004 Pure I 5 modified) For real $x\geq1$ and $0<a<1$, show that: a) $a+a^x\leq 1+a^{x+1}$, $(1+a)^x\leq 2^{x-1}(1+a^x)$. Hence, by rescaling and using symmetry, show that for positive real $a,b$, $(\frac{a+b}{2})^x\leq \frac{a^x+b^x}{2}$.

Read the rest of this passage:

Part I
Part II
Part III

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\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

Mathematical induction and its consequences Part 2

3. M.I. VS mod
In most case, M.I. would not be the most preferred choice to prove the divisibility of an expression because we have another powerful tool: modular arithmetic.

I would not put too much technical formulae about mod because it could be very difficult.

Definition 1. If $a=b+n$ where for some integer $n$, then we say $a\equiv b\mod n$ or sometimes we just write $=$ instead.

Lemma 1. If a is divisible by b, then $a\equiv 0\mod b$.

Lemma 2. For each $a, n$ there exists a unique integer $b$ so that $0\leq b \leq n-1$ and $a\equiv b\mod n$, we say $b$ is the principal value of a mod n, or the remainder when a is divided by n.

Lemma 3. $a+bn\equiv a\mod n$, then by binomial theorem, $(a+bn)^k\equiv a^k \mod n$.

Proof: exercise.

By such method we can now proof all previous examples.

Example 7. (Example 3 - 4 revisited) $6^n\equiv 1\mod 5$ and $6^n(5n-1)\equiv -1\mod 5$
The first one is trivial because $6^n=(1+5)^n\equiv 1\mod 5$.
The second statement can't be proved by diredctly proved in mod 25. Instead we show that $\frac{6^n(5n-1)+1}{5}\equiv 0\mod5$.
$\frac{6^n(5n-1)+1}{5}=n6^n-(1+6+6^2+...+6^{n-1})\equiv n-n=0\mod 5$.

For example 6, we know that $7\pm \sqrt{13}$ are the roots of $x^2-14x+36=0$, by binomial theorem, $(7+\sqrt{13})^n+(7-\sqrt{13})^n=2(C^n_07^n+C^n_27^{n-2}(13)+...)$, but at this level we can't find the bridge to show the divisibility through mod, but we can actually prove this by M.I. through this formula.

Lemma 4. (Extension of M.I.) The proposition is true for all natrual number n if:
a) The proposition is true for n = 1,2,3...,i
b) Assuming n = k is correct, then n = i + k is correct.

From (b), for every $a\equiv b\mod n$ where a is smaller than b, if n = a is true, then n = b is true, eventually it's true for all natrual number n.

By dividing the case into odd n and even n and complete M.I. separately, we can prove the statement as well.

4. Sequence and inequality

Example 8. (HKALE 1994 Pure I2) If $\sum a_i=(\frac{1+a_n}{2})^2$, prove that $a_n=2n-1$ if all terms are positive numbers.

For sequence, we usually prove the n=k+1 part by comparing their difference.

Define $s_n=\sum^{n}_{i=1}a_i=\frac{1}{4}(1+a_n)^2$.
Now $a_{n+1}=s_{n+1}-s_n$. Assuming that $a_n=2n-1$, then $s_n=\frac{1}{4}(1+2n-1)^2=n^2$.

Now $a_{n+1}=\frac{1}{4}(1+a_{n+1})^2-n^2$
$\frac{1}{4}(1-a_{n+1})^2=n^2$,
$a_{n+1}=2n+1$, where all negative terms are rejected.

Apart from some trivial geometric sequences, some sequences can also be transferred into something like geometric sequences, and we will introduce one of the sequence in form of $a_n=c+dr^n$.

Example 9. Find the general term of sequence $a_{n+1}=xa_n+y$.

Define $b_n=a_{n+1}-a_n$, then $b_{n+1}=a_{n+2}-a_{n+1}=(xa_{n+1}+y)-(xa_n+y)=x(a_{n+1}-a_n)=xb_n$, therefore $b_n=x^{n-1}(a_2-a_1)$ is a geometric sequence. Now $a_n=a_1+b_1+b_2+...+b_{n-1}=a_1+(a_2-a_1)(1+x+...+x^{n-2})$
$=a_1+(a_2-a_1)\frac{1-x^{n-1}}{1-x}$.

One of the stupid example is that $a_1=1$, $a_n=2a_{n-1}-1$, then $a_2=1$, $a_n=1+(1-1)\frac{1-2^{n-1}}{1-2}=1$, and therefore the sequence {1,1,1,1,...} is an A.S., G.S., as well as a recurrence sequence.

Exercise 4. It's given that the sum of a sequence is given by $S_n=4a_n+3n-4$, find its general term by
i) Guess and proved by M.I.
ii) Sequential analysis

Example 10 (BAS ex. 9.4.8, p.84) Let $a_1,...,a_n$ be positive reals so that $\prod (1+a_i)=2^n$, show that $\prod a_i \leq 1$.
There is a nice AM-GM proof but if one likes to try it inductively think about the substitution

$(1+b) = \frac{1}{2}(1+a_i)(1+a_j)$ that merges two term into one. The details are left to readers.

Example 11. (HKALE 1995 Pure I6) For a non-negative integral integral sequence so that $n\leq \sum^{n}_{i=1}a_i^2\leq n+1+(-1)^n$ for all natrual number n. Prove that the sequence is identically 1.
This inequality is quite trivial.
Proof 1. $1\leq a_{n+1}^2\leq 3$ when we subtract case (n+1) from case n, since it's non-negative integer, $a_i=1$.
Proof 2. We use another strong induction.

(Strong induction) A proposition $P(n)$ is true for all positive integer $n$ if:

1) P(1) is true.

2) P(1),..., P(n-1) is true implies P(n) is true. 

Assuming that $a_1=a_2=...=a_n=1$, then $n+1\leq n+a_{n+1}^2\leq n+2+(-1)^{n+1}\leq n+3$, the same result is given.

Exercise 5. Try to prove the above statement by separating n into odd and even case.

Read the rest of this passage:

Part I
Part III
Part IV

Mathematical induction and its consequences Part 1

Here we would concentrate in illustrating the case n = k + 1 assuming n = k is correct with n = 1 is correct.

1. Polynomials


Example. The most stupid M.I. in the world, showing that $\sum^{n}_{i=1}i=\frac{n^2+n}{2}$.
In polynomial form M.I. is always easy:
$\sum^{n+1}_{i=1}i=\sum^{n}_{i=1}i+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)((n+1)+1)}{2}$
so that the proof is complete.

Example 2. $\sum ^{n}_{i=1}i^2=\frac{n(n+1)(2n+1)}{6}$
Proof. $\sum^{n+1}_{i=1}i^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2=\frac{(n+1)(2n^2+n+6(n+1))}{6}$
$=\frac{(n+1)(n+2)(2n+3)}{6}$ which finishes the proof.

Exercise 1. Show that:
i) $\sum^{n}_{i=1}(2i-1)=n^2$, e.g., $1+3+5=3^2$
ii) $\sum^{n}_{i=1}i^3=\frac{n^2(n+1)^2}{4}$
In fact, there's no such a general form for sum of the n-th power of natrual number.

2. Divisibility and integral solution

Example 3. $6^n-1$ is divisible by 5.
Let $6^n-1=5K,K\in Z$, then $6^{n+1}-1=6(5K)+5=5(6K+1)$.

In more complicated case, some of the grouping method may not work.

Example 4. $6^n(5n-1)+1$ is divisible by 25.
Let $6^n(5n-1)+1=25K,K\in Z$, then $6^{n+1}(5n+5-1)+1=6((6^n)(5n+4)+1)-5=6(25K)+5(6^{n+1}-1)$ where the last term is divisible by 25 by ex.3.

Example 5. (CSMO) $\prod^{n}_{i=1}(4-\frac{2}{i})\in Z$ for all positive integer n.
It seems to be very fresh to most M2 or even Pure student as you don't know the proposition to be set in order to prove the statement.Think inversely, the next product must be integer if the last one is a multiple, (and of course, an integer) of the next i, then the next term must be integer too.
Therefore the proposition is $\prod^{n}_{i=1}(4-\frac{2}{i})$ is a multiple of $n+1$.

Exercise 2. Show that
1) $5^{2n-1}-3^{2n-1}-2^{2n-1}$ is divisible by 15 by induction on n.
2) Finish the proof for ex. 5.

The last example is from HKALE.

Example 6. (HKALE Pure 1998, I5) For $\alpha,\beta$ as roots of $x^2-14x+36=0$, show that $\frac{\alpha^n +\beta^n}{2^n}\in N$ for all natrual number n.

This is a 5-mark question and shouldn't be hard, or even fit perfectly for M2/Pure level, however we need another method of Mathematical Induction:

Theorem. Second principle of M.I. The proposition is true for all natrual n if:
1) n = 1,2,...i is true.
2) If n = j, (j+1), ... i+j is true, then n = i+j+1 is true.

in this case i = 2.
Assume $\alpha^n+\beta^n=2^nk_1$ and $\alpha^{n-1}+\beta^{n-1}=2^{n-1}k_2$.
By relationship between roots and equations, we have $\alpha + \beta = 14$, $\alpha \beta=36$.

Then $\alpha^{n+1}+\beta^{n+1}=(\alpha^n+\beta^n)(\alpha+\beta)-\alpha \beta(\alpha^{n-1}+\beta^{n-1})$

$=14(2^nk_1)-36(2^{n-1}k_2)=2^{n+1}(7k_1-9k_2)$

The last term is trivially a positive integer.

Challenge. The recurrence relationship of the sequence $a_n=\alpha^n+\beta^n$ is shown. Find the general term of the sequence.

Exercise 3. Is it true that for x,y as roots of $x^2-anx+n^2b=0$ satisfies $\frac{x^k+y^k}{n^k}$ is an integer? Prove your assertion. (a,b,n are natrual numbers.)

Read the rest of this passage:

Part II
Part III
Part IV

Irrationality II

Last time we have discussed the basic features of irrational numbers and this time we may talk more about the relationship between irrationals and ploynomials.

A supplementary note on the irrationality of trigonometric functions

Recall that rational numbers can be expressed in forms of simpliest ratio between two integers, in which the function involved is division (related to multiplication which is the inverse of division), which implies that rational numbers form a group under multiplication. However irrational numbers can't form a group ifself.

Denote a polynomial if and only if . For example, for  , . We call a polynomial a polynomial with integral coefficient, while calling a polynomial  a real polynomial. Our analysis prevent anything beyond real polynomial otherwise it will be far difficult.

Note that these symbols have their special meaning in group theory like the lattice point , but this is boyond the scope of this passage.

Let be a irrational number, i.e., and . Then we say that if , then . The inverse of this statement may NOT be true.
Proof:
Assume , then where n is rational and k is non-negative integer, so as the concerned polynomial f. Therefore .
For example, we know that is irrational since while . Simply putting into f gives the irrationality of the desired number.
However, the same arguement is not applicable on tangent function because it's angle sum formula is NOT a polynomial but a rational function.
We have . For example, we have . Although by the same arguement it works, but we shall prove the irrationality of tangent function by rewriting it into a continued fraction so that for every rational x, tan x is irrational unless it trivially is. (See Wolfram Mathworld)

An interesting fact is that the statement is not equivalent, however it CAN be equivalent. It should be easy for readers to find out its equivalent case when the inverse of f is considered, so it's proof  is left for readers.

Exercise. Find the necessary condition that is equivalent to .

We start from easier case: linear and quadratic functions.

Theorem. For linear , rationality of f(x) is equivalence to the rationality of x. Since rational number is a equivalence class, irrationality of f(x) also implies the irrationality of x.

Proof. If , then for rational m and c. Inversely  which is also linear, so the rationality of x implies the rationality of f(x). For since the coefficients are rational, we can apply the same procedure to show the irratioanlity relation.

Theorem. For quadratic f, the statement is equivalent only when , i.e., square root of a rational number.

Proof. left as exercise.

Sometimes problems concerning rational numbers are easier to be solved when rational numbers are replaced by integers. Then tools like congrunences can be applied easier.
For example, the statement " is irrational" is equivalent to " is insoluble in integers" because you can assume , which is equivalent to the second statement. Similarly we can rewrite the statement " is insoluble in rationals" (The method of Conic paramization) in equation over the integral domain. (Exercise)

The final aim of this passage is to proof the irrationality of more numbers.

Theorem. is either integer (trivial case) or irrational.
Recall that it's equivalent to the statement is soluble in integers of simpliest ratio. It follows that and for any prime factor p of b. Now so that which contradicts our assumption.

In fact this is a generalization of the second (historical) proof.

Here's another proof given by G.H. Hardy:
Assume where a,b,c are integers while with 0 < b < c. Now so that . Let , we have where 0 < d < b, which is a contradiction.

Now a interesting problem arises: why the contradictory result from "simpliest fraction" shows that the statement is false?
You may say that axioms of arithmetics are parallel, therefore if A is equivalent to B and B is proved to be false, then A is false as well.
Meanwhile we can say the lack of simpliest solution led to the infinite descent of solution set which is eventually out of our range [of concern], and therefore such case would not happen and the statement is false.

Similar arguement can be make to prove the irrationality of .
Theorem. is either integer or irrational.
Proof. Exercise.

Now we extend numbers to algebraic numbers.
Rational Root Theorem For a polynomial with integral coefficients, rational roots, if exist, in forms of , then p and q must be integral factor of respectively.
Proof. Exercise. (It's trivial when the rational number is directly subbed into the polynomial. Otherwise Gauss' Lamma can be used.

As a special case of it, we have
Theorem. For polynomial with integral coefficient 1, its real root is either integer or irrational.

Example. is irrational.
Let




is the original equation with root . Quickly check that is not a root of it, and therefore this polynomial has no integral zeros, so its roots so as the concerned number, must be irrational.

It provides us a powerful test for reducibility of polynomials or to test the existance of integral roots, in which we will discuss next time including Eisenstein's irreducible criterion and more tests on irrational numbers by infinite series.