# Tagged Questions

20 views

### Recurrence Relation

So I am just making sure I am on the right track with this. I have the recurrence: T(n) = 2T(n-2) + 1 I am trying to solve this recurrence to get the time complexity T(n) = 2(2T(n-4) + 1) + 1 T(n) ...
25 views

90 views

### Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
24 views

### Solving a simple Recurrence in summation form(very special case)

I have a bit confusing recursion form $\sum_{n=2}^{\infty}\{f(n)\frac{n}{n-1}\}=C, \tag 1$ $f(0)=b,f(1)= a,f(2)=c$ and $C$ are constants. Could you help me to solve this recursion or help me to ...
242 views

### Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $f(1)=1$ and $f(2)=2$.
20 views

### Comparing Generalized Continued Fractions

Gosper lays out a method (under Approximations) for comparing regular (a.k.a simple) continued fractions which have all partial numerators set to 1. Continue comparing terms until they differ, then ...
27 views

### Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
76 views

### Limit of a recursiv trigonometric function

So while doing my math homework I recently stumbled upon this little thing: It seems that $y_n = \sin(y_{n-1}) + k$ with arbitrary $y_0$ and $k$ converges to a definite value for $n \to \infty$. ...
30 views

### Finding the inhomogeneous solution

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?
45 views

### Towers of Hanoi recurrence relation

How would I do this recurrence relation?
38 views

### Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
25 views

### recursive relation for putting signs in 2*n table

Consider we have a $2\times n$ table and we want to put a sign in some of the cells, and we don't put signs in both adjacent cells give a recursive phrase that shows that how many ways we can do that? ...
43 views

### N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
59 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 ...
46 views

I tried to solve this recurrence relation, but I was confused when I had to determine the pattern. $$T(n) = \begin{cases} 3, & \text{if }n = 0 \\ T(n - 1)^2, & \text{if }n > 0 \end{cases} ... 0answers 63 views ### Solving a Recurrence Relation With Summation and Tau Function How can I solve the following:$$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$Where d(n) is the Tau function, and v is the set of values dividing n. e.g. d(18) = ... 0answers 31 views ### Verify that this recurrence relation is in O(log n) For the recurrence T(n)=2*\lceil\frac{n+1}{2}\rceil+c is in \Theta(lg n) My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: T(n)=2*\lceil\frac{n+1}{2}\rceil+c ... 2answers 58 views ### Solving this recurrence relation Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction$$ {\rm ...
73 views

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$ I have been trying to solve this question but I could not find anything. My approach: $n = 2^k$ $S(k) = T(2^n)$ and $S(k/2) = ... 3answers 173 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) } } ... 3answers 34 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 ... 1answer 80 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})+nT(n)=\sqrt{n}T(\sqrt{n})+cT(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$T(2)=1 for all the problems Atleast give the final answer. 3answers 160 views ### How does$\tbinom{4n}{2n}$relate to$\tbinom{2n}{n}$? I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ... 1answer 100 views ### Help with Recursive Algorithm We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ... 1answer 96 views ### What's a useful recurrence relation for$(2n)!$in terms of$n!$? I want to make an algorithm for$n!$which will divide the number in half and call the algorithm again until n is so close to$0$that a value of$1$can be safely returned, and use the value of each ... 1answer 62 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 ...
I have a recursive relation algorithm which is defined as follows: $$F_n = 3(F_{n-1} - F_{n-2}) + F_{n-3}$$ $$F_0 = 0$$ $$F_1 = 1$$ $$F_2 = 4$$ From calculating the first few values, I know this is ...