Tagged Questions

0
votes
1answer
21 views

Recursive Definitions with Converse

I think I know how to solve i. and ii., but not iii: Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$. (For i and ii): Prove that if $(a,b) \in ...
0
votes
4answers
121 views

Solving recurrence relations (change variable etc.) problems

I have been given $$f(1) = 3\\ f(2) = 8\\ f(n) = 6f(n/2) - 8 f(n/4) \;,\;\; n > 0$$ How would I go about solving this? I've tried working so hard to get this to no avail. If someone can ...
1
vote
0answers
38 views

Solving Recursive Equations: How to transform the domain in such cases?

I understand that a widely-used recursive equation for the Binary Search is as follows: $$ \begin{align} T(1) &= 1\\ T(n) &= T(\tfrac{n}{2}) + 1, \quad n>1 \end{align} $$ In order to solve ...
1
vote
1answer
61 views

Find a closed form for the recurrence relation $h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}$

I have a recurrence equation as follows: $$h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}\;,$$ with $h_{0}=0,h_{1}=1,h_{2}=2$.
1
vote
5answers
153 views

How do we deal with recurrence relation characteristic equations that are not quadratic or have imaginary roots?

Suppose we have $$H(n) = H(n-1)-H(n-2) \rightarrow x^2-x+1 \rightarrow r_1 = \frac{1+\sqrt{-3}}{2}, r_2 = \frac{1-\sqrt{-3}}{2}$$ or $$H(n) = H(n-1)+H(n-2)+H(n-3) \rightarrow x^3-x^2-x-1=0$$ In ...
2
votes
3answers
85 views

Can someone intuitively explain the towers of Hanoi and how a proof by induction can be used?

I'm having trouble understanding precisely how the proof by induction is used to show that it takes at most $2^n-1$ moves to get all the disks from one peg to another. Are there any helpful sources ...
2
votes
2answers
101 views

How to define divisibility recursively?

Let $d(x,y)=1$ if $x$ is divisible by $y$, and $=0$ otherwise. How can I define $d(x,y)$ in terms of just the basic primitive recursive functions (zero, successor, identity, projection) and the ...
3
votes
1answer
192 views

Karatsuba Multiplication

Karatsuba's equation to reduce the amount of time it takes in brute force multiplication is as follows (I believe this is a divide-and-conquer algorithm): $$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd ...
1
vote
1answer
272 views

Ulam's problem - guessing a chosen number in a set

I tried to solve the following problem, which I found in the book "Discrete Mathematics and Its Applications", by Kenneth Rosen (Problem 28 of the section 7.3 of the 6th Edition): Suppose someone ...
4
votes
1answer
671 views

Quick sort algorithm average case complexity analysis

This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications". The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm ...
0
votes
1answer
165 views

Finding Big-Theta

I need to use the Master Theorem to find $\Theta(f(n))$ if $f(n)=f(n/2)+3n$ and $f(1)=3$ I don't know how to use the MT in this case, can anyone provide help?
4
votes
1answer
197 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
3
votes
2answers
191 views

Determining a recurrence relation (Homework)

Let ${d_n}$ be the number of DNA strings of length n that contain a pair of consecutive nucleotides of the same type. There are four symbols used in strings of DNA: A, C, G, T. The nucleotides are ...
5
votes
2answers
623 views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...