# Tagged Questions

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

164 views

### Generating Functions, Recursive Polynomials

At the CMFT international conference in Turkey (2009), the following open problem was given: Show that $$p_n(x):=\sum_{k=0}^n \frac{(n-k)^k}{k!}x^{n-k}$$ has only real simple zeros for every $n$. ...
134 views

### Is there a simplification for the coefficients generated with the Mandelbrot iteration rule?

The Mandelbrot Set is obtained using the equation $z_n=z_{n-1}^2+c$ for some constant $c \in \mathbb{C}$ with $z_0=0$. Therefore, $z_1=c$, $z_2=c^2+c$, $z_3=c^4+2c^3+c^2+c$, etc. I have a function ...
875 views

### When do ﬂoors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
212 views

### Fractional iteration of the Newton-approximation-formula: how to resolve one unknown parameter?

For my own exercising I tried to find a closed form expression for the Newton-approximation algorithm, beginning with the simple example for getting the squareroot of some given $\small z^2$ by ...
134 views

### Algorithm for Converting Rational Into Surreal Number

I'm writing a library in Haskell that represents the class of surreal numbers, which like many things can be read about here. I've run into a problem in converting between other classes of numbers (...
45 views

### What's the next “recursion” here?

Plotting a single 3d helix is x = cos(t); y = sin(t); z = t; From this equation: x = [R + a cos(\omega t)] cos t y = [R + a cos(\omega t)] sin t z = h t + a sin(omega t) Comes the awesome ...
99 views

### What is this method of dividing a plane called?

I have an idea of a method for recursively dividing a plane, and as I'd like to do more research about this algorithm and the set of points that it produces, I'd like to know what it's formally known ...
174 views

### Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
267 views

### Question about recursive defined functions.

This question is about counting functions. With counting functions $F$ I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than ...
125 views

### Finding a solution to $\sum _{n=1}^{n=k} \frac{1}{n^x}+\sum _{n=1}^{n=k} \frac{1}{n^y}=0$

Scroll down to the update to see what I am meaning. The Mathematica program below finds a solution to the equation: $$\sum _{n=1}^5 \frac{1}{n^x}+\sum _{n=1}^5 \frac{1}{n^y}=0$$ My question is if you ...
28 views

### Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$. I want to show that $W(n)\in \Theta(n)$. Attempt 1 I understand the technique used in this question that solves ...
77 views

### Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
300 views

### How to find a enclosed envelope with maximum points among a cloud of spheres? [ Concave Hull ]

I have a questions regarding the selection of the outer points (i.e. sphere center), among a collection of many spheres in 2D/3D space. The outer points is that when all of these points are ...
104 views

### Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
101 views

27 views

### What are the first three values for the following recursive sequence?

$a_0 = 3$ $a_n = (a_{n-1})^2 + (a_{n-2})^2 +\cdots + (a_0)^2$ for all integers $n\geq 1$. Would that mean $a_1 = a_0^2 = 9$? Thanks!
29 views

### Is there a decimal based way to take roots or exponents?

We all know about division using decimals and places, you just keep dividing each digit place and move on to the next one. I was wondering if there was a similar method by which you could manually ...
29 views

### Infinite series, continued fractions, nested radicals and such - is there a general recursive algorithm theory?

The nature of infinity and irrational numbers (among other things) always gave me trouble. But recently I learned to think about infinite sequences in terms of recursive algorithms and their time ...
59 views

### Number of Hamilton paths in an extremely dense undirected simple graph

What is the fastest way (algorithm) to calculate the number of Hamilton paths in an extremely dense undirected simple graph (approximately 99.99% edges are connected)? I was thinking of the following ...
29 views

### When the integers got upset.

I have been stuck with this problem for quite large time. https://www.hackerearth.com/code-monk-bit-manipulation/algorithm/when-the-integers-got-upset/. In short what is says is: There are two arrays ...
19 views

### Nodes equation: can't find formula.

Given the level $N$ at which a node $X$ is located in a binary tree, to search for node $X$ according to level-order traversal, we can use the knowledge of level $N$ where $X$ is located to narrow our ...
21 views

### Average gap of a sorted sequence.

Considering a sorted sequence $a_0\leq a_1\leq...\leq a_{n-1}$ and defining the average gap of any subsequence to be:- $f(i,j)=\frac{(aj-ai)}{(j-i)}$, I would like to show that for all $i=1,...,n-2$...
54 views

### Generalization of a FFT with powers of 3

I'm not satisfied with the current answers asked about this on MathSE. So I'm going to ask: Describe the generalization of the FFT algorithm to the case in which n is a power of 3. What's the runtime?...