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