Problem 1.

$\quad$ Let $n \in \mathbf{N}$, and consider
$$1 \cdot 1 !+2 \cdot 2 !+3 \cdot 3 !+\cdots+n \cdot n !$$

1. Use the $\sum$ notation to express the above expression.
2. Find the formula for it.

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

1. 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$$
Problem 2.

$\quad$ Let $n \in \mathbf{N}$, and consider
$$\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)} \text {. }$$

1. Use the $\sum$ notation to express the expression above.
2. Find the formula for it.

$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)}$$

1. 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) .$$

Problem 3.

Prove that
$$\sum_{1 \leq k \leq n} k(k+1)=n(n+1)(n+2) / 3$$

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.
Problem 4.

Let $\lambda$ denote the empty string. Let $A$ be any finite nonempty set. A palindrome over $A$ can be defined as a string that reads the same forward as backward. For example, “mom” and “dad” are palindromes over the set of English alphabets.
We define a set $S$ as follows:

1. $\lambda \in S$
2. $\forall a \in A, a \in S$
3. $\forall a \in A \forall x \in S, a x a \in S$
4. All the elements in $S$ must be generated by the rules above.
Prove by structural induction that $S$ equals the set of all palindromes over $A$.

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™为您的留学生涯保驾护航。

# 概率论代考

## 离散数学代写

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

General Information

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

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.

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