这是离散数学课程的一份Mathematical Induction 作业代写案例

$1 .$ $1 \cdot 1 !+2 \cdot 2 !+3 \cdot 3 !+\cdots+n \cdot n !=\sum_{1 \leq k \leq n} k \cdot k !$

2. In order to obtain a closed form for the sum above, we note that $k=$ $(k+1)-1$ for any $k$. Thus,
   $$
   \begin{aligned}
   1 \cdot & 1 !+2 \cdot 2 !+3 \cdot 3 !+\cdots+n \cdot n ! \
   &=(2 \cdot 1 !-1 !)+(3 \cdot 2 !-2 !)+(4 \cdot 3 !-3 !)+\cdots+((n+1) \cdot n !-n !) \
   &=(2 !-1 !)+(3 !-2 !)+(4 !-3 !)+\cdots+((n+1) !-n !) \
   &=(n+1) !-1
   \end{aligned}
   $$
   Therefore,
   $$
   \sum_{1 \leq k \leq n} k \cdot k !=(n+1) !-1
   $$

$1 .$
$$
\frac{1}{1 \cdot 4}+\frac{1}{4 \cdot 7}+\frac{1}{7 \cdot 10}+\cdots+\frac{1}{(3 n-2) \cdot(3 n+1)}=\sum_{1 \leq k \leq n} \frac{1}{(3 k-2) \cdot(3 k+1)}
$$

2. In this problem we make use of the equality, for any $k, 1 \leq k \leq n$,
   $$
   \begin{aligned}
   \frac{1}{3}\left(\frac{1}{3 k-2}-\frac{1}{3 k+1}\right) &=\frac{1}{3} \frac{3 k+1-3 k+2}{(3 k-2)(3 k+1)} \
   &=\frac{1}{(3 k-2)(3 k+1)}
   \end{aligned}
   $$

$$
\begin{aligned}
\frac{1}{1 \cdot 4} &+\frac{1}{4 \cdot 7}+\frac{1}{7 \cdot 10}+\cdots+\frac{1}{(3 n-2) \cdot(3 n+1)} \
&=\frac{1}{3}\left(\frac{1}{1}-\frac{1}{4}\right)+\frac{1}{3}\left(\frac{1}{4}-\frac{1}{7}\right)+\frac{1}{3}\left(\frac{1}{7}-\frac{1}{10}\right)+\cdots+\frac{1}{3}\left(\frac{1}{3 n-2}-\frac{1}{3 n+1}\right) \
&=\frac{1}{3}\left(\frac{1}{1}-\frac{1}{4}+\frac{1}{4}-\frac{1}{7}+\frac{1}{7}-\frac{1}{10}+\cdots+\frac{1}{3 n-2}-\frac{1}{3 n+1}\right) \
&=\frac{1}{3}\left(1-\frac{1}{3 n+1}\right) .
\end{aligned}
$$
Therefore, the closed form expression of the sum is
$$
\sum_{1 \leq k \leq n} \frac{1}{(3 k-2) \cdot(3 k+1)}=\frac{1}{3}\left(1-\frac{1}{3 n+1}\right) .
$$

Solution 7: $\quad$ Let $D_{n}=\mathbf{N}$, and ${ }^{5}$
$$
P(n)^{6}: \sum_{1 \leq k \leq n} k(k+1)=\frac{1}{3} n(n+1)(n+2) .
$$

• Inductive Basis: $\quad n=1 .$
  $$
  1 \times 2=\frac{1}{3}(1 \times 2 \times 3)
  $$
  [The Basis Holds.]
  Therefore, $P(1)=T$.
• Inductive Hypothesis: Assume $P(n)=T$, i.e.
  $$
  \sum_{1 \leq k \leq n} k(k+1)=\frac{1}{3} n(n+1)(n+2) .
  $$

• Inductive Step: We want to prove that $P(n+1)=$ True. In other words, we want to prove that the following equality is correct:
  $$
  \begin{array}{rl}
  \sum_{1 \leq k \leq n+1} & k(k+1)=\frac{1}{3}(n+1)(n+2)(n+3) . \
  \sum_{1 \leq k \leq n+1} k(k+1) & =\left(\sum_{1 \leq k \leq n} k(k+1)\right)+(n+1)((n+1)+1) \
  & =\frac{n(n+1)(n+2)}{3}+(n+1)(n+2) \quad[\text { by } \quad \text { IH }] \
  & =\frac{n(n+1)(n+2)}{3}+(n+1)(n+2) \
  & =\frac{n(n+1)(n+2)+3(n+1)(n+2)}{3} \
  & =\frac{(n+1)(n+2)(n+3)}{3} \
  & =\frac{(n+1)((n+1)+1)((n+1)+2)}{3} \
  & =\frac{1}{3}(n+1)(n+2)(n+3) .
  \end{array}
  $$
  $$
  P(n+1)=T \text {. [The Inductive Step Holds.] }
  $$
  Therefore, $\forall n \in D_{n}, P(n)$ is true.

Let $A^{}$ denote the set of all possible strings made from $A$, where $\lambda \in A^{}$. Let $\mu$ range over $A^{}$, and let $|\mu|$ denote the length of $\mu$. We will prove the theorem by mathematical induction on the length of strings. Let us first define the domain and the predicate $P(n)$. $$ \begin{aligned} D_{n} &:{0,1,2,3, \ldots} \ P(n) &: \forall \mu \in A^{},[(|\mu|=n) \Rightarrow(\mu \in S \leftrightarrow \mu \text { is a palindrome })]
\end{aligned}
$$

• Inductive Basis: $n=0$ and $n=1$.
  By the definition of $S, \lambda \in S$, and by the definition of palindrome, $\lambda$ is also a palindrome. Therefore, $P(0)=T$.
  If $|\mu|=1$, then by rule 2 any single character from $A$ is in $P$, and it is also a palindrome over $A . P(1)=T$. [The Basis Holds.]
• Inductive Hypothesis: Let $i \in D_{n}$, and $1 \leq i$.
  Suppose if $n \leq i$, then $P(n)=T$, i.e.,
  $$
  \forall \mu \in A^{*},[(|\mu| \leq i) \Rightarrow(\mu \in S \leftrightarrow \mu \text { is a palindrome })] \text {. }
  $$
• Inductive Step: Let $n=i+1$. Because we assume that $1 \leq i$ in the hypothesis, we have $2 \leq n$. This will simplify our discussion because, as you will see, we don’t have to consider rules 1 and 2 in the course of the inductive step. Please note that this is valid, because the cases when $n=0$ and $n=1$ were proved in the basis step.
  Let $\mu \in A^{*}$ and $|\mu|=i+1$.

1. If $\mu \in S$, then $\mu$ must satisfy rule 3. Rules 1 and 2 are ruled out because $2 \leq|\mu|$. Thus, $\mu$ must be a string like $a \nu a$, where $a \in A$ and $\nu \in S$. We also know that $|\nu|=i-1$, and by the strong inductive hypothesis, $\nu \in S$ if and only if $\nu$ is a palindrome. Therefore, $\nu$ is a palindrome over $A$, and $a \nu a$ is also a palindrome over $A$. Therefore,
   $\mu \in S \rightarrow \mu$ is a palindrome.
2. If $\mu$ is a palindrome over $A$ and $2 \leq|\mu|, \mu$ must be a string like $a \nu a$, where $a \in A$ and $\nu$ is a palindrome over $A$. Since $|\nu|=i-1$, and by the strong inductive hypothesis, $\nu \in S$ if and only if $\nu$ is a palindrome. Therefore, $\nu \in S$, and by rule 3 , $a \nu a \in P$. Therefore,
   $\mu$ is a palindrome $\rightarrow \mu \in S$.
   $P(i+1)=T .$
   [The Inductive Step Holds.]

• Inductive Basis: By the definitions of $S$ and palindrome, $\lambda \in S$ and it is a palindrome. Thus, $P(\lambda)=T$. [The Basis Holds.]
• Inductive Hypothesis: Let $s \in A^{*}$, and assume $P(s)=T$, i.e.,
  $s \in S \leftrightarrow s$ is a palindrome.
• Inductive Step: Our task is to prove asa $\in S \leftrightarrow$ asa is a palindrome.
  We have two cases about $s$ : (1) $s \in S$, and (2) $s \notin S$.
  case $1: s \in S$. By the definition of $S, a s a \in S$. By the hypothesis, $s$ is a palindrome, and hence $a s a$ is also a palindrome. Thus,
  $$
  [\text { asa } \in S \rightarrow \text { asa is a palindrome }]=T .
  $$
  case 2: $s \notin S$. By the definition of $S$, asa $\notin S$. By the hypothesis, $s$ is not a palindrome, and hence $a s a$ is not a palindrome. Thus,
  $$
  [\text { asa } \notin S \rightarrow \text { asa is not a palindrome }]=T .
  $$
  By contrapositive, we have
  $$
  [\text { asa is a palindrome } \rightarrow \text { asa } \in S]=T \text {. }
  $$
  Together, we have $a s a \in S \leftrightarrow a s a$ is a palindrome.
  [The Inductive Step Holds.]

real analysis代写analysis 2, analysis 3请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

抽象代数Galois理论代写

偏微分方程代写成功案例

代数数论代考

概率论代考

离散数学代写

集合论数理逻辑代写案例

时间序列分析代写

离散数学网课代修

Announcements
Homework will be due 6pm (on Fridays).

General Information

Office Hours: MWF 4:30, TuTh 11:30.

• Course Outline

Monday  Mar28 – Last day to drop a course.
Tuesday Feb23 – Last day to drop a course without a W being recorded.
Monday Feb15 – Last day for 50% refund.
Monday Feb8 – Last day for 100% refund.

Advanced Help Sessions 

Math Help Sessions sometimes include Math510.
Sessions are held Mon-Fri  in CW41, for times see the
Math Help Sessions etc Schedule.

Homeworks

Note: Homework numbers refer to the Fifth Edition of Brualdi.

HW1. 1.8. 4a(also compute f(13)),12,16,17,34,42. 2.7. 1,4b,5b,6. (Fri 1/29).
HW2. 2.7. 7,9,12,13b,14,20,23,24,25,28,31,57. (Fri Feb 5).
HW3. 2.7. 19b,21,37,38,42,43,45,46,51,63. (Fri Feb 12).
HW4. 3.4.  5,7,9,10,14,16,17,19b,20,23. (Fri Feb 19).
HW5. Homework 5 (Due Fri Feb 26).
HW6. 5.7. 10,11,20,22,25,27,29,37,38,40. (Due Fri Mar 4).
HW7. 5.7. 36,47.  6.7. 2,3,5,6,8,9,13,17. (Due Fri Mar 11).
HW8. 6.7. 14,19,21,24ac,26,27,28,29,31,32. (Due Fri Mar 25).
HW9. 7.7. 1d,2,3c,5,9,11a,32,33,38e,39,40. (Due Fri Mar 32).
HW10. 7.7. 13bce, 14bde,15,18,34,36,47,52. (Due Fri Apr 8).
HW11. 7.7. 26,28,48d,51.  11.8. 2,6,9,11,12. (Due Fri April 15).
HW12. 11.8. 14,15,17,21,29,30,33,37,49ab. (Due Mon April 25).
HW13. 11.8. 20,44,47,54,55,56,62,64. (Due Fri April 29).
HW14. 13.4. 29,30. 9.4.1*,2*,6*,7*,19,25 (women choose).  Bonus questions: 12.7. 5,26,27. (Due Fri May 6).
For * questions use bipartite graphs & max-matchings instead of SDRs.
“Suppose aliens invade the earth and threaten to obliterate it in a year’s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world’s best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.”
Paul Erdős  – as quoted in “Ramsey Theory” by Ronald L. Graham and Joel H. Spencer, in Scientific American (July 1990), p. 112-117