11.6 Three principles

Workshop 4.pdf

Prove that no function exists from \(\mathbb{N} \to \mathbb{N}\) such that \(f(n) > f(n+1)\).

Suppose it exists, \(f(n) > f(n+1)\).

This implies \(f(1)\) is the maximum of \(f\) and \(f\) is decreasing.

Let \(f(1) = M\), so \(f\) is bounded above and decreasing.

Thus, the maximum of \(f(M)=1\implies f(M+1)=0\notin\N\)

Contradiction!
Show that, for all \(n \in \mathbb{N}^*\), we have \(2^{n-1} \leq n! \leq n^n\).

Basic step: For \(n=1\), \(2^0 = 1 <1^1 = 1<1\checkmark\)

Inductive Step: Suppose \(P(n)\) is true for \(n\).

Then we have \(2^{n-1} \leq n! \leq n^n\)

Then \(2^{n} = 2 \cdot 2^{n-1} \leq 2 \cdot n! \leq 2 \cdot n^n\) since \(n \geq 2\).

Then \(2^{n}\leq2\cdot n!\leq(n+1)!\leq2\cdot n^{n}\leq n^{n+1}\leq(n+1)^{n+1}\)

Thus \(2^{n} \leq (n+1)! \leq (n+1)^{n+1}\)
Prove by induction that, for all \(n \in \mathbb{N}^*\), \(6\) divides \(7^n - 1\).

Basic step: \(n = 1. \quad 7^1 - 1 = 6, \quad 6 \mid 6 \quad \checkmark\)

Inductive step: Suppose it is true for \(n\).

Then \(6 \mid (7^n - 1) \Rightarrow 7^n - 1 = 6k\)

Then \(7^{n+1} - 1 = 7 \cdot 7^n - 1 = 7 \cdot (7^n - 1) + 6\)

\(= 7(6k) + 6 = 42k + 6 = 6(7k + 1)\)

Thus \(6 \mid (7^{n+1} - 1)\)
For \(n \in \mathbb{N}\), we consider the following property:

\(P_n : 2^n > n^2\).
1. Show that the implication \(P_n \implies P_{n+1}\) is true for \(n \geq 3\).
2. For what values of \(n\) is the property \(P_n\) true?
Easily....
Let \((u_n)_{n \in \mathbb{N}}\) be the sequence defined by \(u_0 = 2\), \(u_1 = 3\) and, for all \(n \in \mathbb{N}\), \(u_{n+2} = 3u_{n+1} - 2u_n\). Show that, for all \(n \in \mathbb{N}\), \(u_n = 1 + 2^n\).

Basic step: when \(n=0\), \(u_2 = 3u_1 - 2u_0 \Rightarrow u_2 = 5\) and \(u_2 = 1 + 3 \cdot 2 = 5 \quad \checkmark\)

Inductive step: Suppose it is true for \(n\), then \(u_n = 3u_{n-1} - 2u_{n-2}\) and \(u_n = 1 + 2^n\), \(u_{n-1} = 1 + 2^{n-1}\)

Then \(u_{n+1}=3u_{n}-2u_{n-1}\quad\text{ using hypothesis}\)

We have \(u_{n+1} = 3 \cdot (1 + 2^n) - 2 \cdot (1 + 2^{n-1}) = 1 + 2 \cdot 2^n = 1 + 2^{n+1}\)

Thus it is true.
Let \((u_n)_{n \in \mathbb{N}^*}\) be the sequence defined by \(u_1 = 3\) and for all \(n \geq 1\), \(u_{n+1} = \frac{2}{n} \sum_{k=1}^n u_k\). Show that, for all \(n \in \mathbb{N}^*\), we have \(u_n = 3n\).

Basic step: when \(n=1\), \(u_2 = 2 \, u_1 = 6\) and \(u_2 = 3 \cdot 2 = 6 \quad \checkmark\)

Inductive step: Suppose it is true for \(n\), then \(u_{n}=\frac{2}{n-1}\sum_{k=1}^{n-1}u_{k}\), \(u_{n}=3n\).

Then \(u_{n+1}=\frac{2}{n}\sum_{k=1}^{n}u_{k}=\frac{2}{n}\left(u_{n}+\sum_{k=1}^{n-1}u_{k}\right)=\frac{2}{n}\left(3n+\sum_{k=1}^{n-1}u_{k}\right)=\frac{2}{n}\left(3n+\frac{n-1}{2}\cdot u_{n}\right)\)

We have
\(u_{n+1} = 6 + \frac{n}{n} - 3n = 6 + 3n - 3 = 3(n+1)\).

Thus it is true.
Let \((u_n)\) be the sequence defined by \(u_0 = 1\) and, for all \(n \geq 0\), \(u_{n+1} = u_0 + u_1 + \cdots + u_n\). Show that, for all \(n \geq 1\), \(u_n = 2^{n-1}\).

Easily...
Prove that every convex polygon with \(n\) sides has \(\frac{n(n-3)}{2}\) diagonals.

Basic step: \(n=3\), \(0\) diagonals and \(\frac{3(3-3)}{2} = 0 \quad \checkmark\)

Inductive step: Suppose it is true for \(n\), then the number of diagonals is \(\frac{n(n-3)}{2}\).

Then for \(n+1\), diagonals \(=\frac{n(n-3)}{2}+n-1=\frac{\left(n+1\left)\left(n-2\right)\right.\right.}{2}\).

Since we have one more convex \(A\) in the \(n+1\)-sided polygon compared to \(n\)-sided polygon, we can connect \(A\) to the other convexes except neighboring two convexes, which is \(n-2\) diagonals, and we also need to add \(1\) to let the side for \(n\) become the diagonal for \(n+1\). Thus we need plus \(n-1\).
(★)
1. Write \(\cos((n+1)^\circ)\) as a function of \(\cos(n^\circ)\), \(\cos(1^\circ)\) and \(\cos((n-1)^\circ)\).
  
  \(\cos(n+1^{\circ})=\cos(n^{\circ})\cos(1^{\circ})-\sin(n^{\circ})\sin(1^{\circ})\)
  
  We need to express \(\sin(n^\circ)\) and \(\sin(1^{\circ})\)
  
  \(\sin(n^{\circ})=\sqrt{1-\cos^2(n^{\circ})}\quad\sin(1^{\circ})=\sqrt{1-\cos^2(1^{\circ})}\)
  
  Then \(\cos(n+1^{\circ})=\cos(n^{\circ})\cos(1^{\circ})-\sqrt{1+[\cos(n^{\circ})\cos(1^{\circ})]^2-[\cos^2(n^{\circ})+\cos^2(1^{\circ})]}\)
  
  I cannot continue
  
  Thus we need to find a another way to simplify it.
  
  Notice that \(\cos\left(n^{\circ}\right)\cos\left(1^{\circ}\right)=\frac12\left\lbrack\cos\left(n^{\circ}-1^{\circ}\right)+\cos\left(n^{\circ}+1^{\circ}\right)\right\rbrack\)
  
  Thus we can direct write it as \(\cos(n+1^{\circ})=2\cos(n^{\circ})\cos(1^{\circ})-\cos\left(n^{\circ}-1^{\circ}\right)\) 2. Prove that \(\cos(1^\circ)\) is irrational.
  
  Suppose \(\cos(1^\circ)\) is rational, then \(\cos(1^\circ) = \frac{m}{n}\), \(m, n \in \mathbb{N}\)
  
  Let \(n = 1\), \(\cos(2^\circ) = 2 \cos^2(1^\circ) - 1\)
  
  \(\cos2^{\circ}=\frac{2m^2}{2n^2}-1=\frac{2m^2-2n^2}{2n^2}\)
  
  Then we can suppose it is true for \(n\), that is \(\cos\left(n^{\circ}\right)\) and \(\cos\left(\left(n-1\right)^{\circ}\right)\) are rational number
  
  Since \(\cos(n+1^{\circ})=2\cos(n^{\circ})\cos(1^{\circ})-\cos\left(n^{\circ}-1^{\circ}\right)\), then \(\cos\left(\left(n+1\right)^{\circ}\right)\) is also rational number.
  
  But if \(n=44\), contradiction!
(★) Let \(n\) be a strictly positive integer and \(p_n\) the \(n\)-th prime number. Show that there are infinitely many prime numbers.

Let us consider a set \(A=\{t:\text{ There is no prime number in }(t,+\infty),t\text{ is a composite number}\}\)

We need to prove \(A=\emptyset\), let suppose \(A\neq \empty\)

Then by WOP, there exists the first element in \(A\) which is \(t_0\).

Thus there is no prime number in \((t_0,+\infty)\) and \(t_0\) is a composite number.

Then we know \(t_0-1<t_0,t_0-1\notin A\), then there exists prime number in \((t_0-1,+\infty)\equiv[t_0,+\infty)\).

Thus \(t_0\) must be a prime number, which is a contradiction!

Other way:

Suppose there exists a list of prime number \(p_1,p_2,...,p_n\), then we consider \(p_1p_2...p_n+1\)

If it is a prime number, we are done

If it is a composite number, then it can be written as the product of prime numbers

But no prime number can divide \(p_1p_2...p_n+1\), contradiction!

‍

Show the following inequality: \(p_n \leq 2^{2^n}\).

Suppose \(p_i \leq 2^{2^i}\) for all \(i \leq n\). Now \(p_1 \cdot p_2 \cdots p_n + 1\) is not divisible by any of the primes \(p_1, \dots, p_n\), so

\(p_{n+1} \leq \prod_{i=1}^n p_i + 1\)

Substituting the earlier bounds on \(p_i\) and using \(\sum_{i=1}^n 2^i = 2^{n+1} - 2\), we get

\(p_{n+1} \leq \left( \prod_{i=1}^n 2^{2^i} \right) + 1 = \left( 2^{\sum_{i=1}^n 2^i} \right) + 1 = 2^{2^{n+1} - 2} + 1 \leq 2^{2^{n+1}}\)
(★★) Show that, for any integer \(n \geq 3\), we can find \(n\) strictly positive integers \(x_1, \dots, x_n\), two by two distinct, such that \(\frac{1}{x_1} + \cdots + \frac{1}{x_n} = 1.\)

It is easily that if \(n=3\), then \(x_1=2,x_2=3,x_3=6\)

And Suppose it is true for \(n\), that is \(\frac{1}{x_1} + \cdots + \frac{1}{x_n} = 1.\)

Then for \(n+1\), we want \(\frac{1}{x_1}+\cdots+\frac{1}{x_{n}}+\frac{1}{x_{n+1}}=1\)

Thus i want to remain the items from \(\frac{1}{x_1}\) to \(\frac{1}{x_{n-1}}\), then i want to replace \(\frac1{x_n}\) with \(\frac1{x_n}+\frac1{x_n+1}\)

Let us try some easy example, what about \(n=4\)?

\(x_1=2,x_2=3,x_3=7,x_4=42\)

Thus i can see \(\frac16=\frac17+\frac{1}{42}\)

Thus let us try \(\frac{1}{x_{n}}=\frac{1}{x_{n}+1}+\frac{1}{x_{n}\cdot\left(x_{n}+1\right)}\) , correct!!

Thus we can easily complete the induction
(★★) Let \(f : \mathbb{N} \to \mathbb{N}\) such that \(f(n+1) > f(f(n))\) for all \(n \in \mathbb{N}\). Show that \(f(n) = n\) for all \(n \in \mathbb{N}\). (Hint: Show by induction on \(n\) that \(P_{n}:\forall k\geq n\implies f(k)\geq n\).)

Base Case (\(n = 1\) )

We need to show that \(f(1) = 1\).

For \(n = 1\): \(f(2) > f(f(1)).\)

Case 1: Suppose \(f(1) > 1\).
- Then \(f(1) \geq 2\) (since \(f(1)\) is a natural number).
- Consequently, \(f(f(1)) \geq f(2)\) (because \(f\) maps to \(\mathbb{N}\), and thus \(f(1) \geq 2\) implies \(f(f(1)) \geq f(2)\)).
- Substituting into the condition: \(f(2) > f(f(1)) \geq f(2),\) which implies \(f(2) > f(2),\) a contradiction.
Case 2: Therefore, the only possibility is \(f(1) = 1.\)

Thus, \(f(1) = 1\).

#### Inductive Step

Inductive Hypothesis: Assume that for some \(n \geq 1,\) the function satisfies \(f(k) = k \quad \text{for all } k \leq n.\)

Goal: Show that \(f(n + 1) = n + 1.\)

Proof:

Given the condition: \(f(n + 1) > f(f(n)).\)

By the inductive hypothesis, \(f(n) = n.\) Substituting this into the inequality: \(f(n + 1) > f(n) = n.\) Since \(f(n + 1)\) is a natural number greater than \(n,\) the smallest possible value it can take is \(n + 1.\) Therefore: \(f(n + 1) \geq n + 1.\)

Suppose, for contradiction, that \(f(n + 1) \geq n + 2.\)

Then, applying the original condition to \(n + 1\): \(f(n + 2) > f(f(n + 1)) \geq f(n + 2).\) This implies \(f(n + 2) > f(n + 2),\) which is impossible.

Therefore, our assumption that \(f(n + 1) \geq n + 2\) must be false. Hence: \(f(n + 1) = n + 1.\)

Or

Role of the Hint:

The hint suggests that you prove the statement \(P_n: \forall k \geq n \implies f(k) \geq n\) using mathematical induction. This statement establishes a lower bound for the function \(f\); that is, for all natural numbers \(k\) greater than or equal to \(n\), we have \(f(k) \geq n\). This helps us understand the growth trend of \(f\) and provides a foundation for subsequently proving that \(f(n) = n\).

Relationship Between the Hint and the Proof:

By proving \(P_n\), we can conclude that \(f(k)\) will not be less than \(n\) (for \(k \geq n\)). This implies that \(f\) is at least a “non-decreasing” or “increasing” function. Then, we can use the inequality given in the problem, \(f(n+1) > f(f(n))\), along with our understanding of \(f\), to further conclude that \(f(n) = n\).

How to Use the Hint Correctly:

Here are the steps to follow in using the hint for the proof:
1. Base Case (\(n = 1\) ):
  
  We need to prove \(P_1: \forall k \geq 1 \implies f(k) \geq 1\).
  
  Since the range of \(f\) is the natural numbers (\(\mathbb{N}\)), for all \(k \in \mathbb{N}\), we have \(f(k) \geq 1\). Thus, the base case holds. 2. Inductive Hypothesis:
  
  Assume that for some \(n \geq 1\), the statement \(P_n\) holds, i.e., for all \(k \geq n\), \(f(k) \geq n\). 3. Inductive Step:
  
  We need to prove that \(P_{n+1}\) holds, i.e., for all \(k \geq n+1\), \(f(k) \geq n+1\).
  
  According to the inequality given in the problem, \(f(n+1) > f(f(n))\).
  
  From the inductive hypothesis, \(f(n) \geq n\), so \(f(f(n)) \geq f(n) \geq n\).
  
  Therefore, \(f(n+1) > n\). Since \(f(n+1)\) is a natural number, we conclude \(f(n+1) \geq n+1\).
  
  Then, using the hypothesis again, we have that for all \(k \geq n+1\), \(f(k) \geq n+1\). 4. Conclusion:
  
  By mathematical induction, we have proven that for all \(n \in \mathbb{N}\), \(\forall k \geq n \implies f(k) \geq n\). This implies \(f(n) \geq n\) for all \(n \in \mathbb{N}\). 5. Proof of \(f(n) = n\) :
  - Assume there exists some \(m\) such that \(f(m) > m\) :
  - Since \(f(m) > m\) and \(f\) is a natural-valued function, we have \(f(m) \geq m + 1\).
  - By the previous conclusion, \(f(f(m)) \geq f(m) \geq m + 1\).
  - Using the inequality given in the problem, \(f(m+1) > f(f(m))\), we have:
    
    \(f(m+1) > f(f(m)) \geq m + 1\) * Thus, \(f(m+1) \geq m + 2\). * This suggests that if \(f(m) > m\), then \(f(m+1)\) will also be larger, and so on. * However, this leads to \(f(n)\) increasing without bound, which contradicts the nature of \(f\) as a function from \(\mathbb{N}\) to \(\mathbb{N}\). * **Thus, assuming there exists some \(m\) such that \(f(m) > m\) leads to a contradiction, so we conclude \(f(n) = n\) for all \(n\).
Summary:

The hint helps establish a lower bound for the function \(f\), proving \(f(n) \geq n\). Then, by using the inequality given in the problem and induction, we can show that \(f(n)\) cannot exceed \(n\), leading to the conclusion that \(f(n) = n\) for all \(n \in \mathbb{N}\).

‍