Mathematical induction III

Today, we will solve some more problems using mathematical induction.

Problem 7. Observe that  $$\cos 2 \alpha = 2 \cos^2 \alpha - 1$$

Prove that we can write $\cos n\alpha$ as a polynomial of $\cos \alpha$.

Solution. We will prove by induction the following statement

For any $n$, there exists a polynomial $P_n$ such that $\cos n\alpha = P_n(\cos \alpha)$.

For $n=0$, we have $$cos 0 = 1$$

so we can choose the polynomial $P_0(x) = 1$ and the statement is correct for the case $n=0$.

The statement is clearly correct for the case $n=1$ with the polynomial $P_1(x) = x$.

Suppose that the statement is correct for any $0 \leq n \leq k$ where $k \geq 1$. We will prove that the statement is also correct for the case $n=k+1$.

We have $$\cos (k+1)\alpha + \cos (k-1)\alpha = 2 \cos k\alpha \cos \alpha$$

So $$\cos (k+1)\alpha = 2 \cos k\alpha \cos \alpha - \cos (k-1)\alpha$$

Since $0 \leq k-1 < k$, by induction assumption, the statement is correct for the case $n=k-1$, thus, there exists a polynomial $P_{k-1}(x)$ such that $$\cos (k-1)\alpha = P_{k-1}(\cos \alpha)$$

By induction assumption, the statement is correct for the case $n=k$, so there exists a polynomial $P_{k}(x)$ such that $$\cos k\alpha = P_{k}(\cos \alpha)$$

It follows that $$\cos (k+1)\alpha = 2 P_{k}(\cos \alpha) \cos \alpha - P_{k-1}(\cos \alpha)$$

If we let $$P_{k+1}(x) = 2 P_{k}(x) x - P_{k-1}(x)$$ then $\cos (k+1)\alpha = P_{k+1}(\cos \alpha)$. So the statement is correct for the case $n=k+1$.

By the mathematical induction principle, the statement must be correct for any value of $n$. $\blacksquare$

Based on the above proof, we have $P_0(x) = 1$, $P_1(x) = x$ and $$P_{k+1}(x) = 2 P_{k}(x) x - P_{k-1}(x)$$

Thus,

$$P_{2}(x) = 2 P_{1}(x) x - P_{0}(x) = 2 x^2 - 1$$

$$P_{3}(x) = 2 P_{2}(x) x - P_{1}(x) = 2(2 x^2 - 1)x - x = 4 x^3 - 3x$$

$$P_{4}(x) = 2 P_{3}(x) x - P_{2}(x) = 2(4 x^3 - 3x)x - (2 x^2 - 1) = 8 x^4 - 8x^2 + 1$$

$$P_{5}(x) = 2 P_{4}(x) x - P_{3}(x) = 2(8 x^4 - 8x^2 + 1)x - (4 x^3 - 3x) = 16 x^5 - 20x^3 + 5x$$

and we have the following identities

$$\cos 2 \alpha = 2 \cos^2 \alpha - 1$$

$$\cos 3 \alpha = 4 \cos^3 \alpha - 3 \cos \alpha$$

$$\cos 4 \alpha = 8 \cos^4 \alpha - 8\cos^2 \alpha + 1$$

$$\cos 5 \alpha = 16 \cos^5 \alpha - 20 \cos^3 \alpha + 5 \cos \alpha$$

Problem 8. With the Fibonacci sequence $$F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, \dots$$

Find all values of $n$ such that $F_n> n^2$.

Solution. Observe that

$$F_0=0 = 0^2, F_1=1 = 1^2, F_2=1 < 2^2, F_3=2 < 3^2, F_4=3 < 4^2,$$

$$F_5=5 < 5^2, F_6=8 < 6^2, F_7 = 13 < 7^2, F_8 = 21 < 8^2, F_9 = 34 < 9^2,$$

$$F_{10} = 55 < 10^2, F_{11} = 89 < 11^2, F_{12} = 144 = 12^2, F_{13} = 233 > 13^2, F_{14} = 377 > 14^2$$

We will prove by induction the following statement

For any natural number $n \geq 13$, $F_n> n^2$.

With the above calculation, $$F_{13} = 233 > 13^2 = 169, F_{14} = 377 > 14^2 = 196$$

so the statement is correct for the case $n = 13$ and $n=14$.

Suppose that the statement is correct for any $13 \leq n \leq k$ where $k \geq 14$. We will prove that the statement is also correct for the case $n=k+1$.

Since $13 \leq k-1 < k$, by induction assumption, the statement is correct for the case $n=k-1$, thus, $$F_{k-1}> (k-1)^2$$

Also by induction assumption, the statement is correct for the case $n=k$, so $$F_{k}> k^2$$

It follows that $$F_{k+1} = F_{k-1} + F_k > (k-1)^2 + k^2 = (k+1)^2 + (k^2 - 4k)$$

Since $k \geq 14$, we have $k^2 - 4k > 0$, and therefore, $F_{k+1} > (k+1)^2$. So the statement is correct for the case $n=k+1$.

By the mathematical induction principle, the statement must be correct any $n \geq 13$. So $F_n> n^2$ if and only if $n \geq 13$. $\blacksquare$

Problem 9. Let $x_1, x_2, \dots, x_n$ be $n$ distinct numbers. Let $y_1, y_2, \dots, y_n$ be arbitrary numbers. Prove that there exists a polynomial $P(x)$ such that $$P(x_1) = y_1, P(x_2) = y_2, \dots, P(x_n) = y_n$$

Solution. We will prove by induction the following statement

There exists a polynomial $P_n(x)$ such that $$P_n(x_1) = y_1, P_n(x_2) = y_2, \dots, P_n(x_n) = y_n$$

For $n=1$, we can choose the constant polynomial $P_1(x) = y_1$ then we will have $P_1(x_1) = y_1$. Thus, the statement is correct for the case $n=1$.

Suppose that the statement is correct for any $1 \leq n \leq k$. We will prove that the statement is also correct for the case $n=k+1$.

Indeed, by induction assumption, the statement is correct for the case $n=k$, so there exists a polynomial $P_{k}(x)$ such that $$P_k(x_1) = y_1, P_k(x_2) = y_2, \dots, P_k(x_k) = y_k$$

If we let $$P_{k+1}(x) = P_k(x) + a (x-x_1)(x-x_2) \dots (x-x_k)$$

then we immediately have $$P_{k+1}(x_1) = P_k(x_1) = y_1, P_{k+1}(x_2) = P_k(x_2) = y_2, \dots, P_{k+1}(x_k) = P_k(x_k) = y_k$$

We only need to determine $a$ so that $P_{k+1}(x_{k+1}) = y_{k+1}$.

Since $$P_{k+1}(x_{k+1}) = P_k(x_{k+1}) + a (x_{k+1} - x_1)(x_{k+1} - x_2) \dots (x_{k+1} - x_k)$$

to make $P_{k+1}(x_{k+1}) = y_{k+1}$ we need to have $$a = \frac{y_{k+1} - P_k(x_{k+1})}{(x_{k+1} - x_1)(x_{k+1} - x_2) \dots (x_{k+1} - x_k)}$$

Thus, the statement is correct for the case $n=k+1$.

By the mathematical induction principle, the statement must be correct for any values of $n$. $\blacksquare$

We now follow the steps in the solution of Problem 9 to find a polynomial $P(x)$ such that $P(1) = 2$, $P(2) = 3$, $P(3) = 5$, $P(4) = 7$

• First, choose $P_1(x) = 2$ then $P_1(1) = 2$.

• Next, let $P_2(x) = 2 + a(x-1)$ then $P_2(1) = 2$ and $P_2(2) = 2 + a$. 
• Choose $a = 1$, then we have $P_2(2) = 3$. Thus, $P_2(x) = 2 + (x-1)$.

• Let $P_3(x) = 2 + (x-1) + a(x-1)(x-2)$ then $P_3(1) = 2$, $P_3(2) = 3$ and $P_3(3) = 4 + 2a$.
• Choose $a = \frac{1}{2}$, then $P_3(3) = 5$. So $P_3(x) = 2 + (x-1) + \frac{1}{2}(x-1)(x-2)$.

• Let $P_4(x) = 2 + (x-1) + \frac{1}{2}(x-1)(x-2) + a(x-1)(x-2)(x-3)$ then $P_4(1) = 2$, $P_4(2) = 3$, $P_4(3) = 5$ and $P_4(4) = 8 + 6a$. 
• Choose $a = - \frac{1}{6}$, then $P_4(4) = 7$. 

Thus, the required polynomial is $$P_4(x) = 2 + (x-1) + \frac{1}{2}(x-1)(x-2) - \frac{1}{6} (x-1)(x-2)(x-3)$$

See you again in the next post.

Homework.

1. Prove that

• if $n$ is an odd number then there exists a polynomial $Q_n$ such that $\sin n\alpha = Q_n(\sin \alpha)$. 
• if $n$ is an even number then there exists a polynomial $R_n$ such that $\sin n\alpha = \cos \alpha R_n(\sin \alpha)$. 

2. Find $\sin \frac{\pi}{5}$ and $\cos \frac{\pi}{5}$.

3. Given the following sequence: $a_0 = 3$, $a_1 = -1$, $a_2=9$,

$$a_{n+1} = 4 a_{n-1} + 4 a_{n-2} - a_n,$$

prove that if $n$ is odd then $a_n = -1$.

4. On a plane given $n$ straight lines with the following conditions

• no two lines are parallel to each other,
• no three lines meet at a common point.

Prove that there are exactly $n(n-1)/2$ intersection points from these $n$ lines.

5. Find another solution for Problem 9.