Skip to content

3 Induction

Yue Shi 999027873

Exercise 1. (25 points) Use the Principle of Mathematical Induction to prove Bernoulli's inequality: \((1 + x)^n \geq 1 + nx, \quad \forall x > -1, \forall n \in \mathbb{N}\)

Proof

Let \(P(n):(1+x)^{n}\geq1+nx\)​

Basic step: \(P(1):1+x\geq1+x~~~~true!!\)

Inductive step: Assume \(P(n)\) is true (hypothesis) and we need to prove \(P(n+1)\) is also true.

We assume that \((1+x)^n\geq 1+nx\)

Now consider \(\left(1+x\right)^{n+1}=\left(1+x\right)^{n}\cdot\left(1+x\right)\geq\left(1+nx\right)\cdot\left(1+x\right)\text{ we use hypothesis here}\)

\(=1+x+nx+nx^{2}=1+\left(n+1\right)\cdot x+nx^{2}\)

\((1+x)^{n+1}\geq1+(n+1)\cdot x~~~Since~nx^{2}\geq0\)

Thus \((1 + x)^n \geq 1 + nx, \quad \forall x > -1, \forall n \in \mathbb{N}\)

Exercise 2. (25 points) Prove using the Principle of Mathematical Induction that \(\sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2\)

Proof

Basic step: When \(n=1\), \(\sum_{k=1}^1k^3=\left(\frac{1(1+1)}{2}\right)^2=1~~~\checkmark\)

Inductive step: Suppose it is true for \(n\), then we have \(\sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2\) (hypothesis)

We need to prove \(\sum_{k=1}^{n+1}k^3=\left(\frac{\left(n+1)(n+2\right)}{2}\right)^2\)

Let's consider \(\sum_{k=1}^{n+1}k^3=\sum_{k=1}^{n}k^3+\left(n+1\right)^3\). We use hypothesis here: \(=\left(\frac{n(n+1)}{2}\right)^2+\left(n+1\right)^3=\left(n+1\right)^2\left(\frac{n^2}{4}+n+1\right)=\left(n+1\right)^2\left(\frac{n^2+4n+4}{4}\right)=\left(n+1\right)^2\left(\frac{\left(n+2\right)^2}{2^2}\right)=\left(\frac{\left(n+1)(n+2\right)}{2}\right)^2\)

Thus \(\sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2\)

Exercise 3. (25 points) Let \(\{u_n\}\) be the sequence defined as

\(u_1=5,\quad u_2=13,\quad\text{and}\quad u_{n+2}=5u_{n+1}-6u_{n}\quad\forall n\geq1.\)

Prove that \(u_n = 2^n + 3^n\) for all \(n \in \mathbb{N}\).

Proof

Basic step: When \(n=1\), \(u_1=2^1+3^1=5~~~\checkmark\)

Inductive step: Suppose it is true for \(\forall k,1\leq k\leq n+1\), then we have \(u_{k}=2^{k}+3^{k}\) and \(u_{n+2}=5u_{n+1}-6u_{n}\quad\forall n\geq1.\) (hypothesis)

We need to prove \(u_{n+2}=2^{n+2}+3^{n+2}\)

Let's consider \(u_{n+2}=5u_{n+1}-6u_{n}\text{ ''we use hypothesis here''}=5\left(2^{n+1}+3^{n+1}\right)-6\left(2^{n}+3^{n}\right)=5\cdot2^{n+1}+5\cdot3^{n+1}-6\cdot2^{n}-6\cdot3^{n}=2^{n+1}\left(5-3\right)+3^{n+1}\left(5-2\right)=2^{n+2}+3^{n+2}\)

Thus \(u_n = 2^n + 3^n\) for all \(n \in \mathbb{N}\)

Exercise 4. (25 points) A convex polygon of \(n\) vertices is divided into triangles by some diagonals with the condition that no two of these diagonals intersect inside the polygon. Show that the number of such diagonals is \(n - 3\).

Proof

Since a polygon has at least 3 vertices, thus \(n\geq 3\)

Basic step: When \(n=3\), we already have a triangle and there is no diagonal in it.image​

Thus the number of diagonals is \(0\) which is same with \(3-3=0\) \(\checkmark\)

Inductive step: Assume \(n\) vertices polygon (\(V_1V_2...V_n\)) can be triangulated by \(n- 3\) non-intersecting diagonals. (hypothesis)

We need to prove that \(n+1\) vertices polygon (\(V_1V_2...V_nV_{n+1}\)) can be triangulated by \((n+1)- 3=n-2\) non-intersecting diagonals.

Then let's consider \(n+1\)-sides polygon(\(V_1V_2...V_nV_{n+1}\)).

First, we conncet \(V_1V_n\), then we divide it into two part: 1. \(\triangle V_1V_{n}V_{n+1}\) 2. \(n\) vertices polygon (\(V_1V_2...V_n\))

Then, we use hypothesis here: \(V_1V_2...V_n\) can be triangulated by \(n- 3\) non-intersecting diagonals.

Thus the total diagonals are the sum of the diagonals in \(V_1V_2...V_n\) and the diagonal \(V_1V_n\)

Thus there are \(n-3+1=n-2=(n+1)-3\) such diagonals

image​

Thus the number of such diagonals is \(n - 3\).

‍