-4
votes
1answer
38 views

Find a recursive algorithm to find $a^{2^n}$

Edit1: Used Latex. =] Edit2: Thanks for the guidance to the users below. Really helped me out editing the post and guidance on the math problem. The question gave me a hint: $a^{2^{n+1}} = (a^{2^n}) ...
2
votes
1answer
185 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
1
vote
1answer
61 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
0
votes
1answer
33 views

Reccurence relation

Closed form of $\ nT_n = 3(n-1)T_{n-1} + 1, n \ge 1$ I've tried calculating some terms, and looking it up on wolframalpha, it sais the generating function is $\frac{exp(x)}{1-3x}$. Where do i start? ...
0
votes
3answers
152 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
3
votes
1answer
38 views

Finding a recursive definition and computing $B(10)$

For $n \geq 1$, let $B(n)$ be the number of ways to express $n$ as the sum of $1$s and $2$s, taking order into account. Thus $B(4) = 5$ because $4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = ...
1
vote
1answer
86 views

Inductive Definition of regular expression

Give an inductive definition of regular expressions that do not use the star operator. Prove by induction on this definition that every such expression denotes a finite language not containing lambda. ...
0
votes
1answer
87 views

Discrete Math: “Drop Zero in Bitstring” Recursive function

how do i define “dropzeros” of a bitstring as the result of dropping each 0 from the bitstring. ex) dropzeros of 11 is 11. The dropzeros of 1101 is 111. The dropzeros of 00 is the empty string. Let’s ...
0
votes
1answer
84 views

Discrete Math: Recursive Functions

You are given the following recursive definition defining a set of strings. 1∈S; x∈S → x11∈S. What are the 4 shortest members of the set? What does x11∈S mean?
0
votes
1answer
97 views

How does one solve recurrence relations involving subproblems of different sizes?

I just studied the Master Method for solving recurrences but found out that it is applicable only to the recurrence relations having same subproblem sizes, for instance in the following recurrence : ...
2
votes
1answer
153 views

How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm - $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
2
votes
1answer
53 views

help deriving a closed formula for this “magic function”

I'm having trouble coming up with a closed formula for $n$ from the sequence of numbers generated by this function: The following mystery function $M : N \times N \rightarrow N $ is defined by: $$ ...
1
vote
1answer
46 views

Asymptotic Equivalence of Another Recurrence: [duplicate]

So I have the following recurrence relation: $$f(n) = f(n-1) + f(\lceil n/2\rceil)+ 1$$ I already know that: If: $$g(n) = g(n-1) + 1$$ $$g(n) = O(n)$$ If: $$g(n) = g(\lceil n/2\rceil) + 1$$ ...
5
votes
1answer
157 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
3
votes
1answer
63 views

Recursively Defined Entities

So I am having some trouble understanding how one is to come up with the recursive definition to the following problem... We are given a rectangle of width $2$ and length $n$. Suppose we have ...
1
vote
2answers
61 views

Recursion problem help

The following are the teachers example problems. The issue is that I don't understand the exact steps they took to go from $f(0)$ to $f(1)$ to $f(2)$ to $f(3)$. What I'm asking here is if someone ...
0
votes
1answer
121 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
226 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
64 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
84 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
433 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 ...
4
votes
3answers
222 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
281 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
288 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
642 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 ...
5
votes
1answer
1k 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
299 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?
5
votes
1answer
337 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 - ...
4
votes
2answers
300 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 ...
6
votes
2answers
831 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 ...