1
vote
1answer
28 views

Solving a second level functional equation over all functions $g$

I am trying to find a closed form expression $f$ such that $$f(g(x+1) - g(x)) + f(g(x) - g(x-1)) = f(g(x))$$ For all functions $g$ I have concluded that for polynomials $$2^{n+1}f(0) = f(a_0 + ...
2
votes
0answers
38 views

Dynamic Programming: Stock Exercise

I'm having a trouble dealing with this problem: Since future market prices, and the effect of large sales on these prices, are very hard to predict, brokerage firms use models of the market to ...
2
votes
2answers
46 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
0
votes
1answer
58 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
-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}) ...
0
votes
1answer
24 views

how to write a recursive definition

so the question asks to define s(n) as the number of strings of a's b's and c's of length n that do not contains "aa". write a recursive definition for s(n). what is s(0),s(1),s(2),s(3). i had to ...
0
votes
0answers
24 views

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity

How to prove that in optimal strategie of tower of Hanoi none of the disks can't be placed on a disk of same parity if we have 3 rods. So for example disk 2 can't be placed on disk 4, or disk 1 can't ...
2
votes
1answer
188 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
3answers
152 views

Recurrence relations (Big-O notation)

Say I'm given a recursive function such as: function(n) { if (n <= 1) return; int i; for(i = 0; i < n; i++) { function(0.8n) } } ...
4
votes
5answers
777 views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
0
votes
3answers
33 views

A closed form for the recursion?

Let $x$ and $y$ be real numbers and $x < y$ Given the recursion: $m_0 = \frac{x+y}{2}$ and $m_1 =\frac{m_0+ y}{2}$, so in general, $$m_i = \frac{m_{i-1} + y}{2}$$.. What is $m_{\infty}$? thanks ...
0
votes
1answer
29 views

Time complexity of indirect recursion

How to find the complexity of an the given algorithm: Algorithm f(int n) { if(n==1)return(1); else { f(n-1)+g(n-1); } } Algorithm g(int n) { ...
2
votes
1answer
75 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
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 ...
2
votes
3answers
92 views

Can I use the master theorem for this?

this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method: $$T(n) = 4T(n/3) + n \log \log n$$ I want to ...
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 ...
1
vote
0answers
41 views

Is undecidability of arithmetic a corollary of Tarski undefinability theorem?

Arithmetic is undecidable, in other words the set of Godel numbers of theorems of arithmetic is not recursive, and so there is no algorithm/ recursive function to decide if a statement is provable or ...
4
votes
3answers
66 views

Recursion, multiplication and exponential

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} ...
2
votes
4answers
112 views

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+…+T(\frac n {2^k})$

find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ while k is some constant and for any $n\leq3$ $\ T(n)=c$ for k=1 ...
1
vote
2answers
67 views

How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
1
vote
1answer
54 views

How does my textbook come up with this statement? I don't believe it to be true.

My textbook (Introduction to Algorithms) states the following: When polynomially comparing $n^\epsilon$ and $lgn$, it states that $n^\epsilon$ is polynomially greater for any positive $\epsilon$. ...
1
vote
3answers
77 views

Where is the value of the variable $\epsilon$ obtained in the following explanation my professor gave?

My professor gave us this explanation from the textbook Introduction to Algorithms regarding the Master Method/Theorem: As a first example, consider $$T(n)=9T(n/3)+n.$$ For this recurrence, we ...
0
votes
2answers
127 views

Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...
0
votes
0answers
68 views

How is the algorithm for recursively printing permutations of a set of numbers this equation our professor gave us?

I'm having a great amount of trouble understanding where my prof got $T(m, n) = n(T(m+1, n-1) + m+1 + n)$ if $n > 1$ as the recursive formula for the algorithm for recursively printing the ...
0
votes
1answer
25 views

Defining a recursive function $f$ on $\{a, b\}$*

I would need some help on how I can define a recursive function $f$ on $\{a, b\}$* Define a recursive function $f$ on $\{a, b\}$* which replaces any $a$ with $b$ and vice versa, for example, ...
0
votes
2answers
58 views

I need some help on solving a recursive function question

I'm working on a recursive function task which i'm a bit stuck at. I've tried to google it on how I can solve this task, but with no luck Here is the task: Provide a recursive function $r$ on ...
0
votes
1answer
73 views

How can I solve this recursion function task?

I really need help on this task. Im stuck at it and I really would appreciate your help here. Give a recursive function $r$ on $A$ that reverses a string. For instance, $r(logikk) = kkigol$ and ...
1
vote
3answers
51 views

How does my professor go from this logarithm to the following one of a different base?

I don't understand on the second last line how my professor goes from $2^{log_3(n)} = n^{log_3(2)}$ how is that relation formed?
4
votes
1answer
453 views

Fibonacci with Mortal Bunnies

I am trying to understand a twist on the Fibonacci bunnies scenario, where the bunnies die x generations after their birth (where x is a positive integer). An example is shown here. I understand the ...
2
votes
1answer
93 views

Algorithm analysis

Consider a recursive Mergesort implementation that calls Insertion Sort on sublists smaller than some threshold. If there are n calls to Mergesort, how many calls will there be to Insertion Sort? ...
2
votes
2answers
109 views

Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number ...
1
vote
1answer
85 views

Orange Juice, Milk, or Beer

Suppose that we have $n$ dollars and that each day we buy either orange juice for a dollar, milk for two dollars, or beer for two dollars. If $R_n$ is the number of ways of spending all the money, ...
0
votes
3answers
163 views

(CHECK) $n$-bit Strings Containing a Pattern

$$\text{$\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}$}$$ If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and ...
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 ...
5
votes
2answers
199 views

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: $g(1) = \alpha;$ $g(2n+j) = 3g(n) + γn + β_j$ : j = 0,1 and n >= 1 I have assumed the closed form to ...
0
votes
2answers
61 views

Equation of a curve whose difference in ordinate values form an arithmetic sequence

I have the following recurrence equation that I have obtained while trying to solve a problem:- $$T(0) = 1$$ $$T(n) = T(n-1) + 9n - 8: n \ge 1$$ The values of $T(n)$ for $n = 0,1,2,... $ are as ...
2
votes
2answers
122 views

Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
0
votes
1answer
82 views

Bounded recursive sequence

I would like to know if there are known bounded recursive sequence (non monotonic): It shouldn't be a constant, neither a convergent sequence, nor a periodic one. (I am not asking for a true random ...
3
votes
1answer
108 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...
1
vote
2answers
163 views

Recursive relation using successor function

What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: ...
0
votes
0answers
24 views

Using the substitution method prove that T(n) = T(n - 1) + Theta(n) is Theta(n^2) [duplicate]

Possible Duplicate: I need to prove the following by using the substitution method -> $T(n) = T(n - 1) + \Theta(n)$ is $\Theta(n^2)$ The title is pretty much self explanatory. How can I ...
3
votes
1answer
157 views

$\mu$-recursive definition of ulam (3n+1) function

$\newcommand{\ulam}{\operatorname{ulam}}$ The ulam function is defined as $$ \ulam(x) = \begin{cases} 1 & x = 1 \\ \ulam\left( \frac{x}{2}\right) & x \text{ even}\\ \ulam(3x+1) & ...