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: modolar arithmetic.

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

Definition 1. If $a=b+n$ where n is a positive integer larger than 1, then we say $a\equiv b\mod n$.

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

Corollary 2. There's a unique, least positive integer so that for every a we have b so that $a\equiv b\mod n$, we can say b is the principal value of a mod n, or the remainder when a is divided by n.

Corollary 3. $a+bm\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 25$.
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 1. (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+2n+1$.

Now $a_{n+1}=\frac{1}{4}(1+a_{n+1})^2-(n+1)^2$
$\frac{1}{4}(1-a_{n+1})^2=(n+1)^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-1}$, 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. (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 lemma from MI.

Lemma 2. The proposition is true for all natrual n if:
1) n = 1 is true.
2) if n = 1,2,...,(k-1) is true, then n = k is true.

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

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

Example 11 (BAS ex. 9.4.8, p.84) For positive real so that $\prod (1+a_i)=2^n$, show that $\prod a_i \leq 1$.
Assuming n = k is true.
Now if one more number $a_{k+1}$ is added that $\prod (1+a_n)=2^{k+1}$ with $\sigma a_i$ greater than 1.

Then $a_{n+1}=(a_1a_2...a_n)^-1$ which is greater than 1, then $\prod (1+a_i)=2^n(1+a_{n+1})\neq 2^{n+1}$.

The above proof is incomplete and it would be nice for readers to finish the proof himself.

Read the rest of this passage:

Part I
Part III
Part IV