19th Ave New York, NY 95822, USA

# 数学代写代考|Strong Induction离散数学

## 数学代写| Strong Induction 代考

my-assignmentexpert愿做同学们坚强的后盾，助同学们顺利完成学业，同学们如果在学业上遇到任何问题，请联系my-assignmentexpert™，我们随时为您服务！

## 离散数学代写

Strong induction is another form of mathematical induction, which is often employed when we cannot prove a result with (weak) mathematical induction. It is similar to weak induction in that there is a base step and an inductive step. The base step is identical to weak mathematical induction, and it involves showing that the statement is true for some natural number (usually the number 1). The inductive step is a little different, and it involves showing that if the statement is true for all the natural numbers less than or equal to an arbitrary number $k$, then the statement is true for its successor $k+1$. This is often written as $(P(1) \wedge P(2) \wedge \ldots \wedge$ $P(k)) \rightarrow P(k+1) .$
4.2 Strong Induction
83
From the base step and the inductive step, we infer that the statement is true for all the natural numbers (that are greater than or equal to the number specified in the base case). Formally, the proof technique used in mathematical induction is of the form $^{2}$ :
$$(P(1) \wedge \forall k[(P(1) \wedge P(2) \wedge \ldots \wedge P(k)) \rightarrow P(k+1)]) \rightarrow \forall n P(n)$$
Strong and weak mathematical induction are equivalent in that any proof done by weak mathematical induction may also be considered a proof using strong induction, and a proof conducted with strong induction may also be converted into a proof using weak induction.

Weak mathematical induction is generally employed when it is reasonably clear how to prove $P(k+1)$ from $P(k)$, with strong mathematical typically employed where it is not so obvious. The validity of both forms of mathematical induction follows from the well-ordering property of the Natural Numbers, which states that every non-empty set has a least element.
Well-Ordering Principle
Every non-empty set of natural numbers has a least element. The well-ordering principle is equivalent to the principle of mathematical induction.

Example 4.3 Show that every natural number greater than one is dividie by prime number. Proof Base Case and is divisible by itself. and is divisible by itself.
Inductive Step (strong induction)
Suppose that the result is true for every number less than or equal to $k$. Then we consider $k+1$, and there are two cases to consider. If $k+1$ is prime, then it is divisible by itself. Otherwise, it is composite and it may be factored as the product of two numbers each of which is less than or equal to $k$. Each of these numbers is divisible by a prime number by the strong inductive hypothesis, and so $k+1$ is divisible by a prime number.

Thus, we have shown that if all the natural numbers less than or equal to $k$ are divisible by a prime number, then $k+1$ is divisible by a prime number. We have shown that the base case $\mathrm{P}(2)$ is true, and so it follows from strong mathematical induction that every natural number greater than one is divisible by some prime number.

## 图论代考

4.2 强感应
83

$$(P(1) \wedge \forall k[(P(1) \wedge P(2) \wedge \ldots \wedge P(k)) \rightarrow P(k+1)]) \rightarrow \forall n P( n)$$

## 密码学代考

• Cryptosystem
• A system that describes how to encrypt or decrypt messages
• Plaintext
• Message in its original form
• Ciphertext
• Message in its encrypted form
• Cryptographer
• Invents encryption algorithms
• Cryptanalyst
• Breaks encryption algorithms or implementations

## 编码理论代写

1. 数据压缩（或信源编码
2. 前向错误更正（或信道编码
3. 加密编码
4. 线路码