# 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 ...
361 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) ...
236 views

656 views

214 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 ...
2k 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 ...
227 views

166 views

### Counting the number of different ways in which groups of one or two can be formed…

I'm having trouble proving that the number of ways n>3 people can be divided into groups of either one or two is equal to: $A_n = A_{n-1} + (n-1)⋅A_{n-2}$ I'm trying to prove this by counting but ...
108 views

### OEIS A000255 recursion.

I encountered the sequence A000255. $a(n)$ counts permutations of $[1,...,n+1]$ having no substring $[k,k+1]$ I am finding difficulty in proving it. Can you please give any clues or hints on how to ...