## Saturday, 24 December 2011

### 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 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 even 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 sum of rational numbers.
Then if $x\in R/Q$ and $x=\sum \frac{p_n}{q_n}$, then $f(x)=\sum f(\frac{p_n}{q_n})=\sum \frac{p_n}{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^{n}_{i=0}C^{m}_{i}C^{n}_{r-i}$
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$.

Now consider the function $f(x)=\sum^{\infty}_{r=0}C^m_rx^r$ where f converges when |x| < 1. Now $f(m)f(n)=\sum^{\infty}_{r=0}a_rx^r=\sum^{\infty}_{r=0} C^{m+n}_{r}x^r=f(m+n)$ (This can be done by direct expanding.)

Now $f(p)=(f(1))^p=(1+x)^p$ so that it's also valid for real p.

$(f(\frac{q}{p}))^p=f(q)$, so $f(\frac{q}{p})=(1+x)^{\frac{q}{p}}$ in which the positive root is taken due to positive sum is given.

For negative numbers, we have $f(m)f(n+1)=f(m)(1+x)^{n+1}=f(1)=1+x$, then $f(m)=(1+x)^m$.

For real numbers, we know that f is everywhere continous and differentiable in the interval $[0,1]$, therefore we can also put a irrational $r=\sum \frac{p_n}{q_n}$ that $\prod f(\frac{p_n}{q_n})=f(\sum \frac{p_n}{q_n})=f(r)$.

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^r$. When r is integer, $C^r_n=0$ for r < n so that the sum is finite. 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) Show that $\sum^{\infty}_{r=0}C^x_r=2^x$ is valid over real x by:
a) binomial substitution
b) the NZQR approach.
c) Compute $\sum^{\infty}_{r=0}r^xC^m_r$ where m and x is a real number.
3) Show the following identities:
a) $(1-x)^{\frac{-1}{2}}=1+\frac{x}{2}+\frac{(1)(3)x^2}{(2)(4)}+...$
b) $(a-b)^{-2}=\frac{1}{a^2}\sum^{\infty}_{r=0}rb^ra^{-r}$ where $|a|\geq |b|\geq 0$. Is it valid when $|a|=|b|$?
4) (2004 Pure I 5 modified) For real x, |a| < 1, show that: a) $a+a^x\leq 1+a^{x+1}$, $(1+a)^x\leq 2^{x-1}(1+a^x)$, hence show that $(\frac{a+b}{2})^x\leq 2^{x-1}(a^x+b^x)$

Read the rest of this passage:

Part I
Part II
Part III