수학적 귀납법

Consider the following question:

For which natural numbers

n

do there exist nonnegative integers

x

and

y

such that

n = 3x + 5y

?

To help answer this question, we will let $\mathbb{Z}^* = \left\{ {x \in \mathbb{Z} \mid x \geq 0} \right\}$, and let $P \left( n \right)$ be There exist $x,y \in \mathbb{Z}^*$ such that $n = 3x + 5y$. Notice that $P(1)$ is false since if both $x$ and $y$ are zero, then $3x + 5y = 0$ and if either $x > 0$ or $y > 0$, then $3x + 5y \geq 3$. Also notice that $P(6)$ is true since $6 = 3 \cdot 2 + 5 \cdot 0$ and $P(8)$ is true since $8 = 3 \cdot 1 + 5 \cdot 1$.

Explain why $P(9)$, $P(10)$, $P(11)$, and $P(12)$ are true.

Consider the following question:

For which natural numbers

n

do there exist nonnegative integers

x

and

y

such that

n = 3x + 5y

?

To help answer this question, we will let $\mathbb{Z}^* = \left\{ {x \in \mathbb{Z} \mid x \geq 0} \right\}$, and let $P \left( n \right)$ be There exist $x,y \in \mathbb{Z}^*$ such that $n = 3x + 5y$. Notice that $P(1)$ is false since if both $x$ and $y$ are zero, then $3x + 5y = 0$ and if either $x > 0$ or $y > 0$, then $3x + 5y \geq 3$. Also notice that $P(6)$ is true since $6 = 3 \cdot 2 + 5 \cdot 0$ and $P(8)$ is true since $8 = 3 \cdot 1 + 5 \cdot 1$.

We could continue trying to determine other values of $n$ for which $P(n)$ is true. However, let us see if we can use the work in part (2) to determine if $P(13)$ is true. Notice that $13 = 3 + 10$ and we know that $P(10)$ is true. We should be able to use this to prove that $P(13)$ is true. This is formalized in the next part.

Let $k \in \mathbb{N}$ with $k \geq 10$. Prove that if $P( 8 )$, $P ( 9 )$, $\ldots$, $P( k )$ are true, then $P( {k+1} )$ is true.

Hint: $k + 1 = 3 + \left( {k - 2} \right)$.

Use mathematical induction to prove each of the following:

For each natural number $n$ with $n \geq 6$, $2^n > \left( n + 1 \right)^2$.

Use mathematical induction to prove each of the following:

For each natural number $n$ with $n \geq 3$, $\left( {1 + \dfrac{1}{n}} \right)^n \lt n$.

For which natural numbers $n$ is $n! > 3^n$? Justify your conclusion.

Complete the following.

Verify that $\left( {1 - \dfrac{1}{4}} \right) = \dfrac{3} {4}$ and that $\left( {1 - \dfrac{1}{4}} \right)\left( {1 - \dfrac{1}{9}} \right) = \dfrac{4} {6}$.

Complete the following.

Verify that $\left( {1 - \dfrac{1}{4}} \right)\left( {1 - \dfrac{1}{9}} \right) \left( {1 - \dfrac{1}{{16}}} \right) = \dfrac{5}{8}$ and that $\left( {1 - \dfrac{1}{4}} \right)\left( {1 - \dfrac{1}{9}} \right) \left( {1 - \dfrac{1}{{16}}} \right)\left( {1 - \dfrac{1}{{25}}} \right) = \dfrac{6}{{10}}$.

Complete the following.

For $n \in \mathbb{N}$ with $n \geq 2$, make a conjecture about a formula for the product $\left( {1 - \dfrac{1}{4}} \right) \left( {1 - \dfrac{1}{9}} \right) \left( {1 - \dfrac{1}{{16}}} \right) \cdots \left( {1 - \dfrac{1}{{n^2 }}} \right)$.

Is the following proposition true or false? Justify your conclusion.

For each nonnegative integer

n

,

8^n \mid \left( {4n} \right)!

.

Let $y = \ln x$.

Determine $\dfrac{{dy}}{{dx}}$, $\dfrac{{d^2 y}}{{dx^2 }}$, $\dfrac{{d^3 y}}{{dx^3 }}$, and $\dfrac{{d^4 y}}{{dx^4 }}$.

Let $y = \ln x$.

Let $n$ be a natural number. Formulate a conjecture for a formula for $\dfrac{{d^n y}}{{dx^n }}$. Then use mathematical induction to prove your conjecture.

For which natural numbers $n$ do there exist nonnegative integers $x$ and $y$ such that $n = 4x + 5y$? Justify your conclusion.

Can each natural number greater than or equal to 4 be written as the sum of at least two natural numbers, each of which is a 2 or a 3? Justify your conclusion. For example, $7 = 2 + 2 + 3$, and $17 = 2 + 2 + 2 + 2 + 3 + 3 + 3$.

Can each natural number greater than or equal to 6 be written as the sum of at least two natural numbers, each of which is a 2 or a 5? Justify your conclusion. For example, $6 = 2 + 2 + 2$, $9 = 2 + 2 + 5$, and $17 = 2 + 5 + 5 + 5$.

Use mathematical induction to prove the following proposition:

Let

x

be a real number with

x > 0

. Then for each natural number

n

with

n \geq 2

,

\left( {1 + x} \right)^n > 1 + nx

.

Explain where the assumption that $x > 0$ was used in the proof.

Prove that for each odd natural number $n$ with $n \geq 3$,

$$\left( {1 + \frac{1}{2}} \right) \left( {1 - \frac{1}{3}} \right) \left( {1 + \frac{1}{4}} \right) \cdots \left( {1 + \frac{{\left( { - 1} \right)^n }}{n}} \right) = 1$$

.

Prove that for each natural number $n$, any set with $n$ elements has $\dfrac{n \left( {n-1} \right)}{2}$ two-element subsets.

Prove or disprove each of the following propositions:

For each $n \in \mathbb{N}$, $\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n (n + 1 )} = \dfrac{n}{n+1}$.

Prove or disprove each of the following propositions:

For each natural number $n$ with $n \geq 3$,

$$\frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \cdots + \frac{1}{n (n + 1 )} = \frac{n-2}{3n + 3}$$

.

Prove or disprove each of the following propositions:

For each $n \in \mathbb{N}$, $1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n (n + 1 ) = \dfrac{n (n + 1 ) (n + 2 )}{3}$.