# Tagged Questions

Recursion is the process of repeating items in a self-similar way. A recursive definition (or inductive definition) in mathematical logic and computer science is used to define an object in terms of itself. A recursive definition of a function defines values of the functions for some inputs in ...

8k views

### What is the solution to the following recurrence relation with square root: $T(n)=T (\sqrt{n}) + 1$?

This looks like a question asked earlier, but it isn't. $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad & \text{ if } n>1 \\ 1 & \text{ if }n=1\end{cases}$$ My professor gave this to me in ...
357 views

### Establishing formula from recurrence

Can anyone tell me how do we establish a formula from a given recurrence relation? Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$ When I write out the first few values, it ...
2k views

### solve $T(n)=T(n-1)+T(\frac{n}{2})+n$

Using the recursion tree i tried solving this: $T(n)=T(n-1)+T(\frac{n}{2})+n$; the tree has two parts (branches) one that of $T(n-1)$ and other branch is of $T(\frac{n}{2})$. But as the term T(n-1) ...
232 views

656 views

Ignoring the axiom of regularity (and therefore the implication of "no set can contain itself"), would it be correct to state that the set that contains only itself is unique? My argument is that if ... 1answer 22 views ### induction with 2 recursive sequnces I'm having trouble solving this problem. I have relation for two sequences of natural numbers. $$a(n)+\sqrt3\cdot b(n)=\left(1+\sqrt3\right)^n$$ and I have to prove that recursions: \begin{align*... 1answer 376 views ### n Lines in the Plane How am I to "[u]se induction to show that n straight lines in the plane divide the plane into \frac{n^2+n+2}{2} regions"? It is assumed here that no two lines are parallel and that no three lines ... 1answer 93 views ### Proving Reversal of a Language in Recursive Way We define the reverse of a string as follows: (x_1x_2...x_n)^R=x_nx_{n-1}...x_1 where x_1,x_2,...,x_n \in \Sigma. We can also define the reverse of a language by L^R= \lbrace s' | \exists s ... 2answers 276 views ### Proving a recurrence relation for strings of characters containing an even number of a's We consider strings of n characters, each character being a, b, c, or d, that contain an even number of a's. (Recall that 0 is even.) Let E_n be the number of such strings. Prove ... 2answers 671 views ### How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps? Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ... 1answer 88 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 ... 3answers 112 views ### Proof by induction that recursive function \text{take} satisfies \text{take}(n) = 100 - 2n I'm sick and tired off posting threads about induction... I just can't seem to get it, I need someone to give me a detailed explanation and treat me like a 5 year old, literally. I'm wasting a lot of ... 2answers 3k views ### Asymptotic bounds of T(n) = T(n/2) + T(n/4) + T(n/8) + n This problem is given in "Introduction to Algorithms", by Thomas H. Cormen. I have the answer to it, but I don't understand it. The answer is, T(n) = \Theta(n). It would be really good if you ... 1answer 76 views ### Matlab Recursion Loop I need to create a loop to answer part c of the following linear algebra question. I'm new to Matlab so this is extremely confusing. I'm not sure how to make a loop that "counts" from 0-25 in order to ... 2answers 120 views ### Recursion: putting people into groups of 1 or 2 let n \gt 1 be an integer, and consider n people; P_1,P_2,...,P_n let A_n be the number of ways these n people can be divided into groups, such that each group have either one or two people ... 1answer 85 views ### Example of a recursive set S and a total recursive function f such that f(S) is not recursive? Browsing wikipedia, I stumbled on the following: "The image of a computable set under a total computable bijection is computable." Given the form of the theorem, there must be some example of a ... 1answer 69 views ### How many combinations can I make? let n \gt 1 be an integer, and consider n people; P_1, P_2,..., P_n let A_n be the number of ways these n people can be divided into groups, such that each group have either one or two ... 2answers 87 views ### Possible distinct binary tree structures at depth d I'm trying to figure out a recursive formula for the number of possible distinct binary trees at any depth d. I haven't been able to find any sort of sources on this. basically, at depth 0, the only ... 6answers 27k views ### Why is 1 - \frac{1}{1 - \frac{1}{1 - \ldots}} not real? So we all know that the continued fraction containing all 1s... x = 1 + \frac{1}{1 + \frac{1}{1 + \ldots}} $$yields the golden ratio x = \phi, which can easily be proven by rewriting it as ... 1answer 479 views ### The problem of the most visited point. Represents the set R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} as a rectangle of n by n as points in the figures below for exemple. How to calculate the number of circuits that visit ... 3answers 1k views ### Is there a slowest divergent function? So I've been playing around with some functions for a while, and started wondering about a slowest divergent function(as in \lim_{x\to\infty} f(x)\to\infty) and so I searched around for an answer. ... 1answer 323 views ### Limit of recursive sequence n^2q_n=1+(n-1)^2q_{n-1}+2(n-2)q_{n-2} When looking at this riddle, I came across the following sequence for the frequency of sampled integers between 1 and n in a without replacement/without neighbour sampling:$$q_1=1,\quad q_2=1/2,\... 1answer 127 views ### Is there a name for the recursive incenter of the contact triangle? Recently, I became aware that there are many more triangle centers than the four I learned about in school. This reminded me of a thought I had when I first learned about the incenter: what point ... 1answer 659 views ### Bell numbers, recursions, bijections Then$th Bell number, named after Eric Temple Bell (although he was far from the first to think about them), is the number of partitions of a set of cardinality$n$. If they are written in the top ... 7answers 202 views ### Convergence of$a_{n+1}=\sqrt{2-a_n}$I'm attempting to prove the convergence (or divergence, though I strongly suspect it converges) of a sequence defined as$a_{n+1}=\sqrt{2-a_n}$with$a_1=\sqrt{2}$. I cannot use the monotonic ... 5answers 738 views ### Evaluating tetration to infinite heights (e.g.,$2^{2^{2^{2^{.^{.^.}}}}}$) The Problem How can you evaluate (i.e., get a value for) Tetration (i.e., iterated exponentiation) to infinite heights? For example, what would be the value of this expression? $$2^{2^{2^{2^{2^{.^{... 3answers 816 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)+\gamma n+\beta_j$ $\mbox{for}\ j=0,1\ \mbox{and}\ n\geq1$ I ... 0answers 227 views ### Recursive and Primitive recursive functions According to the book that I'm reading, we can define the \mu-recursive functions inductively, as follows: The constant, projection, and successor functions are all \mu-recursive. If g_1, \... 2answers 101 views ### Prove function is Fibonacci sequence Stuck on how to finish a question I'm working on. Have to find the number of bitstrings of length n with no odd length maximal runs of ones. For example, when n=3 there are three such bitsrings: 011, ... 1answer 98 views ### Eigenvalues appear when the dimension of the Prime Index Matrix is a prime-th prime. Why? I had a look at the eigenvalues of the matrix, I called it Prime Index Matrix (is there a better name?), constructed like the following:$$ P_{k,p_k}=P_{p_k,k}=1, $$where p_k is the kth prime. ... 2answers 448 views ### A Recurrence Relation Involving a Square Root Consider the recurrence relation: a_{n+1} = \sqrt{a_n^2 -k}, where k>0, n\in\{0,1,n:a_n^2\geq k\}, and a_0>0 is known. Is it possible to obtain an expression for a_n in terms of n?... 1answer 111 views ### Does every positive rational number appear once and exactly once in the sequence \{f^n(0)\} , where f(x):=\frac1{2 \lfloor x \rfloor -x+1} Consider the map f:\mathbb Q^+ \to \mathbb Q^+ defined as f(x):=\dfrac1{2 \lfloor x \rfloor -x+1} , \forall x \in \mathbb Q^+ ; then is the function g:\mathbb Z^+ \to \mathbb Q^+ defined as g(... 1answer 91 views ### Solve a recursion using generating functions? Given the recursive equation :$$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$A fast solution that I can think of is placing n-1 instead of n , and then we'll get :$$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$... 2answers 3k views ### Convergence and limit of a recursive sequence Let p>0 and suppose that the sequence \{x_n\} is defined recursive as$$ x_1 = \sqrt{p}, \quad x_{n+1} = \sqrt{p + x_n}, $$for all n \in \mathbb{N}. How can I show that x_n converges, ... 2answers 58 views ### Number of 1s in the binary representation of n Trying to define the function b(n) which counts the number of 1s in the binary representation of n arithmetically I came up with the following definition:$$b(n)=m :\equiv (\exists k_1\dots k_m)... 2answers 213 views ### Are hyperoperators primitive recursive? I apologize if this question is too basic. I have read that the Ackerman function is the first example of a computable but NOT primitive recursive function. Hyperoperators seem to be closely related ... 2answers 176 views ###$ T(n)= T(\log n)+ \mathcal O(1) Recurrence Relation what is the solution of following recurrence relation? \begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end{align} a)O(log n)$b)$ O (log^* n) $c)$ O (log^2 n) $d)$ ...
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 ...