Recent content by magneto1

Ran across this problem reading another forum, and wonder if PHP allies here. Given a set $X$ of 16 positive distinct integers, you can find non-empty, disjoint subsets $A, B \subset X$ such that $A$ and $B$ have the same number of elements, and $|\alpha - \beta| < 0.0025$, where $\alpha =...

The equation follows from the definition of $R$ and the problem statement. The inequality follows from the fact that, for $m \geq n$ \[ \binom mn < \sum_k \binom mk = 2^m. \]

You want to use (or proof) the result: \[ R(r,s) \leq \binom{r+s-2}{r-1}. \] In your example, $R(2,2) = 2$, in other words, any graph that has $2$ or more vertices, you are going to find a $2$-clique or $2$-independent set. But that's not what the actual statement you want to prove. In the...

Apply Ramsey's theory. Let $R(m,n)$ be the least integer $s$ where a graph $G$ with $s$ vertices contain either a $m$-clique or an $n$-independent set. Then, use the properties of $R(\cdot, \cdot)$ to show that $R(n,n) \leq 2^{2n}$.

The original question was to show all members of the sequence are integers. However, I am interested in a "closed form" formula for this recurrence. (Since the sequence is increasing, its limit does not exist.)

Not sure if Discrete Math is the correct category, but I'm looking for some idea / hint on how to tackle the following recurrence. $a_0 = 2$, and $a_{n+1} = 2a_{n} + \sqrt{3(a_n)^2 - 12}$ for $n \in \Bbb{N}$. Some attempts to massage the equation got me: $(a_{n+1}-a_n)^2 = 2a_na_{n+1} - 12$...

Do you mean $\lceil \frac{n}{2} \rceil$ comparisons?

It is not wrong. You can show the implications in any order: E.g $Q \Rightarrow P \Rightarrow R \Rightarrow Q$, or $R \Rightarrow P \Rightarrow Q \Rightarrow R$. In fact, you usually want to choose an ordering that makes the proof the simplest if possible.

If you can show $Q \Rightarrow R$ and $R \Rightarrow P$, that immediately implies $Q \Rightarrow P$; it is unnecessary to show it explicitly.

The outline of a proof goes something like this. Let $f(x) := \left\lfloor{nx}\right\rfloor - \sum_{k=0}^{n-1} \left\lfloor{x + \frac kn}\right\rfloor$. Show $f$ has the properties: $(i)$: $f(x + \frac 1n) = f(x)$, and $(ii)$: $f(x) = 0$ for $0 \leq x < \frac 1n$. Then, claim that if $f$ has...

In reference to the POTW, a cleaner solution would probably be to show $y^3 - 1 = (y - 1)(y^2 + y + 1) $ contains an odd factor regardless the parity of $y$. This get rid of the need of induction. However, the principle of induction is just for a predicate, or property, $P(x)$ to hold for...

There is no need to introduce $N$ in your proof, since $N$ is empty. You were given $f(n) \geq \varepsilon$ for all natural $n$. The reason why there is a $\max M + 1$ as I suggested is to find a $n_0$ where the bound will hold for $n > n_0$ (or sufficiently large $n$). Note that the entire...

Let $M$ be the finite set where there are no constants $c_1, c_2$ where $g(n) \leq c_1f(n) + c_2$. To show $g \in O(f)$ by definition of $O()$, choose $c = c_1 + \frac{c_2}{\varepsilon}$, and let $n_0 = \max{M} + 1$.

Oops. The font rendering in Safari is messing up. Then, $\sqrt 6 - \sqrt 2 = \sqrt 2 (\sqrt 3 - 1)$. Since the number are positive, use $a = \sqrt{a^2}$. $ \sqrt 2 (\sqrt 3 - 1) = \sqrt{2 (\sqrt{3}-1)^2}$, and deduce from there $2\sqrt{2-\sqrt 3}$.