Tag Info

Hot answers tagged

5

HINT: If $a_n = \sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+\cdots}}}$ for all positive integers $n$, then we have $a_{n+1} = \sqrt{a_{n}+\underbrace{\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+\cdots}}}}_{a_n}} = \sqrt{a_n+a_n} = \sqrt{2a_n}$ for all $n \ge 2$.


4

This all boils down to the concept of positional notation. For example, consider the number $19$ (in base $10$), which in base $2$ becomes $10011$. To understand why, you need to understand what this notation mean: $$ 19_{10} = \color{lime}{1}\color{green}{0}\color{olive}{0}\color{grey}{1}1_2 := 1 \cdot 2^0 + \color{grey}{1} \cdot 2^1 + \color{olive}{0} ...


2

One quickly checks "whether a solution for the TSP (travelling salesman problem) is true" by quickly solving a coNP-complete problem. I don't know how much asking about uniqueness changes the situation.


2

First let $a_n = b_n + xn^2 + yn +z$. Compute $x,y,z$ such that we have $$b_n = b_{n-1} + 2b_{n-2} + 2^n$$ Now set $c_n = b_n/2^n$, we then have $$c_n = \dfrac{c_{n-1}}2 + \dfrac{c_{n-2}}2 + 1$$ Now you should be able to take it from here.


2

As written this is not going to work - you will have index collisions in your flattened matrix and will overwrite data. For example $(1, 1, 7)$ also maps to the 1-D index $21$ Your formula should be: $$ k = (x \times \max(y) \times \max(z)) + (y \times \max(z)) + z$$ And you invert it with $$z=k\mod\max(z)$$ $$y=(k-z)/\max(z)\mod\max(y)$$ And so on ...


2

$2^n$ is the number of vectors that can be chosen as the first element of the ordered pair. Once the first element is chosen, there are $\binom nk$ ways to choose $k$ of the bit positions to flip from 0 to 1 or vice versa to procude the second element of the pair. The distance between $(0,0,1,0)$ and $(1,0,1,1)$ is $2$ because the two vectors differ at ...


2

I'm going to assume the number is exactly $poly(n)$. The proof certificate for $L^C$ is the list of all words of length $n$ which are in $L$ with their proof certificates. To check whether $x \not\in L$ against the proof certificate, first check that the number of strings in the certificate is exactly $poly(n)$, then for each string in the certificate check ...


1

Drawing the digraph from the transition table is a mechanical procedure that doesn’t match the rest of your question. From the rest of your question it sounds as if what you’re actually trying to do is convert the non-deterministic machine to an equivalent deterministic one using the subset algorithm. I’ll make the further guess that the NDFSM has $4$ ...


1

Setting $b_n=\frac{a_n}{2^n}$ gives you $$\frac{a_n}{2^n}=\frac{8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n}{2^n}$$ $$\iff\frac{a_n}{2^n}=\frac{2\cdot 4a_{n-1}}{2^n}-\frac{2^2\cdot 5a_{n-2}}{2^n}+\frac{2^3\cdot 2a_{n-3}}{2^n}+\frac{2^n}{2^n}$$ $$\iff \frac{a_n}{2^n}=4\frac{a_{n-1}}{2^{n-1}}-5\frac{a_{n-2}}{2^{n-2}}+2\frac{a_{n-3}}{2^{n-3}}+1$$ $$\iff ...


1

HINT: With $S$ as the initial symbol, start with these productions: $$\begin{align*} &S\to aL\mid bL\mid Ra\mid Rb\\ &L\to aL\mid bL\mid X \end{align*}$$ Have $R$ do something similar to what $L$ does, and have $X$ generate the language $$\big\{x\#y:x,y\in\{a,b\}^*\land |x|=|y|\big\}\;.$$ In other words, generate excess length on one side, then ...


1

$ab$ is in the concatenation language but not in $L$; do you see why? For a correct argument I suggest using the pumping lemma for context-free languages.


1

One book that's really great is Serge Lang - Basic Mathematics. It's an algebra/trig book that is written like you're intelligent. It's written in the same style as more serious books.


1

There are several significant ambiguities in your question. The way the machines are encoded matters for this, as does the model of computation. Also, do you mean that the machine always halts, or that it halts for zero input? I will make reasonable assumptions to resolve these ambiguities, if that does not do it for you you will need to clarify your ...


1

If you look at the algorithm in the solution you linked you can see that median($X$) is not excluded if median($X$) = median($Y$). If median($X$) $\lt$ median($Y$) and $A$ = median($X$) then you get There are at most $\frac12 n$ elements less than $A$ in $X$. There are less than $\frac12 n$ elements less than $A$ in $Y$. In total this still gives less ...


1

Since $n\geq 9$ is a power of 3, we will write $n=3^x$ for variable $x\geq 2$. Substitute this into your recurrence, and you get $$a(3^x)=5a(3^{x-1})-6a(3^{x-2})+2x.$$ Now we define a new recurrence in terms of the variable $x$ as follows: define the function $a^*:x\mapsto a(3^x)$. Then, by the recurrence above, $a^*(x)$ satisfies the recurrence ...



Only top voted, non community-wiki answers of a minimum length are eligible