# Questions tagged [recursion]

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 a function for some inputs in terms of the values of the same function on other inputs. Please use the tag 'computability' instead for questions about "recursive functions" in computability theory

2,074 questions
Filter by
Sorted by
Tagged with
63 views

### Solving recursive function with floor

The recursive function is this: $$T(n) = \begin{cases} 2 & \text{ for }n=1;\\ T \left( \lfloor \frac{n}{2} \rfloor \right) + 7 &,\text{ otherwise} \end{cases}$$ Based on the definition of ...
27 views

### Statistics/Discrete Math Recurrence Questions - which of the following are true for integers… [closed]

Can someone explain why the answer for 12 is d) and why the answer for 13 is b)? I'm trying to study for a test tomorrow but I'm looking over the answers for this practice test and I genuinely don't ...
52 views

### 2-cycle and eventually fixed point at periodic point problem

Given $f(x) = x^2-1$. Prove that the basin of attraction of the 2-cycle $\{-1,0\}$ consists of all numbers in the interval $\left(\frac{1-\sqrt5}2, \frac{1+\sqrt5}2\right)$, except for the points ...
28 views

### proof problem of Period 3 point of a function

Let $f(x) = 1/(1-x)$. Show that if x ≠ 0,1, then $x$ is a period 3 point. What I did was I took the 3rd iterate $f^3(x) = f(f(f(x)=x$, ie I took $-\frac{1-\frac{1}{1-x}}{\frac{1}{1-x}}$ and when ...
51 views

### Is it 2 cycle attracting?

Let $c$ be a constant and let $f(x) = x^3-3x+c$, $c>0$. Determine the values of c for which ${0,c}$ is a 2-cycle. Is the 2-cycle attracting for the value of $c$? Explain. I am having trouble ...
40 views

### Verifying a Recursion Formula

I am attempting to prove the equation at the bottom of the image, or simply verify that it is a true mathematical relationship. I have computed a(3) and, in the latter part of the question, found the ...
44 views

34 views

### Calculating the odds of selecting a group, then a specific element of a group

It's been a while since I took probabilities and statistics in school, so I wouldn't be too surprised if this is simpler than I thought but I haven't had much luck figuring it out so far. Lets say you ...
23 views

74 views

### You started with one chip. You need to get 4 chips to win. What is the probability that you will win?

This is very similar to the question I've just asked, except now the requirement is to gain $4$ chips to win (instead of $3$) The game is: You start with one chip. You flip a fair coin. If it ...
52 views

### Given that you started with one chip, what is the probability that you will win this game?

The game is: You start with one chip. You flip a fair coin. If it throws heads, you gain one chip. If it throws tails, you lose one chip. If you have zero chips, you lose the game. If you have ...
28 views

### Why does probability recursion not work in this case? “What is the probability that the person who makes the first roll wins the game?”

So the first example (where recursion works) the author provided is You play a dice game with a friend. You roll a fair 6-sided die and your friend rolls a fair 8-sided die. You add $2$ to your ...
52 views

### Sum index in a Recursive Procedure Call in Maple

I'm trying to reproduce Buchholz Polynomials in Maple as outlined by J. Sesma and J. Abad in their paper (equation 14). The definition given above is a recursive one and so is the code I've created ...
21 views

### Developing a recursive formula for probability problem? [duplicate]

I'm trying to figure out the following problem from Bertsekas & Tsitsiklis' Introduction to Probability, 2nd edition: Two players take turns removing a ball from a jar that initially contains ...
21 views

### linear homogeneous recursion roots second degree

This is just a random example, I just wonder how to solve linear homogeneous recursion relations. If we say that $b_n = b_{n−1} + 2b_{n−2}$ and $b_1 = 1$ and $b_2 = 2$, how do I find the equation for ...
Suppose we are to count bit sequences of length $n$ s.t the sequence doesn't contain 3 consecutive 1's If $P(n)$ is the number of such sequences, is the equality $P(n) = P(n-1) + P(n-2) + P(n-3)$ ...