Tag Info

Hot answers tagged

4

The master theorem isn't a good theorem to apply in this case, it's power comes from situations where the input size is reduced by a constant fraction (not decreased by a constant amount). In this case, $$ T(n)=T(n-10)+n. $$ Then, $$ T(n-10)=T(n-20)+(n-10) $$ Similarly, $$ T(n-20)=T(n-30)+(n-20). $$ Therefore, $$ ...


2

You have proved that the limit exists, so let's set $$b:=\lim_{n\to\infty}b_n.$$ Given the recurrence relation $b_{n+1}^2=2+b_n$ we can take limits on both sides to find $$\lim_{n\to\infty}b_{n+1}^2=\lim_{n\to\infty}(2+b_n)=2+\lim_{n\to\infty}b_n=2+b.$$ Now on the left-hand side we have ...


2

Michael Burr's answer was first and is correct. Here is another way of explaining it using the technique of telescoping series. For every $n \in \{0, 1, 2, 3, \ldots\}$ we have: $$ T(n) - T(n-10) = n $$ Fix an integer $k \geq 1$. Writing this equation for $n\in\{10, 20, 30, ..., 10k\}$ gives: \begin{align} &\underbrace{T(10)}-T(0) &= 10\\ ...


2

Of course, no deterministic algorithm can generate truly random numbers. The goal is to find an algorithm that gives output values that 'behave as if' they are independent and identically distributed according to some distribution--usually $Unif(0, 1).$ By 'behave as if' one means that the pseudo-random numbers pass a large battery of benchmark tests for ...


1

Shift indices to get: $$ b_{n + 2} = 2 b_{n + 1} + b_n $$ Define the generating function: $$ B(z) = \sum_{n \ge 0} b_n z^n $$ Multiply the recurrence by $z^n$, sum over $n \ge 0$ and recognize the resulting sums: $$ \frac{B(z) - b_0 - b_1 z}{z^2} = 2 \frac{B(z) - b_0}{z} + B(z) $$ As partial fractions: $\begin{align} B(z) &= \frac{2z}{1 - 2 z ...


1

Let us assume WLOG that $n\equiv 1 \pmod{10}$, i.e. $n=10k+1$ for some nonnegative integer $k$. Then if $k\geqslant 1$, \begin{align} T(n) &= \sum_{j=0}^k T(10(k-j)+1) + 10(k-j)\\ &= T(1) + \sum_{j=0}^k 10(k-j)\\ &= T(1) + 10\sum_{j=1}^k j\\ &= T(1) + 5k(k+1)\\ &= T(1) + 5\left(\frac{n-1}{10}\right)\left(\frac{n}{10}\right)\\ &= T(1) ...


1

Let me explain why it is impossible to inscribe a regular pentagon into a regular hexagon in the way you want. Let's suppose that the side $AB$ of the hexagon contaning no pentagon vertex is parallel to side $GH$ of the pentagon (see picture). I'll take hexagon sides of unit length and set $x=AH$ so that $GH=1+x$ and $FH=1-x$. We can determine $x$ so that ...


1

A proof goes by using generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, and take your recurrence with initial values $a_0$ through $a_{k - 1}$. Shift indices to get: $\begin{align} a_{n + k} = c_1 a_{n + k - 1} + \dotsb + c_k a_n \end{align}$ Multiply by $z^n$, sum over $n \ge 0$ and get: $\begin{align} \sum_{n \ge 0} a_{n + k} z^n = c_1 ...


1

You aren't doing the induction correctly it should be T(n+1)=n+1 +2kn/2=(k+1)n+1 which is not less than kn Correct proof T(2) = 1 T(n) = n + 2T(n/2) T(n) <= k n lg(n) T(n+1) = n+ 2 (kn/2 lg(n/2)) = n + kn lg(n/2) < kn lg(n)


1

Denote $A(n)=\sqrt{T(n)}$ and solve for A formula. For example try to find in $A(n) = \lambda^{n}$ form.


1

You first prove that the right-shift operator $R$ is a linear operator on (doubly infinite) sequences. Then you define addition and scalar multiplication on operators so that you can given a sequence $f$ obeys a recurrence relation rewrite the recurrence relation as $(P(R))(f) = 0$ for some polynomial $P$, which is the characteristic polynomial. Now $P(R)$ ...


1

For the record, generating functions solve this type of problems in uniform way. Define $A(z) = \sum_{n \ge 0} a_n z^n$; take your recurrence, multiply by $z^n$ and add over $n \ge 0$: $\begin{align} \sum_{n \ge 0} a_{n + 2} z^n + 2 \sum_{n \ge 0} a_{n + 1} z^n - 3 \sum_{n \ge 0} a_n z^n &= \sum_{n \ge 0} n z^n + \sum_{n \ge 0} (-1)^n n 3^n ...



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