text:
## Educators

Problem 1

There are infinitely many stations on a train route. Suppose that the train stops at the first station and suppose that if the train stops at a station, then it stops at the next station. Show that the train stops at all stations.

Prathan J.

Problem 2

Suppose that you know that a golfer plays the first hole of a golf course with an infinite number of holes and that if this golfer plays one hole, then the golfer goes on to play the next hole. Prove that this golfer plays every hole on the course.

Prathan J.

Problem 3

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Let $P(n)$ be the statement that $1^{2}+2^{2}+\cdots+n^{2}=n(n+$ 1$)(2 n+1) / 6$ for the positive integer $n .$
a) What is the statement $P(1) ?$
b) Show that $P(1)$ is true, completing the basis step of a proof that $P(n)$ is true for all positive integers $n .$
c) What is the inductive hypothesis of a proof that $P(n)$ is true for all positive integers $n ?$
d) What do you need to prove in the inductive step of a proof that $P(n)$ is true for all positive integers $n ?$
e) Complete the inductive step of a proof that $P(n)$ is true for all positive integers $n$ , identifying where you use the inductive hypothesis.
f) Explain why these steps show that this formula is true whenever $n$ is a positive integer.

Prathan J.

Problem 4

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Let $P(n)$ be the statement that $1^{3}+2^{3}+\cdots+n^{3}=(n(n+$ 1$) / 2 )^{2}$ for the positive integer $n .$
a) What is the statement $P(1) ?$
b) Show that $P(1)$ is true, completing the basis step of the proof of $P(n)$ for all positive integers $n .$
c) What is the inductive hypothesis of a proof that $P(n)$ is true for all positive integers $n$ ?
d) What do you need to prove in the inductive step of a proof that $P(n)$ is true all positive integers $n ?$
e) Complete the inductive step of a proof that $P(n)$ is true for all positive integers $n,$ identifying where you use the inductive hypothesis.
f) Explain why these steps show that this formula is true whenever $n$ is a positive integer.

Prathan J.

Problem 5

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that $1^{2}+3^{2}+5^{2}+\cdots+(2 n+1)^{2}=(n+1)(2 n+$ 1$)(2 n+3) / 3$ whenever $n$ is a nonnegative integer.

Prathan J.

Problem 6

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that $1 \cdot 1 !+2 \cdot 2 !+\cdots+n \cdot n !=(n+1) !-1$ whenever $n$ is a positive integer.

Prathan J.

Problem 7

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that $3+3 \cdot 5+3 \cdot 5^{2}+\cdots+3 \cdot 5^{n}=3\left(5^{n+1}-1\right) / 4$ whenever $n$ is a nonnegative integer.

Prathan J.

Problem 8

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that $2-2 \cdot 7+2 \cdot 7^{2}-\cdots+2(-7)^{n}=(1-$ $(-7)^{n+1} ) / 4$ whenever $n$ is a nonnegative integer.

Prathan J.

Problem 9

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
a) Find a formula for the sum of the first $n$ even positive integers.
b) Prove the formula that you conjectured in part (a).

Prathan J.

Problem 10

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
a) Find a formula for
$$\frac{1}{1 \cdot 2}+\frac{1}{2 \cdot 3}+\cdots+\frac{1}{n(n+1)}$$
by examining the values of this expression for small values of $n .$
b) Prove the formula you conjectured in part (a).

Prathan J.

Problem 11

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
a) Find a formula for
$$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^{n}}$$
by examining the values of this expression for small values of $n .$
b) Prove the formula you conjectured in part (a).

Prathan J.

Problem 12

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that
$$\sum_{j=0}^{n}\left(-\frac{1}{2}\right)^{j}=\frac{2^{n+1}+(-1)^{n}}{3 \cdot 2^{n}}$$
whenever $n$ is a nonnegative integer.

Prathan J.

Problem 13

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that $1^{2}-2^{2}+3^{2}-\cdots+(-1)^{n-1} n^{2}=(-1)^{n-1}$ $n(n+1) / 2$ whenever $n$ is a positive integer.

Prathan J.

Problem 14

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that for every positive integer $n, \sum_{k=1}^{n} k 2^{k}=$ $(n-1) 2^{n+1}+2$.

Prathan J.

Problem 15

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that for every positive integer $n$
$$1 \cdot 2+2 \cdot 3+\cdots+n(n+1)=n(n+1)(n+2) / 3$$

Prathan J.

Problem 16

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that for every positive integer $n$
\begin{aligned} 1 \cdot 2 \cdot 3+2 \cdot 3 \cdot 4+\cdots &+n(n+1)(n+2) \\ &=n(n+1)(n+2)(n+3) / 4 \end{aligned}

Prathan J.

Problem 17

Use mathematical induction in Exercises $3-17$ to prove summation formulae. Be sure to identify where you use the inductive hypothesis.
Prove that $\sum_{j=1}^{n} j^{4}=n(n+1)(2 n+1)\left(3 n^{2}+3 n-1\right) / 30$ whenever $n$ is a positive integer.

Check back soon!

Problem 18

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Let $P(n)$ be the statement that $n !<n^{n},$ where $n$ is an integer greater than $1 .$
a) What is the statement $P(2) ?$
b) Show that $P(2)$ is true, completing the basis step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than $1 .$
c) What is the inductive hypothesis of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1 ?
d) What do you need to prove in the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1$?$
e) Complete the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than $1 .$
f) Explain why these steps show that this inequality is true whenever $n$ is an integer greater than 1 .

Prathan J.

Problem 19

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Let $P(n)$ be the statement that
$$1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^{2}}<2-\frac{1}{n}$$
where $n$ is an integer greater than 1
a) What is the statement $P(2) ?$
b) Show that $P(2)$ is true, completing the basis step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1 .
c) What is the inductive hypothesis of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1$?$
d) What do you need to prove in the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than 1$?$
e) Complete the inductive step of a proof by mathematical induction that $P(n)$ is true for all integers $n$ greater than $1 .$
f) Explain why these steps show that this inequality is true whenever $n$ is an integer greater than 1 .

Prathan J.

Problem 20

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Prove that $3^{n}<n !$ if $n$ is an integer greater than 6

Prathan J.

Problem 21

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Prove that $2^{n}>n^{2}$ if $n$ is an integer greater than 4

Prathan J.

Problem 22

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
For which nonnegative integers $n$ is $n^{2} \leq n ! ?$ Prove your answer.

Prathan J.

Problem 23

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
For which nonnegative integers $n$ is $2 n+3 \leq 2^{n} ?$ Prove your answer.

Prathan J.

Problem 24

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Prove that $1 /(2 n) \leq[1 \cdot 3 \cdot 5 \cdots \cdot(2 n-1)] /(2 \cdot 4 \cdots .$ 2$n$ ) whenever $n$ is a positive integer.

Prathan J.

Problem 25

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Prove that if $h>-1$ , then $1+n h \leq(1+h)^{n}$ for all non-negative integers $n .$ This is called Bernoulli's inequality.

Prathan J.

Problem 26

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Suppose that $a$ and $b$ are real numbers with $0< b <a$ . Prove that if $n$ is a positive integer, then $a^{n}-b^{n} \leq$ $n a^{n-1}(a-b)$

Prathan J.

Problem 27

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Prove that for every positive integer $n,$
$\quad 1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{n}}>2(\sqrt{n+1}-1)$

Prathan J.

Problem 28

Use mathematical induction to prove the inequalities in Exercises $18-30 .$
Prove that $n^{2}-7 n+12$ is nonnegative whenever $n$ is an integer with $n \geq 3$ .

Prathan J.

Problem 29

In Exercises 29 and $30, H_{n}$ denotes the $n$ th harmonic number.
Prove that $H_{2^{n}} \leq 1+n$ whenever $n$ is a nonnegative integer.

Prathan J.

Problem 30

In Exercises 29 and $30, H_{n}$ denotes the $n$ th harmonic number.
Prove that
$$H_{1}+H_{2}+\cdots+H_{n}=(n+1) H_{n}-n$$

Prathan J.

Problem 31

Use mathematical induction in Exercises $31-37$ to prove divisibility facts.
Prove that 2 divides $n^{2}+n$ whenever $n$ is a positive integer.

Prathan J.

Problem 32

Use mathematical induction in Exercises $31-37$ to prove divisibility facts.
Prove that 3 divides $n^{3}+2 n$ whenever $n$ is a positive integer.

Prathan J.

Problem 33

Use mathematical induction in Exercises $31-37$ to prove divisibility facts.
Prove that 5 divides $n^{5}-n$ whenever $n$ is a nonnegative integer.

Prathan J.

Problem 34

Use mathematical induction in Exercises $31-37$ to prove divisibility facts.
Prove that 6 divides $n^{3}-n$ whenever $n$ is a nonnegative integer.

Prathan J.

Problem 35

Use mathematical induction in Exercises $31-37$ to prove divisibility facts.
Prove that $n^{2}-1$ is divisible by 8 whenever $n$ is an odd positive integer.

Prathan J.

Problem 36

Use mathematical induction in Exercises $31-37$ to prove divisibility facts.
Prove that 21 divides $4^{n+1}+5^{2 n-1}$ whenever $n$ is a positive integer.

Prathan J.

Problem 37

Use mathematical induction in Exercises $31-37$ to prove divisibility facts.
Prove that if $n$ is a positive integer, then 133 divides $11^{n+1}+12^{2 n-1} .$

Prathan J.

Problem 38

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that if $A_{1}, A_{2}, \ldots, A_{n}$ and $B_{1}, B_{2}, \ldots, B_{n}$ are sets such that $A_{j} \subseteq B_{j}$ for $j=1,2, \ldots, n,$ then
$$\bigcup_{j=1}^{n} A_{j} \subseteq \bigcup_{j=1}^{n} B_{j}$$

Prathan J.

Problem 39

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that if $A_{1}, A_{2}, \ldots, A_{n}$ and $B_{1}, B_{2}, \ldots, B_{n}$ are sets such that $A_{j} \subseteq B_{j}$ for $j=1,2, \ldots, n,$ then
$$\bigcap_{j=1}^{n} A_{j} \subseteq \bigcap_{j=1}^{n} B_{j}$$

Prathan J.

Problem 40

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that if $A_{1}, A_{2}, \ldots, A_{n}$ and $B$ are sets, then
\begin{aligned}\left(A_{1} \cap A_{2} \cap \cdots \cap A_{n}\right) \cup B & \\=\left(A_{1} \cup B\right) \cap\left(A_{2} \cup B\right) \cap \cdots \cap\left(A_{n} \cup B\right) \end{aligned}

Prathan J.

Problem 41

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that if $A_{1}, A_{2}, \ldots, A_{n}$ and $B$ are sets, then
\begin{aligned}\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) \cap B & \\=\left(A_{1} \cap B\right) \cup\left(A_{2} \cap B\right) \cup \cdots \cup\left(A_{n} \cap B\right) \end{aligned}

Prathan J.

Problem 42

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that if $A_{1}, A_{2}, \ldots, A_{n}$ and $B$ are sets, then
\begin{aligned}\left(A_{1}-B\right) \cap\left(A_{2}-B\right) \cap \cdots \cap\left(A_{n}-B\right) \\=\left(A_{1} \cap A_{2} \cap \cdots \cap A_{n}\right)-B \end{aligned}

Prathan J.

Problem 43

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that if $A_{1}, A_{2}, \ldots, A_{n}$ are subsets of a universal set $U,$ then
$$\bigcup_{k=1}^{n} A_{k}=\bigcap_{k=1}^{n} \overline{A_{k}}$$

Check back soon!

Problem 44

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that if $A_{1}, A_{2}, \ldots, A_{n}$ and $B$ are sets, then
\begin{aligned}\left(A_{1}-B\right) \cup\left(A_{2}-B\right) \cup \cdots \cup\left(A_{n}-B\right) \\=\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right)-B \end{aligned}

Prathan J.

Problem 45

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that a set with $n$ elements has $n(n-1) / 2$ subsets containing exactly two elements whenever $n$ is an integer greater than or equal to $2 .$

Prathan J.

Problem 46

Use mathematical induction in Exercises $38-46$ to prove results about sets.
Prove that a set with $n$ elements has $n(n-1)(n-2) / 6$ subsets containing exactly three elements whenever $n$ is an integer greater than or equal to $3 .$

Prathan J.

Problem 47

In Exercises 47 and 48 we consider the problem of placing towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a tower.
Devise a greedy algorithm that uses the minimum number of towers possible to provide cell service to $d$ buildings located at positions $x_{1}, x_{2}, \ldots, x_{d}$ from the start of the road. [Hint: At each step, go as far as possible along the road before adding a tower so as not to leave any buildings without coverage.]

Check back soon!

Problem 48

In Exercises 47 and 48 we consider the problem of placing towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a tower.
Use mathematical induction to prove that the algorithm you devised in Exercise 47 produces an optimal solution, that is, that it uses the fewest towers possible to provide cellular service to all buildings.

Check back soon!

Problem 49

Exercises $49-51$ present incorrect proofs using mathematical induction. You will need to identify an error in reasoning in each exercise.
What is wrong with this "proof" that all horses are the same color? Let $P(n)$ be the proposition that all the horses in a set of $n$ horses are the same color.
Basis Step: Clearly, $P(1)$ is true.
Inductive Step: Assume that $P(k)$ is true, so that all the horses in any set of $k$ horses are the same color. Consider any $k+1$ horses; number these as horses $1,2,3, \ldots, k, k+1 .$ Now the first $k$ of these horses all must have the same color, and the last $k$ of these must also have the same color. Because the set of the first $k$ horses and the set of the last $k$ horses overlap, all $k+1$ must be the same color. This shows that $P(k+1)$ is true and finishes the proof by induction.

Prathan J.

Problem 50

Exercises $49-51$ present incorrect proofs using mathematical induction. You will need to identify an error in reasoning in each exercise.
What is wrong with this "proof"?
"Theorem" For every positive integer $n, \sum_{i=1}^{n} i=$ $\left(n+\frac{1}{2}\right)^{2} / 2 .$
Basis Step: The formula is true for $n=1$ .
Inductive Step: Suppose that $\sum_{i=1}^{n} i=\left(n+\frac{1}{2}\right)^{2} / 2$ Then $\sum_{i=1}^{n+1} i=\left(\sum_{i=1}^{n} i\right)+(n+1) .$ By the inductive hypothesis, we have $\sum_{i=1}^{n+1} i=\left(n+\frac{1}{2}\right)^{2} / 2+n+1=$ $\left(n^{2}+n+\frac{1}{4}\right) / 2+n+1=\left(n^{2}+3 n+\frac{9}{4}\right) / 2=$ $\left(n+\frac{3}{2}\right)^{2} / 2=\left[(n+1)+\frac{1}{2}\right]^{2} / 2,$ completing the inductive step.

Prathan J.

Problem 51

Exercises $49-51$ present incorrect proofs using mathematical induction. You will need to identify an error in reasoning in each exercise.
What is wrong with this "proof"?
"Theorem" For every positive integer $n,$ if $x$ and $y$ are
positive integers with max $(x, y)=n$ , then $x=y$ .
Basis Step: Suppose that $n=1 .$ If $\max (x, y)=1$ and $x$
and $y$ are positive integers, we have $x=1$ and $y=1$ .
Inductive Step: Let $k$ be a positive integer. Assume that whenever max $(x, y)=k$ and $x$ and $y$ are positive integers, then $x=y .$ Now let max $(x, y)=k+1,$ where $x$ and $y$ are positive integers. Then $\max (x-1, y-1)=k,$ so by the inductive hypothesis, $x-1=y-1 .$ It follows that $x=y$ completing the inductive step.

Prathan J.

Problem 52

Suppose that $m$ and $n$ are positive integers with $m>n$ and $f$ is a function from $\{1,2, \ldots, m\}$ to $\{1,2, \ldots, n\} .$ Use mathematical induction on the variable $n$ to show that $f$ is not one-to-one.

Prathan J.

Problem 53

Use mathematical induction to show that $n$ people can divide a cake (where each person gets one or more separate pieces of the cake) so that the cake is divided fairly, that is, in the sense that each person thinks he or she got at least $(1 / n)$ th of the cake. [Hint: For the inductive step, take a fair division of the cake among the first $k$ people, have each person divide their share into what this person thinks are $k+1$ equal portions, and then have the $(k+1)$ st person select a portion from each of the $k$ people. When showing this produces a fair division for $k+1$ people, suppose that person $k+1$ thinks that person $i$ got $p_{i}$ of the cake, where $\sum_{i=1}^{k} p_{i}=1 . ]$

Prathan J.

Problem 54

Use mathematical induction to show that given a set of $n+1$ positive integers, none exceeding $2 n,$ there is at least one integer in this set that divides another integer in the set.

Prathan J.

Problem 55

A knight on a chessboard can move one space horizontally (in either direction) and two spaces vertically (in either direction) or two spaces horizontally (in either direction) and one space vertically (in either direction). Suppose that we have an infinite chessboard, made up of all squares $(m, n),$ where $m$ and $n$ are nonnegative integers that denote the row number and the column number of the square, respectively. Use mathematical induction to show that a knight starting at $(0,0)$ can visit every square using a finite sequence of moves. [Hint: Use induction on the variable $s=m+n . ]$

Prathan J.

Problem 56

Suppose that
$$\mathbf{A}=\left[\begin{array}{ll}{a} & {0} \\ {0} & {b}\end{array}\right]$$
where $a$ and $b$ are real numbers. Show that
$$\mathbf{A}^{n}=\left[\begin{array}{cc}{a^{n}} & {0} \\ {0} & {b^{n}}\end{array}\right]$$
for every positive integer $n .$

Prathan J.

Problem 57

(Requires calculus) Use mathematical induction to prove that the derivative of $f(x)=x^{n}$ equals $n x^{n-1}$ whenever $n$ is a positive integer. (For the inductive step, use the product rule for derivatives.)

Prathan J.

Problem 58

Suppose that $A$ and $B$ are square matrices with the property $A B=B A .$ Show that $A B^{n}=B^{n} A$ for every positive integer $n .$

Prathan J.

Problem 59

Suppose that $m$ is a positive integer. Use mathematical induction to prove that if $a$ and $b$ are integers with $a \equiv b$ $(\bmod m),$ then $a^{k} \equiv b^{k}(\bmod m)$ whenever $k$ is a nonnegative integer.

Prathan J.

Problem 60

Use mathematical induction to show that $\neg\left(p_{1} \vee p_{2} \vee\right.$ $\cdots \vee p_{n} )$ is equivalent to $\neg p_{1} \wedge \neg p_{2} \wedge \cdots \wedge \neg p_{n}$ whenever $p_{1}, p_{2}, \ldots, p_{n}$ are propositions.

Prathan J.

Problem 61

Show that
$\left[\left(p_{1} \rightarrow p_{2}\right) \wedge\left(p_{2} \rightarrow p_{3}\right) \wedge \cdots \wedge\left(p_{n-1} \rightarrow p_{n}\right)\right]$
$\quad \rightarrow\left[\left(p_{1} \wedge p_{2} \wedge \cdots \wedge p_{n-1}\right) \rightarrow p_{n}\right]$
is a tautology whenever $p_{1}, p_{2}, \ldots, p_{n}$ are propositions, where $n \geq 2$

Prathan J.

Problem 62

Show that $n$ lines separate the plane into $\left(n^{2}+n+2\right) / 2$ regions if no two of these are parallel and no three pass through a common point.

Prathan J.

Problem 63

Let $a_{1}, a_{2}, \ldots, a_{n}$ be positive real numbers. The arithmetic mean of these numbers is defined by
$$A=\left(a_{1}+a_{2}+\cdots+a_{n}\right) / n$$
and the geometric mean of these numbers is defined by
$$G=\left(a_{1} a_{2} \cdots a_{n}\right)^{1 / n} .$$
Use mathematical induction to prove that $A \geq G$ .

Check back soon!

Problem 64

Use mathematical induction to prove Lemma 3 of Section $4.3,$ which states that if $p$ is a prime and $p | a_{1} a_{2} \cdots a_{n},$ where $a_{i}$ is an integer for $i=1,2,3, \ldots, n,$ then $p | a_{i}$ for some integer $i .$

Prathan J.

Problem 65

Show that if $n$ is a positive integer, then
$$_{\left\{a_{1}, \ldots, a_{k}\right\} \subseteq\{1,2, \ldots, n\}} \frac{1}{a_{1} a_{2} \cdots a_{k}}=n$$
(Here the sum is over all nonempty subsets of the set of the $n$ smallest positive integers.)

Check back soon!

Problem 66

Use the well-ordering property to show that the following form of mathematical induction is a valid method to prove that $P(n)$ is true for all positive integers $n .$
Basis Step: $P(1)$ and $P(2)$ are true.
Inductive Step: For each positive integer $k,$ if $P(k)$ and $P(k+1)$ are both true, then $P(k+2)$ is true.

Prathan J.

Problem 67

Show that if $A_{1}, A_{2}, \ldots, A_{n}$ are sets where $n \geq 2,$ and for all pairs of integers $i$ and $j$ with $1 \leq i<j \leq n$ , either $A_{i}$ is a subset of $A_{j}$ or $A_{j}$ is a subset of $A_{i},$ then there is an integer $i, 1 \leq i \leq n,$ such that $A_{i}$ is a subset of $A_{j}$ for all integers $j$ with $1 \leq j \leq n$.

Prathan J.

Problem 68

A guest at a party is a celebrity if this person is known by every other guest, but knows none of them. There is at most one celebrity at a party, for if there were two, they would know each other. A particular party may have no celebrity. Your assignment is to find the celebrity, if one exists, at a party, by asking only one type of question asking a guest whether they know a second guest. Everyone must answer your questions truthfully. That is, if Alice and Bob are two people at the party, you can ask Alice whether she knows Bob; she must answer correctly. Use mathematical induction to show that if there are $n$ people at the party, then you can find the celebrity, if there is one, with 3$(n-1)$ questions. [Hint: First ask a question to eliminate one person as a celebrity. Then use the inductive hypothesis to identify a potential celebrity. Finally, ask two more questions to determine whether that person is actually a celebrity. $]$

Check back soon!

Problem 69

Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all scandals each knows about. For example, on the first call, two people share information, so by the end of the call, each of these people knows about two scandals. The gossip problem asks for $G(n),$ the minimum number of telephone calls that are needed for all $n$ people to learn about all the scandals. Exercises $69-71$ deal with the gossip problem.
Find $G(1), G(2), G(3),$ and $G(4)$

Prathan J.

Problem 70

Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all scandals each knows about. For example, on the first call, two people share information, so by the end of the call, each of these people knows about two scandals. The gossip problem asks for $G(n),$ the minimum number of telephone calls that are needed for all $n$ people to learn about all the scandals. Exercises $69-71$ deal with the gossip problem.
Use mathematical induction to prove that $G(n) \leq 2 n-4$ for $n \geq 4 .$ [Hint: In the inductive step, have a new person call a particular person at the start and at the end. $]$

Prathan J.

Problem 71

Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they share information about all scandals each knows about. For example, on the first call, two people share information, so by the end of the call, each of these people knows about two scandals. The gossip problem asks for $G(n),$ the minimum number of telephone calls that are needed for all $n$ people to learn about all the scandals. Exercises $69-71$ deal with the gossip problem.
Prove that $G(n)=2 n-4$ for $n \geq 4$

Prathan J.

Problem 72

Show that it is possible to arrange the numbers $1,2, \ldots, n$ in a row so that the average of any two of these numbers never appears between them. [Hint: Show that it suffices to prove this fact when $n$ is a power of $2 .$ Then use mathematical induction to prove the result when $n$ is a power of 2.]

Check back soon!

Problem 73

Show that if $I_{1}, I_{2}, \ldots, I_{n}$ is a collection of open intervals on the real number line, $n \geq 2,$ and every pair of these intervals has a nonempty intersection, that is, $I_{i} \cap I_{j} \neq \emptyset$ whenever $1 \leq i \leq n$ and $1 \leq j \leq n,$ then the intersection of all these sets is nonempty, that is, $I_{1} \cap I_{2} \cap \cdots \cap I_{n} \neq \emptyset$ . (Recall that an open interval is the set of real numbers $x$ with $a< x <b,$ where $a$ and $b$ are real numbers with $a<b .$ .

Prathan J.

Problem 74

Sometimes we cannot use mathematical induction to prove a result we believe to be true, but we can use mathematical induction to prove a stronger result. Because the inductive hypothesis of the stronger result provides more to work with, this process is called inductive loading. We use inductive loading in Exercise $74-76$ .
Show that we cannot use mathematical induction to prove that $\sum_{j=1}^{n} 1 / j^{2}<2$ for all positive integers $n$ , but that this inequality is a consequence of the inequality proved by mathematical induction in Exercise $19 .$

Check back soon!

Problem 75

Sometimes we cannot use mathematical induction to prove a result we believe to be true, but we can use mathematical induction to prove a stronger result. Because the inductive hypothesis of the stronger result provides more to work with, this process is called inductive loading. We use inductive loading in Exercise $74-76$ .
Suppose that we want to prove that
$$\sum_{j=1}^{n} j /(j+1) !<1$$
for all positive integers $n .$
a) Show that if we try to prove this inequality using mathematical induction, the basis step works, but the inductive step fails.
b) Show that mathematical induction can be used to prove the stronger inequality
$$\sum_{j=1}^{n} j /(j+1) ! \leq 1-1 /(n+1) !$$
for all positive integers $n,$ implying that the weaker inequality is also true.

Check back soon!

Problem 76

Sometimes we cannot use mathematical induction to prove a result we believe to be true, but we can use mathematical induction to prove a stronger result. Because the inductive hypothesis of the stronger result provides more to work with, this process is called inductive loading. We use inductive loading in Exercise $74-76$ .
Suppose that we want to prove that
$$\frac{1}{2} \cdot \frac{3}{4} \cdots \frac{2 n-1}{2 n}<\frac{1}{\sqrt{3 n}}$$
for all positive integers $n .$
a) Show that if we try to prove this inequality using mathematical induction, the basis step works, but the inductive step fails.
b) Show that mathematical induction can be used to prove the stronger inequality
$$\frac{1}{2} \cdot \frac{3}{4} \dots \frac{2 n-1}{2 n}<\frac{1}{\sqrt{3 n+1}}$$
for all integers $n$ greater than $1,$ which, together with a verification for the case where $n=1$ , establishes the weaker inequality we originally tried to prove using mathematical induction.

Prathan J.

Problem 77

Let $n$ be an even integer. Show that it is possible for $n$ people to stand in a yard at mutually distinct distances so that when each person throws a pie at their nearest neighbor, everyone is hit by a pie.

Prathan J.

Problem 78

Construct a tiling using right triominoes of the $4 \times 4$ checkerboard with the square in the upper left corner removed.

Prathan J.

Problem 79

Construct a tiling using right triominoes of the $8 \times 8$ checkerboard with the square in the upper left corner removed.

Prathan J.

Problem 80

Prove or disprove that all checkerboards of these shapes can be completely covered using right triominoes whenever $n$ is a positive integer.
$\begin{array}{ll}{\text { a) } 3 \times 2^{n}} & {\text { b) } 6 \times 2^{n}} \\ {\text { c) } 3^{n} \times 3^{n}} & {\text { d) } 6^{n} \times 6^{n}}\end{array}$

Prathan J.

Problem 81

Show that a three-dimensional $2^{n} \times 2^{n} \times 2^{n}$ checkerboard with one $1 \times 1 \times 1$ cube missing can be completely covered by $2 \times 2 \times 2$ cubes with one $1 \times 1 \times 1$ cube removed.

Check back soon!

Problem 82

Show that an $n \times n$ checkerboard with one square removed can be completely covered using right triominoes if $n>5, n$ is odd, and $3 \not{|}$ $n.$

Check back soon!

Problem 83

Show that a $5 \times 5$ checkerboard with a corner square removed can be tiled using right triominoes.

Prathan J.

Problem 84

Find a $5 \times 5$ checkerboard with a square removed that cannot be tiled using right triominoes. Prove that such a tiling does not exist for this board.

Prathan J.
Use the principle of mathematical induction to show that $P(n)$ is true for $n=b, b+1, b+2, \ldots,$ where $b$ is an integer, if $P(b)$ is true and the conditional statement $P(k) \rightarrow$ $P(k+1)$ is true for all integers $k$ with $k \geq b$ .


text:
Session 1 - Chromosphere, Corona, Flares.
Display session, Friday, June 27
Ballroom B, Chair: Charles Kankelborg

## [1.20] Wave Propagation in the Chromosphere and Transition Region: Where Have All the Shock Waves Gone?

B. Fleck (ESA/SSD), S. Steffens, F. -L. Deubner (Univ. Würzburg), K. Wilhelm (MPAe), R. Harrison (RAL), J. Gurman (NASA/GSFC)

We present first results from a joint observing program (SOHO JOP 26) involving SUMER, CDS and EIT on SOHO, coordinated with ground-based observations at the Vacuum Tower Telescope at Izaña, Tenerife. The objective of this study is to characterize the wave propagation properties in the solar atmosphere, from the photosphere through the chromosphere up into the transition region. Particular emphasis is laid on the 3-min shock waves observed in the Ca II K line. How do they impact the transition region and what signature do they leave there and in the lower corona?

The ground-based measurements comprise high resolution time series (both filtergrams and spectrograms) in Ca II K, H\,\alpha and Mg\,b_2. With SUMER we ran four sequences covering different temperature regimes: a) O I 1302, O I 1306, Si II 1309, C I 1311, C II 1334, C II 1335, b) Si I 1256, N V 1242, O V 629 c) He I 584, C III 1175, O I 1152, d) H I 1025, O VI 1031, O VI 1037. With CDS we took spectral time series in O VI 554, He I 584, He II 607, Mg IX 368, and O V 629 as well as wide-slit (90\times240'') movies'' in He I 584, Mg IX 368 and O V 629, while EIT ran sub-field high cadence sequences in He II 304.

format: plain


text:
### Session PI2: Tokamak Physics: Edge, Scrape-off Layer and Wall

2:00 PM–5:00 PM, Wednesday, November 4, 2009
Room: Centennial I

Chair: Andrea Garofalo, General Atomics

Abstract ID: BAPS.2009.DPP.PI2.2

### Abstract: PI2.00002 : ELM mitigation studies in JET and implications for ITER

2:30 PM–3:00 PM

Preview Abstract MathJax On | Off   Abstract

#### Author:

Elena de la Luna
(Laboratorio Nacional de Fusion, Asociacion EURATOM/CIEMAT, Madrid-28040, Spain)

Type I edge localized modes (ELMs) remain a serious concern for ITER because of the high transient heat and particle flux that can lead to rapid erosion of the divertor plates. This has stimulated worldwide research on exploration of different methods to avoid or at least mitigate the ELM energy loss while maintaining adequate confinement. ITER will require reliable ELM control over a wide range of operating conditions, including changes in the edge safety factor, therefore a suite of different techniques is highly desirable. In JET several techniques have been demonstrated for control the frequency and size of type I ELMs, including resonant perturbations of the edge magnetic field (RMP), ELM magnetic triggering by fast vertical movement of the plasma column (vertical kicks'') and ELM pacing using pellet injection. In this paper we present results from recent dedicated experiments in JET focusing on integrating the different ELM mitigation methods into similar plasma scenarios. Plasma parameter scans provide comparison of the performance of the different techniques in terms of both the reduction in ELM size and on the impact of each control method on plasma confinement. The compatibility of different ELM mitigation schemes has also been investigated. The plasma response to RMP and vertical kicks during the ELM mitigation phase shares common features: the reduction in ELM size (up to a factor of 3) is accompanied by a reduction in pedestal pressure (mainly due to a loss of density) with only minor ($<$ 10\%) reduction of the stored energy. Interestingly, it has been found that the combined application of RMP and kicks leads to a reduction of the threshold perturbation level (vertical displacement in the case of the kicks) necessary for the ELM mitigation to occur. The implication of these results for ITER will be discussed.

To cite this abstract, use the following reference: http://meetings.aps.org/link/BAPS.2009.DPP.PI2.2


text:
# Leslie Matrix

• Jun 11th 2009, 11:38 PM
popsterrockz
Leslie Matrix
I have a difficulty to solve this problem. I wonder how am i going to find a matrix factor that if i multiply it by a 12x12 leslie matrix, will give me almost the same leslie matrix but doubled the breeding rate. this is the Leslie Matrix 1:
http://i596.photobucket.com/albums/t...errockz/L1.jpg
and this is what we should get after multiplying a matrix factor to L1:
L2: http://i596.photobucket.com/albums/t...errockz/L2.jpg
oh please i really need it 2 days from now
• Jun 12th 2009, 03:07 PM
CaptainBlack
Quote:

Originally Posted by popsterrockz
I have a difficulty to solve this problem. I wonder how am i going to find a matrix factor that if i multiply it by a 12x12 leslie matrix, will give me almost the same leslie matrix but doubled the breeding rate. this is the Leslie Matrix 1:
http://i596.photobucket.com/albums/t...errockz/L1.jpg
and this is what we should get after multiplying a matrix factor to L1:
L2: http://i596.photobucket.com/albums/t...errockz/L2.jpg
oh please i really need it 2 days from now

I'm not sure that I understand what you are asking for, what is wrong with:

$
\left[ \begin{array}{cc}2&{\bf{0}}_{1\times 11}\\
{\bf{0}}_{11 \times 1}&{\bf{I}}_{11 \times 11} \end{array}
\right]
$

CB


text:
# How would we represent the combustion of paper?

Jul 3, 2017

Well, paper is $\text{cellulose}$, i.e. ${\left({C}_{6} {H}_{10} {O}_{5}\right)}_{n}$
${\left({C}_{6} {H}_{10} {O}_{5}\right)}_{n} \left(s\right) + 6 n {O}_{2} \left(g\right) \rightarrow 6 n C {O}_{2} \left(g\right) + 5 n {H}_{2} O \left(l\right) + \Delta$
Is this stoichiometrically balanced......? What does the $\Delta$ symbol mean in this scenario?


text:
# Determining the remainder of a small integer n raised to a high power when divided by m

I recently took a test that asked me to determine the value of $3^{82} \mod 5$.

I was unable to figure out how to do it on the test, but when I got home I noticed that there is a pattern to the remainders of $3^n$,

• $3^{1} \mod 5 = 3$
• $3^{2} \mod 5 = 4$
• $3^{3} \mod 5 = 2$
• $3^{4} \mod 5 = 1$
• $3^{5} \mod 5 = 3$
• $3^{6} \mod 5 = 4$
• $3^{7} \mod 5 = 2$
• $3^{8} \mod 5 = 1$
• $3^{9} \mod 5 = 3$

Is the best strategy to follow this pattern up to the $82^{\text{nd}}$ remainder (obviously in an intelligent way) or is there some much more obvious trick to this question that I missed?

-

As you have observed $$3^4 \equiv 1 \pmod 5$$ This means that $$3^{4k} \equiv 1 \pmod 5$$ Hence, $$3^{80} \equiv 1 \pmod 5 \implies 3^{82} \equiv 3^2 \pmod{5} = 4 \pmod 5$$ In general, $$3^{4k + r} \equiv 3^r \pmod{5}$$
Thank you for your answer. It's not entirely clear to me how $3^4 \mod 1 \equiv 1$ tells us that $3^{4k} \mod 1 \equiv 1$. Could you explain this step? –  crazedgremlin Nov 7 '12 at 1:07
@crazedgremlin $\rm\: \color{#0A0}{3^4}\equiv\color{#C00} 1\:\Rightarrow\: 3^{4k} = (\color{#0A0}{3^4})^k\equiv \color{#C00}1^k\equiv 1\:$ by the Congruence Product Rule. It is essential to learn the arithmetic of congruences, as opposed to less flexible mod operations. –  Bill Dubuque Nov 7 '12 at 1:23


text:
Unity my c++ d c# benchmark!

Recommended Posts

Today I saw the D's pi computing sample (\dmd\samples\d\pi.d) and thought that porting it to c++ and c# for making a little benchmark should be easy: d:
import std.c.stdio;
import std.c.stdlib;
import std.c.time;

const int LONG_TIME=4000;

byte[] p;
byte[] t;
int q;

int main(char[][] args)
{
int startime, endtime;
int i;

if (args.length == 2) {
sscanf(&args[1][0],"%d",&q);
} else {
printf("Usage: pi [precision]\n");
exit(55);
}

if (q < 0)
{
printf("Precision was too low, running with precision of 0.\n");
q = 0;
}

if (q > LONG_TIME)
{
printf("Be prepared to wait a while...\n");
}

// Compute one more digit than we display to compensate for rounding
q++;

p.length = q + 1;
t.length = q + 1;

/* compute pi */

std.c.time.time(&startime);
arctan(2);
arctan(3);
mul4();
std.c.time.time(&endtime);

q--;

/* print pi */

printf("pi = %d.",cast(int)(p[0]));
for (i = 1; i <= q; i++)
printf("%d",cast(int)(p[i]));
printf("\n");
printf("%ld seconds to compute pi with a precision of %d digits.\n",endtime-startime,q);

return 0;
}

void arctan(int s)
{
int n;

t[0] = 1;
div(s); /* t[] = 1/s */
n = 1;
do {
mul(n);
div(s * s);
div(n += 2);
if (((n-1) / 2) % 2 == 0)
else
sub();
} while (!tiszero());
}

{
int j;

for (j = q; j >= 0; j--)
{
if (t[j] + p[j] > 9) {
p[j] += t[j] - 10;
p[j-1] += 1;
} else
p[j] += t[j];
}
}

void sub()
{
int j;

for (j = q; j >= 0; j--)
if (p[j] < t[j]) {
p[j] -= t[j] - 10;
p[j-1] -= 1;
} else
p[j] -= t[j];
}

void mul(int multiplier)
{
int b;
int i;
int carry = 0, digit = 0;

for (i = q; i >= 0; i--) {
b = (t[i] * multiplier + carry);
digit = b % 10;
carry = b / 10;
t[i] = digit;
}
}

/* t[] /= l */

void div(int divisor)
{
int i, b;
int quotient, remainder = 0;

for (i = 0; i <= q; i++) {
b = (10 * remainder + t[i]);
quotient = b / divisor;
remainder = b % divisor;
t[i] = quotient;
}
}

void div4()
{
int i, c, d = 0;

for (i = 0; i <= q; i++) {
c = (10 * d + p[i]) / 4;
d = (10 * d + p[i]) % 4;
p[i] = c;
}
}

void mul4()
{
int i, c, d;

d = c = 0;

for (i = q; i >= 0; i--) {
d = (p[i] * 4 + c) % 10;
c = (p[i] * 4 + c) / 10;
p[i] = d;
}
}

int tiszero()
{
int k;

for (k = 0; k <= q; k++)
if (t[k] != 0)
return false;
return true;
}

(I compiled pi.d with dmd -O -release pi.d) c++:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LONG_TIME 4000

__int8* p;
__int8* t;
int q;

void arctan(int s);
void sub();
void mul(int);
void div(int);
void mul4();
void div4();
int tiszero();

int main(int argv,char** args)
{
time_t startime, endtime;
int i;

if (argv == 2) {
sscanf(&args[1][0],"%d",&q);
} else {
printf("Usage: pi [precision]\n");
exit(55);
}

if (q < 0)
{
printf("Precision was too low, running with precision of 0.\n");
q = 0;
}

if (q > LONG_TIME)
{
printf("Be prepared to wait a while...\n");
}

// Compute one more digit than we display to compensate for rounding
q++;

p = new __int8[ q + 1 ];
t = new __int8[ q + 1 ];
for(int tt=0;tt<=q;tt++)
{
p[tt]=0;
t[tt]=0;
}
/* compute pi */

time(&startime);
arctan(2);
arctan(3);
mul4();
time(&endtime);

q--;

/* print pi */

printf("pi = %d.",(int)(p[0]));
for (i = 1; i <= q; i++)
printf("%d",(int)(p[i]));
printf("\n");
printf("%ld seconds to compute pi with a precision of %d digits.\n",(long)endtime-(long)startime,q);

delete [] p;
delete [] t;
return 0;
}

void arctan(int s)
{
int n;

t[0] = 1;
div(s); /* t[] = 1/s */
n = 1;
do {
mul(n);
div(s * s);
div(n += 2);
if (((n-1) / 2) % 2 == 0)
else
sub();
} while (!tiszero());
}

{
int j;

for (j = q; j >= 0; j--)
{
if (t[j] + p[j] > 9) {
p[j] += t[j] - 10;
p[j-1] += 1;
} else
p[j] += t[j];
}
}

void sub()
{
int j;

for (j = q; j >= 0; j--)
if (p[j] < t[j]) {
p[j] -= t[j] - 10;
p[j-1] -= 1;
} else
p[j] -= t[j];
}

void mul(int multiplier)
{
int b;
int i;
int carry = 0, digit = 0;

for (i = q; i >= 0; i--) {
b = (t[i] * multiplier + carry);
digit = b % 10;
carry = b / 10;
t[i] = digit;
}
}

/* t[] /= l */

void div(int divisor)
{
int i, b;
int quotient, remainder = 0;

for (i = 0; i <= q; i++) {
b = (10 * remainder + t[i]);
quotient = b / divisor;
remainder = b % divisor;
t[i] = quotient;
}
}

void div4()
{
int i, c, d = 0;

for (i = 0; i <= q; i++) {
c = (10 * d + p[i]) / 4;
d = (10 * d + p[i]) % 4;
p[i] = c;
}
}

void mul4()
{
int i, c, d;

d = c = 0;

for (i = q; i >= 0; i--) {
d = (p[i] * 4 + c) % 10;
c = (p[i] * 4 + c) / 10;
p[i] = d;
}
}

int tiszero()
{
int k;

for (k = 0; k <= q; k++)
if (t[k] != 0)
return false;
return true;
}

c#:
using System;
using System.Diagnostics;

class Pi
{
static void Main(string[] args)
{
Pi pi = new Pi();
pi.run(args);
}
private const int LONG_TIME = 4000;
sbyte[] p;
sbyte[] t;
int q;

void run(string[] args)
{
Stopwatch timer = new Stopwatch();
int i;

if (args.Length == 1)
{
q = int.Parse(args[0]);
}
else
{
Console.WriteLine("Usage: pi [precision]");
return;
}

if (q < 0)
{
Console.WriteLine("Precision was too low, running with precision of 0.");
q = 0;
}

if (q > LONG_TIME)
{
Console.WriteLine("Be prepared to wait a while...");
}

// Compute one more digit than we display to compensate for rounding
q++;

p = new sbyte[q + 1];
t = new sbyte[q + 1];
/* compute pi */

timer.Start();
arctan(2);
arctan(3);
mul4();
timer.Stop();

q--;

/* print pi */

Console.Write("pi = {0}.", p[0]);
for (i = 1; i <= q; i++)
Console.Write(p[i]);
Console.WriteLine();
Console.WriteLine("{0} seconds to compute pi with a precision of {1} digits.", timer.ElapsedMilliseconds / 1000.0, q);

return;
}

void arctan(int s)
{
int n;

t[0] = 1;
div(s); /* t[] = 1/s */
n = 1;
do
{
mul(n);
div(s * s);
div(n += 2);
if (((n - 1) / 2) % 2 == 0)
else
sub();
} while (!tiszero());
}

{
int j;

for (j = q; j >= 0; j--)
{
if (t[j] + p[j] > 9)
{
p[j] += (sbyte)(t[j] - 10);
p[j - 1] += 1;
}
else
p[j] += t[j];
}
}

void sub()
{
int j;

for (j = q; j >= 0; j--)
if (p[j] < t[j])
{
p[j] -= (sbyte)(t[j] - 10);
p[j - 1] -= 1;
}
else
p[j] -= t[j];
}

void mul(int multiplier)
{
int b;
int i;
int carry = 0, digit = 0;

for (i = q; i >= 0; i--)
{
b = (t[i] * multiplier + carry);
digit = b % 10;
carry = b / 10;
t[i] = (sbyte)digit;
}
}

/* t[] /= l */

void div(int divisor)
{
int i, b;
int quotient, remainder = 0;

for (i = 0; i <= q; i++)
{
b = (10 * remainder + t[i]);
quotient = b / divisor;
remainder = b % divisor;
t[i] = (sbyte)quotient;
}
}

void div4()
{
int i, c, d = 0;

for (i = 0; i <= q; i++)
{
c = (10 * d + p[i]) / 4;
d = (10 * d + p[i]) % 4;
p[i] = (sbyte)c;
}
}

void mul4()
{
int i, c, d;

d = c = 0;

for (i = q; i >= 0; i--)
{
d = (p[i] * 4 + c) % 10;
c = (p[i] * 4 + c) / 10;
p[i] = (sbyte)d;
}
}

bool tiszero()
{
int k;

for (k = 0; k <= q; k++)
if (t[k] != 0)
return false;
return true;
}

}

I used the release builds for the benchmark, here are the results: d : 26 seconds to compute pi with a precision of 10000 digits. c# : 34,745(34.745) seconds to compute pi with a precision of 10000 digits. c++ : 15 seconds to compute pi with a precision of 10000 digits. I do not want to start a language war... we had enough such wars in the past days and I have just made this benchmark because I saw the “What do you think of the D language?“ thread and was testing d. I'm just surprised a little: I thought that D shouldn't be much slower than c++ and I thought that c# would be much faster. Maybe there is some optimization option I have not used(?) What do you think about the results? (maybe some one can test java) (I really like the invariant and unittest features of D, are there equivalents for c#?) -I can't reply until tomorrow- [Edited by - Kambiz on October 7, 2006 2:02:45 AM]

Share on other sites
34,745 seconds! You realy ran the program for 9 hours?

Share on other sites
The comma is the new dot. (At least in germany.)

Share on other sites
In most/all of Europe, actually. So, 3.14159 would be 3,14159. You really should know that, since chances are it will bite you one time (as you saw, it made a vast difference here).

What compiler where you using for C++ and what optimizations did you enable?

Share on other sites
One of traditions in the computer technology was use of "." for 0.030. The "," was used for something else.

"," was used traditionally only in math classes. However teachers would survive "." instead if they weren't completely retarded.

BTW if you'd like to test Java, should it be a direct port, or should it use BigDecimal instead? You might like to add an 64 bit ASM program as well.

Share on other sites
Alright, managed code haters -- don't feel too vindicated yet. I sat down with the C# code for about 15 minutes, and made some modifications to the mul and div functions.
using System;using System.Diagnostics;class Pi{	static void Main( string[] args )	{		Pi pi = new Pi();		pi.run( args );	}	private const int LONG_TIME = 4000;	sbyte[] p;	sbyte[] t;	int q;	void run( string[] args )	{		Stopwatch timer = new Stopwatch();		int i;		if( args.Length == 1 )		{			q = int.Parse( args[0] );		}		else		{			Console.WriteLine( "Usage: pi [precision]" );			return;		}		if( q < 0 )		{			Console.WriteLine( "Precision was too low, running with precision of 0." );			q = 0;		}		if( q > LONG_TIME )		{			Console.WriteLine( "Be prepared to wait a while..." );		}		// Compute one more digit than we display to compensate for rounding		q++;		p = new sbyte[q + 1];		t = new sbyte[q + 1];		/* compute pi */		timer.Start();		arctan( 2 );		arctan( 3 );		mul4();		timer.Stop();		// Return to the number of digits we want to display		q--;		/* print pi */		Console.Write( "pi = {0}.", p[0] );		for( i = 1; i <= q; i++ )			Console.Write( p[i] );		Console.WriteLine();		Console.WriteLine( "{0} seconds to compute pi with a precision of {1} digits.", timer.ElapsedMilliseconds / 1000.0, q );		return;	}	void arctan( int s )	{		int n;		t[0] = 1;		div( s ); /* t[] = 1/s */		add();		n = 1;		do		{			mul( n );			div( s * s );			div( n += 2 );			if( ( ( n - 1 ) / 2 ) % 2 == 0 )				add();			else				sub();		} while( !tiszero() );	}	void add()	{		int j;		for( j = q; j >= 0; j-- )		{			if( t[j] + p[j] > 9 )			{				p[j] += (sbyte) ( t[j] - 10 );				p[j - 1] += 1;			}			else				p[j] += t[j];		}	}	void sub()	{		int j;		for( j = q; j >= 0; j-- )			if( p[j] < t[j] )			{				p[j] -= (sbyte) ( t[j] - 10 );				p[j - 1] -= 1;			}			else				p[j] -= t[j];	}	void mul( int multiplier )	{		int b;		int i;		int carry = 0, digit;		for( i = q; i >= 0; i-- )		{			b = ( t[i] * multiplier + carry );			carry = (int) ( b * 0.1f );			digit = b - 10 * carry;			t[i] = (sbyte) digit;		}	}	/* t[] /= l */	void div( int divisor )	{		int i, b;		int quotient, remainder = 0;		float fdiv = 1.0f / divisor;		for( i = 0; i <= q; i++ )		{			b = ( 10 * remainder + t[i] );			quotient = (int) ( b * fdiv );			remainder = b - divisor * quotient;			t[i] = (sbyte) quotient;		}	}	void div4()	{		int i, c, d = 0;		for( i = 0; i <= q; i++ )		{			c = ( 10 * d + p[i] ) / 4;			d = ( 10 * d + p[i] ) % 4;			p[i] = (sbyte) c;		}	}	void mul4()	{		int i, c, d;		d = c = 0;		for( i = q; i >= 0; i-- )		{			d = ( p[i] * 4 + c ) % 10;			c = ( p[i] * 4 + c ) / 10;			p[i] = (sbyte) d;		}	}	bool tiszero()	{		int k;		for( k = 0; k <= q; k++ )			if( t[k] != 0 )				return false;		return true;	}}

Initial figures on my system before modification were in the vicinity of about 19s (probably closer to 20) for the C++ and 38s for the C#. This version of the C# runs in just under 22s. I brought the same optimizations back to the C++ version, but they didn't appear to have any particular effect.

Perhaps someone can step up and defend D's honor. 26s is much worse than I expected. (Although the fact that the D code was written by Digital Mars does not bode well.)

[Edited by - Promit on October 6, 2006 9:28:51 PM]

Share on other sites
The fastest way to calculate PI in C is of course:

#define _ -F<00||--F-OO--;int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO(){            _-_-_-_       _-_-_-_-_-_-_-_-_    _-_-_-_-_-_-_-_-_-_-_-_  _-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_ _-_-_-_-_-_-_-_-_-_-_-_-_-_-_  _-_-_-_-_-_-_-_-_-_-_-_-_-_    _-_-_-_-_-_-_-_-_-_-_-_        _-_-_-_-_-_-_-_            _-_-_-_}

Share on other sites
Quote:
 Original post by TrueTomThe comma is the new dot. (At least in germany.)

yes... (I have a German Windows.)

Quote:
 Original post by PromitAlright, managed code haters -- don't feel too vindicated yet. I sat down with the C# code for about 15 minutes, and made some modifications to the mul and div functions....

19.443 seconds to compute pi with a precision of 10000 digits.
But because of the modifications we should not compare these result with the others.

Quote:
 Original post by EzbezWhat compiler where you using for C++ and what optimizations did you enable?

MSVC++ 2005
/O2 /Ot /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Fo"Release\\" /Fd"Release\vc80.pdb" /W3 /nologo /c /Wp64 /Zi /TP /errorReport:prompt
/OUT:"D:\kambiz\c++\pi\Release\pi.exe" /INCREMENTAL:NO /NOLOGO /MANIFEST /MANIFESTFILE:"Release\pi.exe.intermediate.manifest" /DEBUG /PDB:"d:\kambiz\c++\pi\Release\pi.pdb" /SUBSYSTEM:CONSOLE /OPT:REF /OPT:ICF /LTCG /MACHINE:X86 /ERRORREPORT:PROMPT kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib

Share on other sites
Quote:
 Original post by KambizBut because of the modifications we should not compare these result with the others.

Under which conditions may we compare one result with another?

Share on other sites
Quote:
Original post by ToohrVyk
Quote:
 Original post by KambizBut because of the modifications we should not compare these result with the others.

Under which conditions may we compare one result with another?
Presumably, one is only allowed to use the exact implementation originally written in C, without taking into account the fact that a good C implementation may be a terrible implementation for another language.

In short, when comparing the performance of languages, one must assume that all programmers are competent at no languages other than C.

Share on other sites
Quote:
 Original post by PromitPresumably, one is only allowed to use the exact implementation originally written in C, without taking into account the fact that a good C implementation may be a terrible implementation for another language.

You seem to be right. I've only just noticed that the version advertised as C++ isn't C++, but is in fact C.

Share on other sites
Quote:
 Original post by KambizI'm just surprised a little: I thought that D shouldn't be much slower than c++ and I thought that c# would be much faster. Maybe there is some optimization option I have not used(?)What do you think about the results?
Interesting, but you're comparing the Microsoft C++ optimizer with the Digital Mars C++ optimizer. DMD, the Digital Mars D compiler, is built using the Digital Mars C++ optimizer.

To compare apples-apples, it makes sense to compare DMD versus DMC++, or GDC versus g++, as then the optimizer and code generator would be the same for each language. I tried DMD and DMC++, and got essentially the same times for each.

Share on other sites
I actually have a suspicion that some of the modifications I applied in the C# version will improve the D version's performance as well. Anyone want to try my edits on D and see what happens? I really don't feel like downloading DMD.

Share on other sites
Quote:
 Original post by Kambizd : 26 seconds to compute pi with a precision of 10000 digits.c# : 34,745(34.745) seconds to compute pi with a precision of 10000 digits.c++ : 15 seconds to compute pi with a precision of 10000 digits....I do not want to start a language war...

Yeah, right. The fact that you only gave a decimal point only for the C# version (using a comma to represent it, making it look like a huge number) and your dismissal of Promit's benchmark implies that you hold a certain prejudice toward C#. Now, theres nothing inherently wrong with that but trying to spread propaganda in the form of a benchmark is pretty sad if you ask me.

Share on other sites
I'll make it fair barakus.

d : 26 seconds to compute pi with a precision of 10000 digits.
c# : 35 seconds to compute pi with a precision of 10000 digits.
c++ : 15 seconds to compute pi with a precision of 10000 digits.

As for propaganda, I see none - just the results of a benchmark.

Share on other sites
i don't want to comment on the benchmark a lot. quite frankly these kind of performance benchmarks don't mean so much, but yes they can be interesting in some cases. a pure number crunching benchmark should be winnable by a native language like c++, no surprise there. a realistic number cruncher would resort to simd instructions anyways which (for now) leaves all other alternatives far behind.. but that's only a matter of time (for me that is the main reason not to use managed languages for these kinds of applications. i need the simd capabilities the metal offers).
i like the fact, though, that people are starting to defend c# like most of us here do with c++ and the sc++l. that kind of advocacy for a certain language is a very good sign for the language (and - admit it! - its creators). i think that on its own is a good process.

cheers,
simon

Share on other sites
Quote:
 Original post by barakusYeah, right. The fact that you only gave a decimal point only for the C# version (using a comma to represent it, making it look like a huge number) [...] implies that you hold a certain prejudice toward C#.
I think you're reading too much to that. In Europe (where he's from), believe it or not, people use comma to separate decimals (mind-boggling, I know!). And that only C# version had decimals is likely due to the fact that in C# he had to write the outputting code slightly differently. The C-version's timing and output is more of a direct port from the original D code (using the same printf statement).
Quote:
I think this was fair. It's not like Promit's code is more idiomatic C#, it's just a tweak that happens to make .NET run faster. Similar tweaks could probably be found in C++ and D versions as well, and we could spend weeks optimizing each one. Why not actually compare versions that are near identical in code to save the trouble? It even looks to me like his code would make the algorithm wrong due to the fact that floating point math isn't as accurate, but I didn't check this..

Share on other sites
I've deleted the AP replies that seem intent on derailing this thread. So far the discussion is clean and interesting - whilst these benchmarks may not be the best way to compare languages they are a good platform for learning and discussing various characteristics.

The whole "," or "." thing is a bit pointless - why bother arguing over something so silly [smile]

Cheers,
Jack

Share on other sites
I'm not much of a .net freak but to me it seems like .net is going to be slower no matter what in this specific case. It's basically a series of tight loops with bounds checked array accesses which will generate at least an extra branch for each array access, probably with stack unwinding also.

I see nothing wrong with the test and it demonstrates what is a fairly well known weakness of .net, tight loops and a lot of array accesses.

Share on other sites
Quote:
 Original post by Anonymous PosterIt's not like Promit's code is more idiomatic C#, it's just a tweak that happens to make .NET run faster. Similar tweaks could probably be found in C++ and D versions as well, and we could spend weeks optimizing each one. Why not actually compare versions that are near identical in code to save the trouble? It even looks to me like his code would make the algorithm wrong due to the fact that floating point math isn't as accurate, but I didn't check this..

Different languages work in different ways. It is extremely biased to write a program in one language (C++) and expect a direct port to run equally fast on other languages (D or C#, in this case). Spending "weeks" (hopefully less) on optimizing each language according to their strengths would provide the best benchmarks. After all, I could care less how well C# or D implements C-specific algorithms. What I care about is the performance I'll achieve using those languages in the way they're designed.

- Mike

Share on other sites
Looks like DMD is missing some optimization oportunities in the div and mul functions. I tried using a similar modification to what Promit had posted:

import std.c.stdio;import std.c.stdlib;import std.c.time;const int LONG_TIME=4000;byte[] p;byte[] t;int q;int main(char[][] args){	int startime, endtime;	int i;	if (args.length == 2) {		sscanf(&args[1][0],"%d",&q);	} else {		printf("Usage: pi [precision]\n");		exit(55);	}	if (q < 0)	{		printf("Precision was too low, running with precision of 0.\n");		q = 0;	}	if (q > LONG_TIME)	{	    printf("Be prepared to wait a while...\n");	}	// Compute one more digit than we display to compensate for rounding	q++;	p.length = q + 1;	t.length = q + 1;	/* compute pi */	std.c.time.time(&startime);	arctan(2);	arctan(3);	mul4();	std.c.time.time(&endtime);	// Return to the number of digits we want to display	q--;	/* print pi */	printf("pi = %d.",cast(int)(p[0]));	for (i = 1; i <= q; i++)	printf("%d",cast(int)(p[i]));	printf("\n");	printf("%ld seconds to compute pi with a precision of %d digits.\n",endtime-startime,q);	return 0;}void arctan(int s){	int n;	t[0] = 1;	div(s); /* t[] = 1/s */	add();	n = 1;	do {		mul(n);		div(s * s);		div(n += 2);		if (((n-1) / 2) % 2 == 0)			add();		else			sub();	} while (!tiszero());}void add(){	int j;	for (j = q; j >= 0; j--)	{		if (t[j] + p[j] > 9) {			p[j] += t[j] - 10;			p[j-1] += 1;		} else			p[j] += t[j];	}}void sub(){	int j;	for (j = q; j >= 0; j--)		if (p[j] < t[j]) {			p[j] -= t[j] - 10;			p[j-1] -= 1;		} else			p[j] -= t[j];}void mul(int multiplier){	int b;	int i;	int carry = 0, digit = 0;	for (i = q; i >= 0; i--) {		b = (t[i] * multiplier + carry);		carry = b / 10;		digit = b - carry * 10;		t[i] = digit;	}}/* t[] /= l */void div(int divisor){	int i, b;	int quotient, remainder = 0;	for (i = 0; i <= q; i++) {		b = (10 * remainder + t[i]);		quotient = b / divisor;		remainder = b - divisor * quotient;		t[i] = quotient;	}}void div4(){	int i, c, d = 0;	for (i = 0; i <= q; i++) {		c = (10 * d + p[i]) / 4;		d = (10 * d + p[i]) % 4;		p[i] = c;	}}void mul4(){	int i, c, d;	d = c = 0;	for (i = q; i >= 0; i--) {		d = (p[i] * 4 + c) % 10;		c = (p[i] * 4 + c) / 10;		p[i] = d;	}}int tiszero(){	int k;	for (k = 0; k <= q; k++)		if (t[k] != 0)			return false;	return true;}

Then I tested the original and modified program on two systems, on linux machine from my univ and my laptop running windows. Here are my results:

Linux 2.6.17-1.2142_FC4smp

Digital Mars D Compiler v0.168
dmd, no modifications: 50 seconds
dmd, modifications: 33 seconds
dmd flags: -release -inline -O

g++ (GCC) 4.0.2 20051125 (Red Hat 4.0.2-8)
g++, no modifications: 29 seconds
g++, modifications: 32 seconds
g++ flags: -O3

Windows XP SP2 Pro

Digital Mars D Compiler v0.168
dmd, no modifications: 20 seconds
dmd, modifications: 15 seconds
dmd flags: -release -inline -O

g++ (GCC) 3.4.2 (mingw-special)
g++, no modifications: 12 seconds
g++, modifications: 14 seconds
g++ flags: -O3

gdc (GCC) 3.4.2 (mingw-special) (gdc 0.19, using dmd 0.162)
gdc, no modifications: 12 seconds
gdc, modifications: 14 seconds
gdc flags: -frelease -finline -O3

I ran each test twice and took the better result. I used a windows build of the GCC D Compiler available from the following page: http://gdcwin.sourceforge.net/

Share on other sites
Quote:
 Original post by Anonymous PosterI think this was fair. It's not like Promit's code is more idiomatic C#, it's just a tweak that happens to make .NET run faster. Similar tweaks could probably be found in C++ and D versions as well, and we could spend weeks optimizing each one. Why not actually compare versions that are near identical in code to save the trouble? It even looks to me like his code would make the algorithm wrong due to the fact that floating point math isn't as accurate, but I didn't check this..

Comparing identical versions is pointless unless you're comparing different compilers of the same langage. In other words, its only fair if you're comparing VC++ to g++. When comparing different languages, you have to make changes for each langage in order to keep the test fair...a tightly optimized program for language X may well run like shit in language Y. You should keep the algorithm the same, and that's it.

CM

Share on other sites
Quote:
 Original post by doctorsixstringDifferent languages work in different ways.
It's more of a comparison of compilers than languages here. As you can see, the codes are near identical. What we could conclude from Promit's tests is that the C++ compiler relieves the writer of the code from micro-optimizations more than the .NET compiler does. He did the same fix for C++ and the speed was unaffected. So when writing code casually for C++ without regard to micro-optimizations, you'd get 34/15 times faster code than with the .NET compiler. With .NET you'd have to spend extra effort doing the compiler's job to get down to 22/20. I think this already tells us something useful.
Quote:
 What I care about is the performance I'll achieve using those languages in the way they're designed.
Can you claim with a straight face that Promit's opitimization is how you would've written the code in the first place with C#, and you would've used the modulo operator on C++ instead? It's not like C# was "designed" to perform worse with the integer modulo/div combo than C++. It's just a quirk.

Share on other sites
Quote:
 Original post by Conner McCloudComparing identical versions is pointless unless you're comparing different compilers of the same langage. In other words, its only fair if you're comparing VC++ to g++. When comparing different languages, you have to make changes for each langage in order to keep the test fair...a tightly optimized program for language X may well run like shit in language Y.
Even if we were comparing different compilers of the same language, one could use the same reasoning you do. One would want to optimize one's code for the particular compiler's quirks, no? And code tightly optimized for compiler X could run like shit when compiled with compiler Y.

For a code like this all three are essentially identical. None of them provide some super speed constructs that lack from the other languages that should be exploited for this code. Promit's changes still work for D and C++ directly. The original D code worked for C++ and C# (essentially) directly. I know there are tons of actual cases where language differences matter for speed, only this is not one of them. Promit's change was only to make the compiler happy, not to make the code "better C#".

Share on other sites
Quote:
 Original post by Anonymous PosterIt's more of a comparison of compilers than languages here.

Comparing a C# compiler to a C or C++ compiler to a D compiler is a bit like comparing apples to oranges, don't you think?

Quote:
 Original post by Anonymous PosterAs you can see, the codes are near identical.

As I mentioned earlier, I think this is the wrong way to run a benchmark. What if the original example is written in a non-C language, and then ported to C in a way that is beneficial to the original language? Obviously that would be unfair.

Quote:
 Original post by Anonymous PosterWhat we could conclude from Promit's tests is that the C++ compiler relieves the writer of the code from micro-optimizations more than the .NET compiler does. He did the same fix for C++ and the speed was unaffected. So when writing code casually for C++ without regard to micro-optimizations, you'd get 34/15 times faster code than with the .NET compiler. With .NET you'd have to spend extra effort doing the compiler's job to get down to 22/20. I think this already tells us something useful.

I agree that C++ has the edge over C# in this case. It is interesting that C#'s modulus operator is so much slower that C++. What version of .NET was used for the tests? Has anyone compared it to non-MS implementations like Mono?

Quote:
 Original post by Anonymous PosterCan you claim with a straight face that Promit's opitimization is how you would've written the code in the first place with C#, and you would've used the modulo operator on C++ instead?

No, I honestly would never have thought to use Promit's code instead of the modulus.

Quote:
 Original post by Anonymous PosterIt's not like C# was "designed" to perform worse with the integer modulo/div combo than C++. It's just a quirk.

I agree. It would be interesting to see if this quirk is common across all versions and implementations of .NET.

- Mike

Create an account

Register a new account

• Forum Statistics

• Total Topics
628301
• Total Posts
2981906
• Similar Content

• Hey there! My name is Cpaws and I compose music, sound effects and overall sound design for video games and film. I'm looking to work on a horror game mainly for fun and as an addition to my portfolio. I've used Unity & Wwise before for audio implementation.
If you're interested in working together, don't hesitate to contact me at cpawsmusic@gmail.com
Here's a few demo reels of my past projects:
Here's some snippets of some quick game music I've composed: https://soundcloud.com/cpawsmusic/sets/cpaws-video-game-film-music
Here's my portfolio/website: https://CpawsMusic.com/
E-mail: cpawsmusic@gmail.com

• My first mobile game made by unity

iphone: https://itunes.apple.com/us/app/aa-countdown/id1314223584?ls=1&mt=8

I appreciate every suggestion
• By Simplepg
• By Simplepg

• Who We Are
We are Forged Interactive, a small team of like-minded game developers with the sole purpose of making games we love! We're a team of artists, animators, programmers, level designers, writers, composers, producers, and other creative minds. We want to make games that you, the modern gamer want to play! We hope to build a community that enjoys our games as much as we love creating them. With your feedback and support we will be able to achieve that.

GAME NAME is a fun, action-packed army builder with unique characters, challenges and engaging levels. Set forth on an adventure to protect friends, family and countrymen from new adversaries. Once defeated your enemies turn coat and join you in your adventures. Players can enjoy a range of troops and abilities based on their gameplay style which become more important as maps introduce more challenging terrain, enemies and bosses. Strong orc knights, dangerous shamans, and even a dragon are out on the prowl. Knowing when to fight and when to run, and how to manage your army is essential. Your actions alone decide the fate of this world.

Previous Work by Team
Although we are working towards our first game as a team, our team members themselves have past experience in the industry.
This includes members who have worked on titles including:
Final Fantasy Kingsglaive, FIFA, Xcom 2 and Civilization.

Who are we looking for? 3D Modellers Concept Artists Marketing Specialists Level Designer

What do we expect? Reference work or portfolio. Examples what have you already done and what projects you have worked on academic or otherwise. The ability to commit to the project on a regular basis. If you are going on a two-week trip, we don't mind, but it would be good if you could commit 10+ hours to the project each week. Willingness to work with a royalty based compensation model, you will be paid when the game launches. Openness to learning new tools and techniques
What can we offer? Continuous support and availability from our side. You have the ability to give design input, and creative say in the development of the game. Shown in credits on websites, in-game and more. Insight and contacts from within the Industry.
Contact
If you are interested in knowing more or joining. Please email or PM us on Skype. Myself or Colin will reply to you within 48 hours.

E-mail: Recruitment@ForgedInteractive.com
Skype: ForgedInteractive

Regards,
David and Colin


text:
# Range of value to satisfy sufficient and necessary condition

1. Nov 1, 2015

### songoku

1. The problem statement, all variables and given/known data
Let
p: x and y satisfy inequality x2 + y2 + 4x - 8y + c < 0 where c is real number
q: x and y satisfy x - y + 8 > 0 ; 4x + 3y - 24 < 0 ; y < 0

Find the range of c so that:
a. p is sufficient condition for q
b. p is necessary condition for q

2. Relevant equations
Circle
Inequality

3. The attempt at a solution
p is the region inside circle (excluding circumference), centered at (-2, 4) and has radius of √(20 - c)

q is the infinite region bounded by two lines and x - axis

I want to ask whether my opinion is correct:
a. For p to be sufficient condition for q, region q should be located inside the circle
b. For p to be necessary condition for q, the circle should be inside the region of q

Thanks

2. Nov 1, 2015

### andrewkirk

I think it's the other way around.
'p is sufficient for q' means $p\Rightarrow q$ which should mean that $p\subseteq q$.

3. Nov 1, 2015

### HallsofIvy

Staff Emeritus
'p' is the interior of a circle with radius depending on c, 'q' is the region between two intersecting lines and below the y-axis . 'if p then q' (p is a sufficient condition for q) says that if (x,y) is in the circle it must be in the region between the lines- the circle must be a subset of the region. 'if q then p' (p is a necessary condition for q) says that if (x, y) is in the region it must be a in the circle- the region is a subset of the circle. But since the region between the line extends infinitely, that does not see, possible for any 'c'. If the last condition were "y> 0", then it would be a bounded triangular region.

4. Nov 1, 2015

### songoku

I get it.

Thanks a lot for all the help


text:
# spark-reviews mailing list archives

##### Site index · List index
Message view
Top
From srowen <...@git.apache.org>
Subject [GitHub] spark pull request #20396: [SPARK-23217][ML] Add cosine distance measure to ...
Date Fri, 26 Jan 2018 13:40:52 GMT
Github user srowen commented on a diff in the pull request:

https://github.com/apache/spark/pull/20396#discussion_r164111780

--- Diff: mllib/src/main/scala/org/apache/spark/ml/evaluation/ClusteringEvaluator.scala
---
@@ -421,13 +460,220 @@ private[evaluation] object SquaredEuclideanSilhouette {
computeSilhouetteCoefficient(bClustersStatsMap, _: Vector, _: Double, _: Double)
}

-    val silhouetteScore = dfWithSquaredNorm
-      .select(avg(
-        computeSilhouetteCoefficientUDF(
-          col(featuresCol), col(predictionCol).cast(DoubleType), col("squaredNorm"))
-      ))
-      .collect()(0)
-      .getDouble(0)
+    val silhouetteScore = overallScore(dfWithSquaredNorm,
+      computeSilhouetteCoefficientUDF(col(featuresCol), col(predictionCol).cast(DoubleType),
+        col("squaredNorm")))
+
+    bClustersStatsMap.destroy()
+
+    silhouetteScore
+  }
+}
+
+
+/**
+ * The algorithm which is implemented in this object, instead, is an efficient and parallel
+ * implementation of the Silhouette using the cosine distance measure. The cosine distance
+ * measure is defined as 1 - s where s is the cosine similarity between two points.
+ *
+ * The total distance of the point X to the points $C_{i}$ belonging to the cluster
$\Gamma$
+ * is:
+ *
+ *

+ *   $$+ * \sum\limits_{i=1}^N d(X, C_{i} ) = + * \sum\limits_{i=1}^N \Big( 1 - \frac{\sum\limits_{j=1}^D x_{j}c_{ij} }{ \|X\|\|C_{i}\|} \Big) + * = \sum\limits_{i=1}^N 1 - \sum\limits_{i=1}^N \sum\limits_{j=1}^D \frac{x_{j}}{\|X\|} + * \frac{c_{ij}}{\|C_{i}\|} + * = N - \sum\limits_{j=1}^D \frac{x_{j}}{\|X\|} \Big( \sum\limits_{i=1}^N + * \frac{c_{ij}}{\|C_{i}\|} \Big) + *$$
+ *

+ *
+ * where $x_{j}$ is the j-th dimension of the point X and $c_{ij}$ is the j-th
dimension
+ * of the i-th point in cluster $\Gamma$.
+ *
+ * Then, we can define the vector:
+ *
+ *

+ *   $$+ * \xi_{X} : \xi_{X i} = \frac{x_{i}}{\|X\|}, i = 1, ..., D + *$$
+ *

+ *
+ * which can be precomputed for each point and the vector
+ *
+ *

+ *   $$+ * \Omega_{\Gamma} : \Omega_{\Gamma i} = \sum\limits_{j=1}^N \xi_{C_{j}i}, i = 1, ..., D + *$$
+ *

+ *
+ * which can be precomputed too for each cluster $\Gamma$ by its points $C_{i}$.
+ *
+ * With these definitions, the numerator becomes:
+ *
+ *

+ *   $$+ * N - \sum\limits_{j=1}^D \xi_{X j} \Omega_{\Gamma j} + *$$
+ *

+ *
+ * Thus the average distance of a point X to the points of the cluster $\Gamma$ is:
+ *
+ *

+ *   $$+ * 1 - \frac{\sum\limits_{j=1}^D \xi_{X j} \Omega_{\Gamma j}}{N} + *$$
+ *

+ *
+ * In the implementation, the precomputed values for the clusters are distributed among
the worker
+ * nodes via broadcasted variables, because we can assume that the clusters are limited
in number.
+ *
+ * The main strengths of this algorithm are the low computational complexity and the
intrinsic
+ * parallelism. The precomputed information for each point and for each cluster can be
computed
+ * with a computational complexity which is O(N/W), where N is the number of points
in the
+ * dataset and W is the number of worker nodes. After that, every point can be analyzed
+ * independently from the others.
+ *
+ * For every point we need to compute the average distance to all the clusters. Since
the formula
+ * above requires O(D) operations, this phase has a computational complexity which
is
+ * O(C*D*N/W) where C is the number of clusters (which we assume quite low), D
is the number
+ * of dimensions, N is the number of points in the dataset and W is the number of
worker
+ * nodes.
+ */
+private[evaluation] object CosineSilhouette extends Silhouette {
+
+  private[this] var kryoRegistrationPerformed: Boolean = false
+
+  private[this] val normalizedFeaturesColName = "normalizedFeatures"
+
+  /**
+   * This method registers the class
+   * [[org.apache.spark.ml.evaluation.CosineSilhouette.ClusterStats]]
+   * for kryo serialization.
+   *
+   * @param sc SparkContext to be used
+   */
+  def registerKryoClasses(sc: SparkContext): Unit = {
+    if (!kryoRegistrationPerformed) {
+      sc.getConf.registerKryoClasses(
+        Array(
+          classOf[CosineSilhouette.ClusterStats]
+        )
+      )
+      kryoRegistrationPerformed = true
+    }
+  }
+
+  case class ClusterStats(normalizedFeatureSum: Vector, numOfPoints: Long)
+
+  /**
+   * The method takes the input dataset and computes the aggregated values
+   * about a cluster which are needed by the algorithm.
+   *
+   * @param df The DataFrame which contains the input data
+   * @param predictionCol The name of the column which contains the predicted cluster
id
+   *                      for the point.
+   * @return A [[scala.collection.immutable.Map]] which associates each cluster id to
a
+   *         [[ClusterStats]] object (which contains the precomputed values N and
+   *         $\Omega_{\Gamma}$).
+   */
+  def computeClusterStats(df: DataFrame, predictionCol: String): Map[Double, ClusterStats]
= {
+    val numFeatures = df.select(col(normalizedFeaturesColName)).first().getAs[Vector](0).size
+    val clustersStatsRDD = df.select(
+      col(predictionCol).cast(DoubleType), col(normalizedFeaturesColName))
+      .rdd
+      .map { row => (row.getDouble(0), row.getAs[Vector](1)) }
--- End diff --

I'm neutral on it. I don't think importing implicits is a big deal either way.

---

---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org

Mime
View raw message


text:
# 92 questions

Tagged
• x
18
views
1
vote
1

## Where is the latest User Guide for Gazell?

Hi,

the documentation page of Gazell warns that it is outdated.

Warning: This is old documentation, and should only be used for historic reference. Please go here to find the latest.

documentation page

But where do I find the latest ... (more)

21
views
no
no

Hi ,all

I have a problem in my project .I want to use gzp preload ack feature .When the host receives datas ,I would use this function "void gzp_preload_ack(uint8_t* src, uint8_t length, uint8_t pipe)" to send datas to the ... (more)

30
views
no
1

## Error in Gazell diagram? [closed]

I am not sure whether there is a small error in a Gazell packet transaction diagram, or if I have an incorrect understanding. From Gazell user guide:

If only the ACK packet sent from the Host to the Device is ...

(more)

70
views
1
vote
1

## looking for example Gazell project on Nrf52840

I am looking at using two Nrf52840 on Custom PCBs to create a wireless link from my product to a PC one 840 would be the host and would be wired to the PC using USB (HID,MSC,CDC) and ... (more)

34
views
no
1

## [GZP] Two gazelle "slaves" pairing with each other

Hello,

I have two identical devices with Laird's BL600 chip (that uses NRF51822). They are initialized as NRF_GZLL_MODE_DEVICE and use GZP library (without encryption - only pipe no 2 is used). They are cyclically calling gzp_address_req_send() function until the positive ... (more)

48
views
no
1

## Using Gazell on third party chipset

Hello,

I want to create BLE connection between two different modules - nrf51822 and TI CC2564 (possibly Laird BT800). Is there any chance on using Gazell protocol on other devices than Nordic?

96
views
3
1

## Gazell nRF51822

Does the s210 softdevice not function on the nRF51822? I see it available for the nRF51422 here but it is listed under the 51422 only.

I have a v1.1.0 PCA10031 (nrf51422) and have written an LED blink example ... (more)

78
views
no
1

## gazell out_of_sync and in_sync [closed]

hi ,all

I feel confused about" out_of_sync" and" in_sync" parameters .If a devece is in sync,how the channels was changed ?And what's the use of"nrf_gzll_set_device_channel_selection_policy())"? And how could I get the sync_lifetime in our softcode ?

82
views
no
1

## Gazell data lag when more than 1 device is connected

Hi! I am fairly new to programming micro controllers so apologies if I ask many questions. I am using NRF52832. The situation is this - I have 2 devices and 1 host . After receiving data the host then sends data via ... (more)

49
views
no
no

## BLE hid keyboard and Gazell at the same time [closed]

Hi there,

My scenario is the split keyboard which has 2 parts: left-hand part and right-hand part. Each part has a NRF52832. I am willing to implement the left-hand part to be a BLE hid keyboard and also connect right-hand ... (more)

42
views
no
1

## gazell in more devices application [closed]

hi all:

I am a new user.Now i have a project in which I need to implement a function a host and four devices .I just want to know if i use the example of " gzp_dynamic_pairing " what do i ... (more)

23
views
no
no

## Are the pairing information of gzp stored in the flash?

So the question would be if I would need to pair each time the device comes out of reset or are there information stored to return to direct communication without pairing if pairing has been executed once?

And what happens ... (more)

196
views
1
vote
3

## Frequency hopping with S132 v3

Hello! I'd like to know if S132 v3 implements the frequency hopping scheme defined by BLE.

I've read some documentation on Gazell, but from what I understood, that is a completely different protocol, not a superset of BLE ... (more)

63
views
1
vote
1

## Gazell example with PCA10028 does not load - does it need softdevice?

I am confused about the lack of softdevice information for the Gazell examples. I am looking at SDK 10 now having first tried SDK12 before deciding to stay with 10.

As a starting point, I have no trouble compling, loading ... (more)

60
views
no
1

## GZP (Gazell Pairing Library) causes application to reset into Bootloader

Hello there, thanks so much for taking the time to read. My problem is the following

I am trying to run GZP (Gazell Pairing Library). After successfully pairing with a Gazell Host, if I power cycle my Gazelle device (NRF52 ... (more)

100
views
no
2

## Gazell host with multiple devices

I'm new to Gazell, so please excuse the simplicity of my question, but I just seem to be missing something.

I have an application where I will be using one host with two devices. When the host receives a ... (more)

132
views
no
1

## How to improve the communication distance with Gazell?

My gazell configuration is as follows:

#define PIPE_NUM                    0
#define TIMESLOT_PERIOD             2000
#define TIMESLOT_PER_CHANNEL        2
#define CHANNEL_TABLE_SIZE          1
#define CHANNEL_TABLE               {18}
#define SYNC_LIFETIME           (3 * CHANNEL_TABLE_SIZE * TIMESLOT_PER_CHANNEL)
#define MAX_TX_ATTEMPTS             3
#define TX_POWER            NRF_GZLL_TX_POWER_4_DBM
#define TX_DATARATE         NRF_GZLL_DATARATE_1MBIT

frames per ... (more)

39
views
no
1

## Gazell how to update channel table using num_channel_switches

HI, I look at nRF5 SDK doc about Gazell,see that 'the nrf_gzll_device_tx_info_t contains the num_channel_switches parameter which can be used by application to determine wheather the RF channels are reliable.'But I don't know how to achieve that ... (more)

125
views
no
1

## about nrf51 Gazell timeslot period

hi, I test the gazell example gzll_ack_payload in SDK9.0,I found that the default timeslot period is 600us.But after testing using logic analysis,I found sometime transfer interval is600us,but most time it's 1200us. What's the reason?

29
views
no
1

I'd like to add a capslock function in gazell when i am developing a keyboard based on 'nrfready_desktop_2_v3.1.0'. After i have read the source code from nordic, i cant found about how to get the RX datas ... (more)

64
views
no
no

## Gazell two device cannot suppport ,why?

I use Gazell to acomplish one host --two device.When i just have one device,everything is OK。But when added to two,it cannot work. I think,whether channel of two devices is same cause it ?? So ,for host ... (more)

212
views
no
1

## Gazell Ack not received after data transfer

I'm working on a very simple Gazell build - basically the gzll_ack_payload example with some of it pulled out, since I'm working on a board with no LEDs or buttons to run that specific build against. It's a ... (more)

109
views
no
1

## nrf51822 Bluetooth and Gazell enabled at same time

Hi Can we have both bluetooth and Gazell enabled at the same time?

We are using nrf51 series chips.

We want Gazell to communicate with with other nrf chips and Bluetooth to communicate with the phone.

Regards Ashwin

106
views
no
no

## Gazell Flywheel TIMER2_IRQHandler HardFault

Problem:

We trigger HardFaults reproducibly. By manually unwinding the stack we have traced the source of the error back to the TIMER2_IRQHandler in Gazell. We can see that the TIMER2_IRQHandler reads a callback pointer that sometimes is NULL, but no ... (more)

1k
views
1
vote
2

## Question of nRF52 + Gazell data rate?

Hi

Befor I used nRF51822 to transmit a packet per 5ms, payload length is 12. I can received 200 packets/s, Initialization settings are as follows

• Device : nRF51822 Gazell Device
• Host : nRF24Lxx Gazell Host
• Softdevice : s110_nrf51822_7.1.0
• library : gzll_arm ...
(more)

316
views
no
2

## what is the maximum range to connect 2 NRF51822 devices with Gazell

Hello,

I was looking into Gazell and read that Gazell only allows pairing when Host and Device are in close proximity to each other. This range is about 30 centimeters. I was wondering if this range could be extended? and ... (more)

326
views
1
vote
1

## Can I run BLE, ANT, and Gazell protocol in the same time on nRF52832?

I wanna plan to design a new hardware which has ability to connect to smartphones using BLE and broadcasting ANT pages in the same time. I also need a way to transmit some private data with the rate of 1 ... (more)

548
views
2
2

## Gazell, ESB and nRF52 [closed]

Hi all,

Will the Gazell protocol be available on the nRF52, or should I stick to an nRF51?

Also for a new product, is it better to use Gazell than ESB?

Thanks!

569
views
no
1

## Gazell, ANT or ..other ?

Hello we would like to use the Nordic chip to send wireless messages from a node to other nodes directly,without hubs. We wouldn't like to be limited to up to 8 nodes receiving the message. All the chain ... (more)

55
views
1
vote
1

## gazell and app_pwm conflict

Hi,

I'm using gazell library with app_pwm.

From documentation gazell use Timer2 and PPI channels 0,1,2. APP_PWM use Timer0.

When I disable pwm using app_pwm_disable(&PWM1), gazell can't send any packet, but when I enable it ... (more)

#### Statistics

• Total users: 24443
• Resolved questions: 10448
• Total questions: 25453

## Recent blog posts

• ### 6 Things to Know about Bluetooth Beacons

Posted 2017-09-22 08:27:00 by Rose Martin
• ### Creating a Keil project for a Bluetooth Mesh example

Posted 2017-09-19 12:08:11 by Kristian Skordal
• ### Using millis() like in Arduino.

Posted 2017-09-18 11:58:04 by schef
• ### Flashing nRF5x firmware using any dumb terminal program via standard serial COM port

Posted 2017-09-18 03:53:40 by Nguyen Hoan Hoang
• ### How to Debug the nRF52 Interrupts — Useful Tips

Posted 2017-09-13 15:15:22 by Yaniv Nis

## Recent questions

• ### Can I combine beacon code and HID keyboard code?

Posted 2017-09-22 23:35:41 by alikob
• ### how to enter "power down" mode in nrf52832

Posted 2017-09-22 21:21:04 by Ed
• ### BPROT Protecting Bootloader nRF52832

Posted 2017-09-22 20:53:06 by superpak
• ### Issue using NRF_DRV_TWI_XFER_DESC_TXRX TWI master driver

Posted 2017-09-22 20:45:08 by Tgage
• ### Fstorage - fs_erase causes connection failure

Posted 2017-09-22 20:27:34 by John DeWitt


text:
# What is the probability that the second player will win in this random game?

I'm working through Stanford's CS109 Problem Set 1 on Probability for Computer Scientists, and on #15 there's an extra credit question I can't explain:

1. Consider a game that uses a generator which produces independent random integers between 1 and 100 inclusive. The game starts with a sum $$S = 0$$. The first player adds random numbers from the generator to $$S$$ until $$S > 100$$ and records her last random number as $$x$$. The second player continues adding random numbers from the generator to $$S$$ until $$S > 200$$ and records her last random number as $$y$$. The player with the highest number wins, i.e. if $$y > x$$ the second player wins. Is this fair? Write a program to simulate 100,000 games. What is the probability estimate, based on your simulations, that the second player wins? Give your answer rounded to 3 places behind the decimal. For extra credit, calculate the exact probability (without sampling).

By creating a Python script to simulate 100,000 games, the probability of the second player winning hovers around $$0.532$$. Yet, I suspected it to be $$0.495$$ since each players' last number could be any number from $$1$$ to $$100$$ since $$S \leq 100$$ is met to allow them to keep generating numbers. The same goes for player two and $$S \leq 200$$. Since each number seems equally likely, I found:

$$P(y > x) = \frac{99 \cdot 100}{2} \cdot \frac{1}{100^2} = 0.495$$

But this is definitely not correct as the simulation shows. Where is the problem in my analysis? I made sure I used a uniform distribution for generating numbers in my simulation.

• What you ignored is that player 2 doesn't always start at 100. – Don Thousand May 22 at 3:43
• @DonThousand Yes, but doesn't player two still have the potential to generate any number. The worst case is if player one generates $100$ then $100$ again. Player two still has a chance to generate. – Andrew Li May 22 at 3:45
• @DonThousand I agree. But why does the starting condition for player two matter? They will always be able to generate a number no matter what. – Andrew Li May 22 at 3:52
• Lets consider the bound of 2, instead of 100. For player 1, the probability of the last number being 2 is 75% (if player 1 first picks 2, then that ends his turn, but if he picks 1, he has another chance to pick 2). For player 2, there is a 75% chance he starts at 2, and 25% at 3. For the case of player 2 starting at 2, the same calculations hold, but if he starts at 3, the probability of picking 2 last is 50%, not 75%. So, for player 2, the probability of the last number being 2 is $75\%\cdot75\%+25\%\cdot50\%=68.75\%$. – Don Thousand May 22 at 3:53
• @DonThousand Oh, that's right. I completely overlooked that. Also--the note about the last number being $2$--even if player 1 chooses a $2$ initially, they can still go again. Player 1 stops when $S > 2$ not $S \geq 2$. – Andrew Li May 22 at 3:56


text:
# Solving a recurrence equation

Hi, I'm trying to solve this recurrence equation.

1. Homework Statement
Solve $$y[k+2]+y[k]=sin(k)$$.
$$y[k]=c_1sin(\frac{\pi}{2}k) + c_2cos(\frac{\pi}{2}k) + \frac{sin(k)+sin(k-2)}{2(1+cos(2))}$$

2. Homework Equations

3. The Attempt at a Solution
First I solve the homogeneous equation.
$$y[k+2]+y[k]=0$$.
The characteristic function is
$$r^2+1=0$$
This has two complex roots $$r=i$$ and $$r=-i$$.
Thus the general solution is
$$y[k]=c_1(i)^k+c_2(-i)^k$$
If you change the notation for the complex numbers, then it gives
$$y[k]=c_1(cos(\frac{\pi}{2}k)+isin(\frac{\pi}{2}k)) + c_2(cos(\frac{-\pi}{2}k)+isin(\frac{-\pi}{2}k))$$
After grouping together it gives
$$(c_1+c_2)cos(\frac{\pi}{2}k) + (c_1-c_2)isin(\frac{\pi}{2}k)$$
Apparently, the answer is without complex numbers so I guess they only keep the real part. Then it must be so that
$$c_1-c_2=0\Leftrightarrow c_1=c_2$$
Then I get as solution
$$y[k]=2c_1cos(\frac{\pi}{2}k)$$
which is not the same solution as the general solution in the answer. What did I do wrong?

I also tried to find a particular solution for the non-homogeneous equation. I tried as a solution
$$y[k]=\alpha sin(k)$$
with $$\alpha$$ the parameter to determine. I don't this is the right solution. Can anyone help me with this problem?

Thanks,

Yoran

## Answers and Replies

Related Calculus and Beyond Homework Help News on Phys.org
They don't "only keep the real part". Plug the solution back into the homogeneous equation; the sine part falls out without imposing any constraint on c1 and c2.

Hi,

Thanks for your quick reply. I tried to do what you told me but when I plug it into the homogeneous equation, everything cancels out! I get 0=0. This is what I did:
We have that
$$y[k]=(c_1+c_2)cos(\frac{\pi}{2}k)+(c_1-c_2)isin(\frac{\pi}{2}k)$$
I plug it into
$$y[k+2]+y[k]=0$$
I get
$$(c_1+c_2)cos(\frac{\pi}{2}(k+2))+(c_1-c_2)isin(\frac{\pi}{2}(k+2))+(c_1+c_2)cos(\frac{\pi}{2}k)+(c_1-c_2)isin(\frac{\pi}{2}k)=0$$
Because
$$cos(\theta + \pi)=-cos(\theta)$$ and
$$sin(\theta + \pi)=-sin(\theta)$$
I get that
$$-(c_1+c_2)cos(\frac{\pi}{2}k)-(c_1-c_2)isin(\frac{\pi}{2}k)+(c_1+c_2)cos(\frac{\pi}{2}k)+(c_1-c_2)isin(\frac{\pi}{2}k)=0$$
which makes
$$0=0$$
How come?

Actually, you are correct. That was a silly suggestion of me, because 0=0 simply confirms your solution satisfies the equation from which you derived the solution. I will edit this post if I come up with something.

Edit: Wow I had been reading it wrong for a good 45 minutes, sorry! Consider complex coefficients and make the substitution d1=c1+c2 and d2=i(c1-c2).

Can you find the particular solution from here?

Last edited:
Hi,

Yeah of course... just give different names as they are just parameters... Thanks a lot.
I tried the substitution $$\alpha sin(k)$$ because there is $$sin(k)$$ on the right side of the equation. However, I can't find the right answer. This is what I have done:
Try
$$y[k]=\alpha sin(k)$$
Plug it into the equation:
$$\alpha sin(k+2) + \alpha sin(k) = sin(k)$$
Then we get
$$\alpha = \frac{sin (k)}{2sin(k+1)cos(1)}$$
by using the identity
$$sin(\theta) + sin(\alpha) = 2sin(\frac{\theta + \alpha}{2})cos(\frac{\theta - \alpha}{2})$$
The answer for $$\alpha$$ is obviously not the right answer.
Did I make the wrong substitution?

Anyone?

tiny-tim
Homework Helper
Try
$$y[k]=\alpha sin(k)$$
Hi yoran!

Try $$y[k]=\alpha\,sin(k\,-\,1)$$ .

Ok, I tried
$$y[k]=\alpha \sin(k-1)$$.
Then I get that
$$\alpha = \frac{1}{2\cos 1}$$
So given the solution for the homogeneous equation and this solution, I have that
$$y[k]=c_1\sin{\frac{\pi}{2}k} + c_2\cos{\frac{\pi}{2}k} + \frac{1}{2\cos{1}}\sin{k-1}$$
But the answer should be
$$y[k]=c_1\sin{\frac{\pi}{2}k} + c_2\cos{\frac{\pi}{2}k} + \frac{\sin{k}+\sin(k-2)}{2(1+\cos{2})}$$
Where does it go wrong in my solution?

tiny-tim
Homework Helper
Hi yoran!
…I have that
$$y[k]=c_1\sin{\frac{\pi}{2}k} + c_2\cos{\frac{\pi}{2}k} + \frac{1}{2\cos{1}}\sin{k-1}$$
But the answer should be
$$y[k]=c_1\sin{\frac{\pi}{2}k} + c_2\cos{\frac{\pi}{2}k} + \frac{\sin{k}+\sin(k-2)}{2(1+\cos{2})}$$
Where does it go wrong in my solution?
:rofl: But they're the same! :rofl:

Standard trig equation: 1 + cos(2) = 2cos²(1).

So $$\frac{\sin{k}+\sin(k-2)}{2(1+\cos{2})}$$ = … ?

Hehe, of course... Thanks a lot!
$$\frac{\sin{k}+\sin(k-2)}{2(1+\cos{2})}=\frac{2\sin(k-1)\cos(1)}{4\cos^2(1)}=\frac{\sin(k-1)}{2\cos 1}$$